Slides badge

Algorithm Specification

Learning Intentions

  • Understand the purpose of certain algorithms

  • Understand how to implement them in Python

Success Criteria

  • Be able to describe the purpose of a specified algorithm
  • Be able to implement the algorithms required for Higher using Python

Algorithms

  • Algorithms are a series of instructions that attempt to solve a problem.

  • A computer program may be composed of several algorithms.

  • For Higher Computing Science, you need to know about three different algorithms and be able to implement them in Python:

    • Linear search

    • Finding the minimum and maximum

    • Count occurrences 

  • Each of these algorithms relates to using an array.

Input validation

  • Input validation is actually an algorithm you need to know about from National 5.

  • The purpose of this algorithm is to ensure that the user inputs data that is in a specified format or range

GET input FROM KEYBOARD

WHILE input is invalid

  SEND message TO DISPLAY

  GET input FROM KEYBOARD

END WHILE

Input validation

  • Input validation is actually an algorithm you need to know about from National 5.

  • The purpose of this algorithm is to ensure that the user inputs data that is in a specified format or range

uname = input("Please insert your username")
while uname != "jb04":
  print("Your username is not correct")
  uname = input("Please try again. Insert your username")
print("Welcome to the system")

Linear search

  • The linear search algorithm is used to search through an array one element by one.

  • It is an inefficient algorithm because of an array consists of 10,000,000 elements - even with the fastest computer - this will take some time to process.

  • With a linear search, the user provides what is needed and the result is the index of the value that was being searched for.

Linear search

SET counter TO 0
RECEIVE desired_item FROM (STRING) KEYBOARD
REPEAT
   IF desired_item = nation[counter] THEN
     SEND "The program found  " & desired_item & " at position " & counter & " of the nation array." TO DISPLAY
   ELSE
     SET counter TO counter + 1
   END IF
UNTIL counter = 10
IF item_found = FALSE THEN
    SEND "The program did not find a match for " & desired_item & " within the nation array." TO DISPLAY
END IF

Convert the code before into a Python subprogram

Test it out

Python task

linear search in Python

  • We can implement the linear search algorithm very easily in Python as shown below

  • However, this algorithm is inefficient. Why?

def linearSearch(l, term):
  i = 0
  index = -1
  while (i < len(l)):
    if l[i] == term:
      index = i
    i = i + 1
  return index

people = ["Matthew", "Flynn", "Connor", "Finlay"]

print(linearSearch(people, "Connor"))

Linear search - what has changed?

SET item_found TO FALSE
SET counter TO 0
RECEIVE desired_item FROM (STRING) KEYBOARD
REPEAT
   IF desired_item = nation[counter] THEN
     SET item_found TO TRUE
     SEND "The program found  " & desired_item & " at position " & counter & " of the nation array." TO DISPLAY
   ELSE
     SET counter TO counter + 1
   END IF
UNTIL counter = 10 OR item_found = TRUE
IF item_found = FALSE THEN
    SEND "The program did not find a match for " & desired_item & " within the nation array." TO DISPLAY
END IF

How does this help?

  • In pairs discuss the two previous algorithms.
  • How is the second algorithm more efficient than the first?

Better linear search in Python

  • To implement the improved algorithm in Python we use the following code:

def linearSearch(l, term):
  found = False
  i = 0
  while (not(found) and i < len(l)):
    if l[i] == term:
      found = True
    i = i + 1
  return i

people = ["Matthew", "Flynn", "Connor", "Finlay"]

print(linearSearch(people, "Matthew"))

Even better linear search in Python

  • This can be improved by simply returning the index when the item is found, to make it even more efficient:

def linearSearch(l, term):
  i = 0
  while (i < len(l)):
    if l[i] == term:
      return i
    i = i + 1

  return -1

people = ["Matthew", "Flynn", "Connor", "Finlay"]

print(linearSearch(people, "Flynn"))

Add in a new subprogram into your program called linearSearchImproved.

Copy your linear search and improve the performance of this one by using the method with the flag

Python Task

Finding the minimum and maximum

  • Finding the minimum/maximum is another algorithm you need to know how to implement at Higher. 
  • Again, it's fairly straightforward. Below is an example of finding the maximum:

SET maximum TO items [0]
FOR counter FROM 1 TO 9 DO
   IF items [counter] > maximum THEN
     SET maximum TO items [counter]
   END IF
  END FOR
SEND "The maximum value was " & maximum TO DISPLAY

List of 10 test scores is show below:

 

[53, 12, 95, 54, 23, 45, 60, 72, 87, 48]

 

Implement a program to find the highest test score using Python. You should implement this in a subprogram.

Python task

Finding the maximum in Python

  • Below is a solution to the previous task

def findMaximum(l):
  i = 0
  max = l[0]
  while (i < len(l)):
    if l[i] > max:
      max = l[i]
    i = i + 1

  return max

scores = [53, 12, 95, 54, 23, 45, 60, 72, 87, 48]

print(findMaximum(scores))

Counting occurrences

  • Counting occurrences is the last algorithm you are expected to know at Higher and it's fairly straightforward. Below is an example of counting occurrences:

SET occurrence TO 0
RECEIVE desired_value FROM (INTEGER) KEYBOARD
FOR counter FROM 0 TO 9 DO
  IF age [counter] = desired_value THEN
    SET occurrence TO  occurrence + 1
  END IF
END FOR
SEND "There were " & occurrence & " occurrences of " & desired_value TO DISPLAY

A program is required to find out how many times a country was a certain temperature. A list of temperatures was provided:

 

[23, 34, 40, 43, 10, 23, 34, 22, 23, 43]

 

Write a subprogram to count how many times a temperature has occurred. Test it with 23 and 43.

Python Task

Finding the maximum in Python

  • Below is a solution to the previous task

def countOccurrences(l, term):
  total = 0
  for i in range(0, len(l)):
    if l[i] == term:
      total = total + 1
  return total

temperatures = [23, 34, 40, 43, 10, 23, 34, 22, 23, 43]

print(countOccurrences(temperatures, 23))
print(countOccurrences(temperatures, 43))

Work through the worksheet on Google Classroom.

Python Tasks

Presentation Overview
Close
JB
Algorithm Specification
© 2020 - 2024 J Balfour
08:55 | 21-05-2024
Join Live Session
Start Remote
Save Progress
Slideshow Outline
Presenter Mode
Widget Screen
Canvas Controls
Random Selector
Timer
Volume Meter
Binary Converter
Python Editor
Show Knox 90
Provide Feedback
Help
!
Keywords
    DragonDocs Management
    Random selector
    Sections
      Binary conversion
      Denary to binary conversion
      Binary to denary conversion
      Feedback 👍
      Accessibility

      Apply a filter:

      ×
      All slideshow files