Algorithms
Computational thinking and algorithm design are two critical skills that A level students will develop during their studies. They will form a firm foundation for developing programs but also have wider benefits in the ability to solve problems in a logical and efficient manner.
Computational thinking
This is a cornerstone of Computer Science. Students need to learn how to use decomposition to break down large problems into smaller, more manageable tasks. They need to use pattern recognition to be able to identify parts of a solution that are repeated and abstraction to manage the complexity of the solution. Students should be able to solve problems in a structured, logical way through the application of computational thinking skills. They should be able to use techniques such as divide and conquer, backtracking, pipelining and heuristics.
Developing algorithms
Algorithms can be expressed as a flow diagram or pseudo-code. Students need to practise and become competent at both of these techniques. Examination boards often issue guidance on the expected format of pseudo-code but at its simplest level, it is a text-based sequence of instructions written in a language independent, structured way so that the required control structures are clear.
Algorithms for manipulating data structures
Students will need to know how to use algorithms to manipulate and maintain data in stacks, queues, linked lists and trees including binary trees. They need to be able to represent the algorithms as flowcharts and pseudo-code. Data structures are used for specific purposes for example, a stack is used to hold register values during an interrupt, a syntax tree is constructed during compilation and a queue is used to hold processes waiting to be executed by the CPU for example. Students should be able to apply their knowledge of data structures within the context of algorithms.
Searching and sorting algorithms
Knowledge of linear and binary searching algorithms are common to all A level specifications. Additionally, students should learn searching algorithms for trees including depth first and breadth first searching.
Students should learn a variety of sorting methods namely bubble, insertion, quick and merge sorts. They should recognise where recursion is used in an algorithm.
Comparing performance of algorithms
When choosing an algorithm, there are several considerations such as ease of coding, how quickly it will complete and how much memory is required. The efficiency of algorithms can be compared by analysing time and space complexity using Big O notation.
Path finding algorithms
Students should understand directed and undirected graph data structures. They should know how to traverse graphs by using a shortest path algorithm and heuristics. Dijkestra’s algorithm is the best known and is forms the computational basis of the Open Shortest Path First (OSPF) routing protocol. The A* algorithm has applications in computer games and data mining.
- ALL
- Teacher guidance
- External link
Teacher guidance
Create a Face
Although this activity is designed for younger students, however it is valuable and a popular activity when teaching the topic of algorithms. One particular problem of Computer Generated Imagery is the representation of human-like facial expressions. This activity explores how surprise, sadness and joy can be represented via eyes and mouth movements.
Computational thinking: Puzzling tours
This is a very comprehensive resource covering a range of pathfinding algorithm activities using graphs. It includes the Knight’s Tour puzzle as well as other examples. This is a highly readable resource that could be used for smaller activities including homework.
Big O Notation
This presentation covers algorithms and their complexity expressed as Big O notation. This could be used by students as a revision aid or as a basic introduction to the topic.
Algorithm efficiency
From a more mathematical perspective this time, this document covers the derivation of algorithm complexity. It could be used in the classroom as extension reading or as a homework.
Thinking abstractly
This resource from OCR provides teachers with a summary of A level coverage and common misconceptions. There are also a sequence of activities to allow students to develop their skills in applying abstraction. These include use of Venn diagram to consider object properties, a binary representation of an image and developing a currency converter program.
Thinking logically
Within this resource from OCR, students use their logical problem-solving skills to develop a cash register that will calculate required change. The task develops students’ logical thinking skills.They will also investigate Bayes’ theorem to calculate probabilities and learn the logic behind Sudoku puzzles. Within the exploration teacher guide, there are numerous informative links embedded that provide background information and useful resources for teaching.
Thinking concurrently
This set of activities from OCR illustrate the concept of concurrency in algorithm development. A teacher pack and learning activity packs are provided. Activities move from the familiar, division of labour when washing up, to the less familiar topic of writing programs using threading in Python. Routing and deadlock and the classic dining philosopher problem are covered.
External link
Computational techniques delivery guide
Several computational methods are covered within this delivery guide from OCR. Students will learn more about using divide and conquer, backtracking, data mining and visualisation in solving problems. The document also covers common misconceptions.
Computational methods exploration teacher guide
From eating biscuits to identifying different cakes and biscuits , this resource from OCR includes a number of engaging activities including the use of backtracking. There are a number of very useful links to other activities and useful information relating to the topic of computational methods.
