Algorithms from zero
Graphs: free-recall review
Retrieval beats re-reading. For each prompt, say or write a full answer from memory before you open the model answer — the effort of recall is what makes the material stick.
Reconstruct the unit’s core mechanisms — representation tradeoffs, BFS vs DFS, topological sort, Dijkstra’s settle invariant, and union-find’s amortized bound — without looking back at the lessons.
- 01When do you choose an adjacency list over an adjacency matrix, and what does each cost?
- 02BFS and DFS both run in O(V + E). When does the order matter, and what does each give you?
- 03What is a topological order, when does it exist, and how do the two algorithms detect a cycle?
- 04State Dijkstra's settle invariant and explain exactly why it fails with a negative edge.
- 05Why is union-find's amortized cost O(alpha(n)) and not true O(1) or O(log n)?
- 06Connected components can be found with BFS/DFS or with union-find. When do you reach for each?
If you could reconstruct each answer from memory, you hold the unit’s spine: representation tradeoffs (list for sparse, matrix for dense or O(1) lookup), BFS for fewest-edge paths and DFS for depth and ordering, topological sort with built-in cycle detection, Dijkstra’s settle invariant and why non-negative weights are mandatory, and union-find’s amortized O(alpha(n)) for dynamic connectivity. The recurring lesson is to match the algorithm to the problem’s shape before coding.