Advanced Algorithms
Course Map
This page puts every chapter of the course on one map. Each chapter is a node, and an arrow shows which idea from an earlier topic the next one relies on. Read it before the course starts to see where the topics are heading, or during the course to see where you are.
Figure 1 draws only the most direct connections. Table 1 lists every chapter that each chapter depends on, together with the idea that links them.
| Topic (chapter) | Builds on | Connection |
|---|---|---|
| Divide and Conquer (1) | — | The common template of merge sort and quicksort; recurrence relations and the Master Theorem (Algorithms, Chapters 2–3). |
| Greedy Algorithms (2) | Divide and Conquer | Take the choice that looks best at each step; Prim, Kruskal, and Dijkstra are greedy graph algorithms (Algorithms, Chapters 6–7). |
| Dynamic Programming (3) | Divide and Conquer | Divide and conquer with overlapping subproblems: memoization and tabulation; LCS and edit distance on strings (Algorithms, Chapter 10). |
| Backtracking (4) | — | Depth-first search of the state-space tree (Algorithms, Chapter 5); an introduction to P, NP, and NP-hard problems. |
| Branch and Bound (5) | Backtracking | Backtracking gains a bound: branches that cannot contain the best solution are pruned. |
| Approximation Algorithms (6) | Greedy Algorithms, Backtracking | Solutions with a proven ratio for NP-hard problems: the MST-based 2-approximation, LPT, vertex cover. |
| Randomized Algorithms (7) | Divide and Conquer | Quicksort with a random pivot and QuickSelect; the Las Vegas and Monte Carlo types. |
| Online Algorithms (8) | Greedy Algorithms, Approximation Algorithms | Deciding without knowing the future: the competitive ratio is the online counterpart of the approximation ratio; paging. |
| Parallel Algorithms (9) | Divide and Conquer | Independent subproblems are solved in parallel: prefix sums, parallel merge sort, work and depth. |
The backbone of the map can be read as design paradigms → hard problems → other models. The course builds on the analysis, sorting, searching, graph, and string algorithms of the Algorithms course. Divide and conquer grows out of sorting and opens onto dynamic programming and onto randomized and parallel algorithms. The greedy method is familiar from graph algorithms. Backtracking and branch and bound search for the best solution in exponential time; approximation algorithms settle instead for a proven ratio. Online algorithms apply the same idea of a ratio to an unknown future.
Course page: Advanced Algorithms · Glossary · © Sercan Külcü. All rights reserved.