 # 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("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
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

## 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
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"))``````

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

## 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 
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.

## Finding the maximum in Python

• Below is a solution to the previous task

``````def findMaximum(l):
i = 0
max = l
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
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.

## 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

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.

Presentation Overview
Algorithm Specification
14:25 | 07-12-2023
!
Keywords
Random selector
Sections
Binary conversion
Denary to binary conversion
Binary to denary conversion
Feedback 👍
Accessibility

Apply a filter:

×
All slideshow files