Understand the purpose of certain algorithms
Understand how to implement them in Python
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
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 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")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")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.
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
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"))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
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"))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
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.
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))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.
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.
Apply a filter: