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.

DynamicProgrammingDivide andConquerGreedyAlgorithmsRandomizedAlgorithmsParallelAlgorithmsApproximationAlgorithmsBacktrackingOnlineAlgorithmsBranch andBound
Figure 1: The course map. Each arrow points from a topic to one that builds on it. The top row holds the design paradigms, the right side the hard problems, and the left side the other models of computation.

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.

Table 1: Connections on the map.
Topic (chapter)Builds onConnection
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 ConquerTake 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 ConquerDivide 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)BacktrackingBacktracking gains a bound: branches that cannot contain the best solution are pruned.
Approximation Algorithms (6)Greedy Algorithms, BacktrackingSolutions with a proven ratio for NP-hard problems: the MST-based 2-approximation, LPT, vertex cover.
Randomized Algorithms (7)Divide and ConquerQuicksort with a random pivot and QuickSelect; the Las Vegas and Monte Carlo types.
Online Algorithms (8)Greedy Algorithms, Approximation AlgorithmsDeciding without knowing the future: the competitive ratio is the online counterpart of the approximation ratio; paging.
Parallel Algorithms (9)Divide and ConquerIndependent 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.