Author: Amanda McGarrigle

Computing—Term 2
We are computational thinkers

Background Information
In this unit, the pupils participate in some hands-on unplugged activities that help them to develop an understanding of some important algorithms. They also investigate these when implemented as Scratch or Snap! programs.
This unit is designed to provide some depth to the pupils’ computational thinking by getting them to think through some of the most common problems in computing, e.g. search and sort, as well as some key areas of maths where an algorithmic approach is useful.
In computing, the pupils are expected to reason about algorithms to explain how they work. The activities here aim to develop this. The pupils look first at inefficient search algorithms (random and linear searching) before looking at binary (divide and conquer) search. In sorting, the pupils learn about an inefficient, but easy to understand algorithm (selection sort) before looking at the much more efficient quicksort algorithm.
The unit draws on their mathematical understanding as they look at algorithms for testing if a number is prime and finding the highest common factor or two numbers.
understanding as they look at algorithms for
testing if a number is prime and finding the highest
common factor of two numbers.

In this unit the children will…
develop the ability to reason logically about algorithms
understand how some key algorithms can be expressed as programs
understand that some algorithms are more efficient than others for the same problem
understand common algorithms for searching and sorting a list appreciate algorithmic approaches to problems in mathematics.
Random search jigsaw in Scratch: scratch.mit.edu/ projects/100911838/#editor
Linear search jigsaw in Scratch: scratch.mit.edu/ projects/100912018/#editor
Scratch program jigsaw at scratch.mit.edu/ projects/100912338/#editor
Buggy selection sort in Scratch: scratch.mit.edu/ projects/100912596/#editor
Buggy Snap! selection sort program at snap.berkeley.edu/ snapsource snap.html#present:Username=mgberry&ProjectName=buggyquicksort

By the end of this unit….
All children will:
Use random, linear and binary search to play the ‘Guess my number’ game
Sort yogurt pots into order by weight with the pan balance using their own algorithm and quicksort
Test whether small numbers are prime
Work out the highest common factor of a pair of numbers
Most children will:
Record algorithms for random, linear and binary search
Record an algorithm for sorting
Appreciate that quicksort will be faster than, e.g. selection sort
Record an algorithm for testing if a number is prime
Record an algorithm for working out the highest common factor of a pair of numbers
Some children will:
Correct the Scratch jigsaws for random, linear and binary search
Correct the Scratch selection sort program
Correct the Snap! quicksort program
Implement their prime test algorithm as a program
Implement their highest common factor algorithm as a program

The children will explore:
Random and Linear search - Guess my number game
Binary search— Divide and conquer
Selection sort— Buggy selection sort
Quick sort—pupils to practise this method, using the pan balance or slips of paper.
Testing if a number is prime
Finding the highest common factor

Key Vocabulary
Computational thinking: Looking at systems and problems in a way which would allow computer systems to be
used to model or solve these.
Random search: Algorithm by which items are compared to the one required in random order until a matching item is found.
Linear search: Algorithm by which items are compared to the one required one at a time in the order in which they are stored, until the right one is found.
Pseudocode: An informal but detailed written description of an algorithm, allowing it to be coded in a range of programming languages.
Algorithm: An unambiguous set of rules or a precise step-by-step guide to solve a problem or achieve a particular objective.
Binary search: Divide and conquer algorithm in which the set of possible matches is halved at each comparison.
Selection sort: Algorithm in which the largest, second largest, third largest and so on items from a list are found, enabling the list to be sorted.
Prime number: A number which can be divided by exactly two other numbers, one and itself.
Highest common factor (HCF): The largest number which divides exactly into two (or more) other numbers
Debug: To fix the errors in a program.