Sequence 13 — Advanced Algorithms

BFS, DFS, iterative tree traversal, Reverse Polish Notation, searching algorithm selection, merge sort and Dijkstra's algorithm — with explicit reasoning about correctness. AQA 4.3.1–4.3.9.

Retrieval: Searching and Sorting Algorithms

  • Recall Linear Search, Binary Search, Bubble Sort and Insertion Sort from Year 12
  • Recall Big-O complexity analysis and apply it comparatively across algorithms
Lesson ready

Graph Traversal Algorithms (BFS & DFS)

  • Explain and compare Breadth-First Search and Depth-First Search
  • Understand how queues and stacks determine traversal behaviour
Lesson ready

Iterative Tree Traversal

  • Implement pre-order and in-order tree traversal iteratively, using an explicit stack
  • Explain why the stack-based ordering correctly reproduces the recursive traversal order
Lesson ready

Reverse Polish (Postfix) Notation

  • Convert between infix and postfix notation
  • Evaluate postfix expressions using a stack
Lesson ready

Comparing and Selecting Searching Algorithms

  • Compare Linear Search, Binary Search and Binary Search Tree search
  • Explain why Binary Search produces incorrect results on unsorted data
Lesson ready

Merge Sort

  • Explain the divide-and-conquer strategy behind merge sort
  • Implement merge sort, including the merge step
Lesson ready

Dijkstra's Shortest Path Algorithm

  • Trace and implement Dijkstra's algorithm on a weighted graph
  • Explain why Dijkstra's algorithm relies on non-negative edge weights
Lesson ready