GCSE Algorithms
There are various ways to describe algorithms, from natural language (which can imprecise), through flowcharts (which are often used to plan out the sequence in which events must take place in an algorithm) to pseudocode which is a much more formal version of natural language, designed to imitate a programming language. At GCSE level students are required to be able to read and understand these various representations, as well as being able to produce their own implementations of them.
It is also a requirement of the GCSE Specifications that students need to understand some of the details involved in common searching and sorting algorithms, as well as knowing some of their performance characteristics i.e. to compare the speeds of the algorithms.
Tourist Town - Dominating Sets
It is also a requirement of the new GCSE Specifications that students, need to understand some of the details involved in common searching and sorting algorithms, as well as knowing some of the performance characteristics of them (to the extent that they can compare the speeds of the algorithms. This is an activity requiring the students to solve a problem about Ice Cream Vans and their placement with regards to streets in order to minimise people's travel time to get an ice cream and minimise the number of vans required. Although the task is described as being accessible to children as young as 7, coming up with some sort of algorithm to solve the problem could be quite a complex task. The discussion regarding this style of problem which is included within the resource goes past the level required for GCSE Computer Science, but may be of interest to the brightest students. This final discussion (the 'Whats it all about?' section) can be safely omitted if the content is beyond the class, although the first sentence of the section might still be used.
Introduction to Pseudocode
This activity features detailed instructions for a lesson to introduce the concept of pseudocode, using fairly simple but accessible graphics. The students are required to devise instructions in order to move a cartoon character on a grid including being able to interact with its' environment by picking up bananas. Some editing of the presentation may be required to remove references to the original teacher on specific slides. The lesson plan included also makes reference to various levels, which will need adapting to whichever scheme is in use in a school.
Pseudocode Challenge
This activity contains a resource which is accessed via the web browser. The web page once loaded contains 20 interactive Pseudocode challenges. A detailed explanation of Pseudocode is included along with answers to the problems, and instructions for how to get this activity up and running on an older Raspberry Pi.
Introduction to Algorithms
This resource details a real-world algorithm which students are unlikely to have encountered previously. The Luhn Algorithm is one method for validating that the long number on a credit/debit card is a valid number (it doesn't check if the card is actually a credit/debit one, just that the number conforms to the specific pattern required). An explanation of the algorithm is provided, along with an example, it then asks students to write a program to implement this algorithm. Adding a step requiring the students to produce a flowchart and/or pseudocode first would probably be desirable. There is an implementation of the algorithm provided which uses Visual Basic, but none of the resources require students to use this for their implementation.
Flowcharts and Pseudocode
An introductory lesson, linking ideas from flowcharts to the use of pseudocode. The presentation may need some editing to remove school specific information. It contains a link to the "Friendship Algorithm" sequence from Big Bang Theory and a link to the description section for Algorithms and Pseudocode from BBC Bitesize. The presentation takes students through a recap of flowcharts before moving on to introduce simple pseudocode. There is also a worksheet which comes in two versions differentiated by ability and answers for these sheets.
Coded simulation of Bubble Sort
This presentation guides students through an explanation & coded simulation of Bubble Sort. Students can add to this later by adding another option for Merge Sort with the potential to then measure the time taken for each algorithm to form a basis to compare the time complexity of the two. A copy of the python code is included (uses version 3.3.5).to enable the students to look at an implementation and interact with it as it runs.
Game Show Algorithms
This resource is taken from CS4FN publication. Although this activity is not in the form of a lesson plan, the activity illustrates a good series of steps that students could either work through as a class, or in smaller groups/pairs. They could then be asked to pick from a selection of existing real Game Shows or ones made up by the teacher in order to do a similar activity for themselves. The content could also be used to introduce flow charts with a small amount of modification.
The 21 Card Trick
The book "The Magic of Computer Science" contains a variety of tricks that relate to various elements of computer science.
In this resource, the algorithm for which is then described, along with why this ensures that the trick will always work. This makes for a good starting point in order to get students analysing an existing solution and describing it using an algorithm. Once they have worked through this trick, a further activity might be to get them to analyse and "prove" (to an extent) the algorithm for another card trick, possibly from this book, possibly from another. Or if they modify the algorithm, what effect does it have on the trick? What happens if the column containing the chosen card is always the first one picked up (and placed on the top of the pack) or always the column placed on the bottom? Can they draw it out as a Flowchart? Can they explain their result by describing things with Pseudocode?
An Intelligent Piece of paper
This longer article taken from AI: Where is the Intelligence? discusses Artificial Intelligence and rule following "bots". The activities contained within would easily lend themselves to a series of lessons on algorithms. The section on noughts and crosses, could start with students playing some games, and trying to analyse the patterns needed to win the game. They could then draw flowcharts of their versions and play them off against each other? What difference does it make if they go second? Can they design an algorithm to cope with this?