Eduqas A500QS 1.3: Algorithms and programs
The free BugBot lessons that teach this point, a robot to try it on, and the past-paper questions that test it.
Lessons that teach it
- A2.2 Recursion Recursion and computational thinking
Base case and general case, winding and unwinding, and a spiral the robot draws by calling itself. - A2.3 Recursion versus iteration Recursion and computational thinking
The same algorithm both ways, the cost of a frame per call, repeated work, and stack overflow. - A2.9 Computational methods Recursion and computational thinking
Problem recognition, divide and conquer, backtracking, heuristics, performance modelling, data mining and visualisation. - A2.10 Project: out of the dead end Recursion and computational thinking
Model a maze, solve it by recursive backtracking, and drive the robot out along the route. - A5.1 Comparing algorithms Algorithms and complexity
Time and space efficiency as functions of the size of the problem; linear, polynomial, exponential and logarithmic functions; permutations… - A5.2 Big O notation Algorithms and complexity
Dominant terms, the orders of complexity from O(1) to O(2^n), deriving complexity from code, best, average and worst case, and space… - A5.3 Linear and binary search Algorithms and complexity
Tracing both searches in pseudocode, recursive binary search, O(n) against O(log n), and when sorting first pays off. - A5.4 Bubble sort and insertion sort Algorithms and complexity
Tracing passes and insertions, counting comparisons in the best and worst case, in-place sorting and stability. - A5.5 Merge sort Algorithms and complexity
Divide and conquer, a recursive merge sort, why it is O(n log n) in every case, and its O(n) memory cost. - A5.6 Quick sort Algorithms and complexity
Pivots and in-place partitioning, O(n log n) on average and O(n^2) at worst, and the four sorts compared. - A5.7 Dijkstra's shortest path algorithm Algorithms and complexity
Tracing Dijkstra's algorithm in a table, why negative weights break it, a priority queue version, its efficiency and applications. - A5.9 Project: plan the route, then drive it Algorithms and complexity
Choose and justify a route planner, build the mat's graph, find the shortest route with Dijkstra's algorithm and drive it.
Try it on a robot
The task from A2.2 Recursion, running here. Change the program and press Run.
The specification is Eduqas's own document; this page says which of our lessons teach point 1.3 and is not endorsed by the board.