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

Algorithm Specification

00:50 | 07-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

Remove after pick

Sections

Binary conversion

Denary to binary conversion

Binary to denary conversion

Use two's complement

Slideshow Outline

Help

The following are key shortcuts for using DragonSlides and reveal.js.

Key combination	Action
→, PAGE DOWN, SPACE	Next slide
←, PAGE UP	Previous slide
SHIFT + →	Last Slide
SHIFT + ←	First slide
B	Whiteboard
W	Widget Board/White Screen
C	Toggle Notes Canvas
DEL	Clears Whiteboard/Notes Canvas
S	Show Presenter Mode
SHIFT + D	Toggle Dark Mode
H	Goes to the Home Slide
META + P	Show Print options window

In order to use the 'Start Remote' feature, you'll need to download JB Slide Controls from the Apple App Store. Once you have this you'll be able to control the slides using the app from you Apple Watch.

Feedback 👍

Accessibility

Apply a filter:

Dark Mode

Bold Text

All slideshow files