OCR H446 2.3.1: Algorithms
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
- A4.3 Depth-first traversal Trees and graphs
Going deep and backtracking, recursively and with a stack; tracing it and what it is used for. - A4.4 Breadth-first traversal Trees and graphs
Level by level with a queue, shortest paths in unweighted graphs, and a breadth-first visit of the mat's zones. - A4.7 Tree traversals Trees and graphs
Pre-order, in-order and post-order, the outline method, expression trees and what each traversal is for. - A4.8 Project: plan the route Trees and graphs
Model the mat as a graph, find the shortest route with breadth-first search, and drive it. - 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.8 A* search Algorithms and complexity
g, h and f, open and closed lists, admissible heuristics, tracing A*, and A* against Dijkstra on the mat's grid. - 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. - A6.6 Reverse Polish notation Theory of computation
Infix and postfix, converting both ways, evaluating RPN with a stack, and the shunting-yard algorithm. - A6.7 Limits of computation: tractable and intractable problems Theory of computation
How complexity and hardware limit computation, tractable and intractable problems, and a heuristic route for the robot. - A15.1 How your A level is assessed Exam preparation
The papers and the project for OCR H446, AQA 7517 and Eduqas A500QS, the assessment objectives, and a timing plan built with integer… - A15.3 Trace tables and hand-tracing Exam preparation
Tracing loops, recursion and Little Man Computer programs without slips, and a binary search that prints its own trace table. - A15.5 Writing algorithms and code in the exam Exam preparation
Planning before writing, how code is marked, the standard algorithms to know by heart, and Dijkstra's algorithm driving the robot. - A15.7 Calculation and theory questions Exam preparation
Number representation, floating point, Boolean logic, state machines and complexity answered quickly and checked. - A15.8 A revision plan and mixed practice Exam preparation
Mapping the specification, retrieval, spacing and interleaving, and a spaced repetition scheduler for the whole course.
Try it on a robot
The task from A4.3 Depth-first traversal, running here. Change the program and press Run.
The specification is OCR's own document; this page says which of our lessons teach point 2.3.1 and is not endorsed by the board.