Algorithms and complexity
Comparing algorithms by time and space, the maths behind Big O, then searching and sorting analysed in depth, Dijkstra's shortest path and A*, finishing with BugBot planning the shortest route across the mat and driving it.
Start in the simulator- A5.1 Comparing algorithms Time and space efficiency as functions of the size of the problem; linear, polynomial, exponential and logarithmic…
- A5.2 Big O notation Dominant terms, the orders of complexity from O(1) to O(2^n), deriving complexity from code, best, average and worst…
- A5.3 Linear and binary search 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 Tracing passes and insertions, counting comparisons in the best and worst case, in-place sorting and stability.
- A5.5 Merge sort 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 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 Tracing Dijkstra's algorithm in a table, why negative weights break it, a priority queue version, its efficiency and…
- A5.8 A* search 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 Choose and justify a route planner, build the mat's graph, find the shortest route with Dijkstra's algorithm and drive…