Advanced Algorithms: Sorting, Graphs, and Dynamic Programming

Lesson Promise

By the end of this lesson, you will understand how merge sort divides and conquers in O(n log n), how BFS and DFS traverse graphs through adjacency lists, and how dynamic programming turns exponential recursion into linear or polynomial time.

Narration Draft

Part 1 — Sorting and Binary Search (6:00) Review binary search on a sorted array: O(log n) by halving the search space each step. Then show merge sort: recursively split the array in half, sort each half, merge back. Trace the division producing single-element arrays, then the merge rebuilding sorted arrays.

Part 2 — Hash Tables and Trees (5:00) Recap hash table collision handling. Trace a hash table lookup through a collision chain. Then review tree traversals — inorder, preorder, postorder — and how recursion naturally maps to tree structure.

Part 3 — Graph Traversal (7:00) A graph is a set of nodes with edges between them. Show adjacency list representation. Trace BFS using a queue (level-order): visit node, enqueue neighbors. Trace DFS using a stack (recursive): visit node, recurse into unvisited neighbor.

Part 4 — Dynamic Programming (7:00) Dynamic programming solves problems with overlapping subproblems by caching results. Start with the climbing stairs problem: ways(n) = ways(n-1) + ways(n-2). Show the naive recursive tree (exponential), then the memoized version (O(n)), then the bottom-up version. Trace the computation table filling left to right.

Part 5 — Common Patterns (5:00) Sliding window, two pointers, prefix sums, union-find. Show how each pattern applies to its canonical problem.

Visual Sequence

1. Binary search: highlight the shrinking search window halving each step
2. Merge sort: divide tree showing 8 → 4 → 2 → 1, then merge animations
3. BFS on a graph: queue animation, level-by-level node discovery
4. DFS on a graph: recursive descent, stack unwinding, backtracking
5. DP table: climbing stairs, show the table filling left to right

Companion Material

• Article: Searching and Sorting
• Trace: Searching and Sorting
• Practice: Binary Search
• Article: Graph Algorithms
• Trace: Graph Algorithms
• Practice: Number of Islands
• Practice: Climbing Stairs
• Practice: Coin Change