Learning Resources
This module is populated from the local chunked books in library/raw/semester-02-algorithms/books. Use this page as a source map, not as an instruction to read everything.
Source Stack
| Book | Role | How to use it in this module |
|---|---|---|
| The Algorithm Design Manual (Skiena) | Primary / problem-driven | Default escalation for modeling, recognition, and "which algorithm fits this problem" |
| Introduction to Algorithms (CLRS) | Reference / proofs and depth | Default escalation for correctness arguments, running-time derivations, and formal detail on flow and SCCs |
| Algorithms (Sedgewick) | Selective / implementation and visual intuition | Use when you want worked implementations or a different visual framing |
| Competitive Programming | Applied problems and tricks | Use when you want compact variants, tricks, and problem-shaped examples |
| Grokking Algorithms | Accessible intro | Use only to repair missing intuition on BFS or Dijkstra - do not rely on it for rigor |
Resource Map by Cluster
Cluster 1: Graph Models and Representations
| Need | Best local chunk | Why |
|---|---|---|
| what a graph is | ADM: Graph Traversal | Clean problem-first framing before any algorithm |
| flavors of graphs | ADM: Flavors of Graphs | Names every model dimension explicitly |
| list vs matrix | CLRS 20.1: Representations of Graphs | Best formal treatment of time/space tradeoffs |
| implementation side | Sedgewick: Elementary Graph Algorithms (Part 1) | Code-level reinforcement |
| problem recognition | ADM 6.6: Design Graphs, Not Algorithms | The whole module's modeling philosophy in one chunk |
| war-story modeling | ADM: Getting the Graph | Shows why the model choice dominates everything after |
Cluster 2: Graph Traversals
| Need | Best local chunk | Why |
|---|---|---|
| BFS definition and correctness | CLRS 20.2: Breadth-First Search | Clean invariant-level treatment |
| BFS applications | ADM 5.7: Applications of BFS | Shows BFS as a toolbox rather than one routine |
| DFS definition and timestamps | CLRS 20.3: Depth-First Search | Best formal treatment of d/f/edge types |
| DFS applications | ADM 5.9: Applications of DFS | Pulls articulation, bridges, topology into one view |
| topological sort | CLRS 20.4: Topological Sort | Shortest correct statement plus proof |
| SCC | CLRS 20.5: Strongly Connected Components | Kosaraju with proof |
| SCC (Tarjan variant) | Competitive Programming: SCC | Compact Tarjan-style implementation |
Cluster 3: Shortest Paths
| Need | Best local chunk | Why |
|---|---|---|
| variant overview | CP 4.4: Single-Source Shortest Paths | Fastest route to "which algorithm fits" |
| correctness framework | CLRS 22.5: Proofs of Shortest-Paths Properties | Core lemmas used by BFS, Dijkstra, Bellman-Ford |
| Dijkstra | CLRS 22.3: Dijkstra's Algorithm | Algorithm + correctness + running time in one place |
| Dijkstra intuition | ADM 6.3.1: Dijkstra | Problem-first framing |
| Dijkstra code walkthrough | Grokking: Dijkstra implementation | Minimal first-pass implementation |
| Bellman-Ford | CLRS 22.1: Bellman-Ford Algorithm | Best formal treatment |
| negative cycles | CP 4.4.4: SSSP with negative cycles | Compact detection patterns |
| Floyd-Warshall | CLRS 23.2: Floyd-Warshall Algorithm | DP view with clean pseudocode |
| APSP on sparse graphs | CLRS 23.3: Johnson's Algorithm | Necessary for sparse APSP with negative edges |
Cluster 4: Minimum Spanning Trees and Greedy on Graphs
| Need | Best local chunk | Why |
|---|---|---|
| MST framework | CLRS 21.1: Growing an MST | Cut and cycle properties with proofs |
| Kruskal and Prim | CLRS 21.2: Kruskal and Prim | Both algorithms together, same theoretical scaffold |
| Kruskal's applied view | ADM 6.1.2: Kruskal's Algorithm | Problem-first view |
| union-find | ADM 6.1.3: Union-Find | Concise but complete coverage including analysis |
| MST variants | ADM 6.1.4: Variations on MST | Bottleneck, Steiner, second-best |
| MST applications | ADM: Nothing But Nets war story | Shows the modeling step end-to-end |
Cluster 5: Network Flow and Matching
| Need | Best local chunk | Why |
|---|---|---|
| flow networks | CLRS 24.1: Flow Networks | Formal definition with capacities |
| Ford-Fulkerson method | CLRS 24.2: Ford-Fulkerson Method | The canonical source for residual graphs and augmenting paths |
| Edmonds-Karp | CLRS 24.2: Ford-Fulkerson (Part 3) | BFS-based polynomial bound |
| flow applications | ADM 6.5: Network Flows and Bipartite Matching | Best short survey of modeling tricks |
| Sedgewick overview | Sedgewick: Network Flow | Different exposition with implementation notes |
| bipartite matching | CLRS 24.3: Maximum Bipartite Matching | Clean reduction to flow |
| Hopcroft-Karp intuition | CLRS 25.1: Bipartite Matching Revisited | Phase structure and sqrt(V) bound |
| assignment / weighted matching | CLRS 25.3: Hungarian Algorithm | When bipartite matching needs weights |
External Resources (Validated)
Lecture Videos and Notes
- MIT 6.006 Spring 2020, Lecture 9: Breadth-First Search - lecture notes PDF - clean treatment of BFS as shortest paths on unweighted graphs.
- MIT 6.006 Spring 2020, Lecture 10: Depth-First Search - lecture page - follows naturally from the BFS lecture and introduces edge classification.
- MIT 6.006 Spring 2020, Lecture 11: Weighted Shortest Paths - lecture notes PDF - Dijkstra and relaxation framed via the triangle inequality.
- MIT 6.006 Fall 2011, Lecture 13: BFS (Erik Demaine) - YouTube - if you want a video presentation rather than notes.
- Stanford CS 161 (Virginia Williams / Roughgarden), Lecture 11: Dijkstra's Algorithm - lecture notes PDF - proof-forward treatment of Dijkstra.
- Stanford CS 161 Winter 2023, Lecture 15: Minimum Spanning Trees - lecture notes PDF - cut property + Kruskal and Prim.
- Stanford CS 161 course page - schedule - use for additional lecture-note PDFs covering Bellman-Ford and DP.
Reference Articles (cp-algorithms.com)
- Breadth-First Search - BFS with code, applications, and edge cases.
- 0-1 BFS - the deque-based generalization when weights are
{0, 1}. - Strongly Connected Components and Condensation - Kosaraju with condensation graph.
- Topological Sorting - DFS-based and Kahn's both covered.
- Dijkstra - finding shortest paths - dense-graph version with
O(|V|^2). - Dijkstra on sparse graphs - heap-based version with implementation notes.
- Bellman-Ford - with negative-weight handling.
- Finding a Negative Cycle in the Graph - the extraction step after detection.
- Floyd-Warshall - APSP with code.
- Minimum spanning tree - Kruskal - implementation and analysis.
- Minimum Spanning Tree - Prim - heap-based Prim.
- Maximum flow - Ford-Fulkerson and Edmonds-Karp - step-by-step with residual graph.
- Maximum flow - Dinic's algorithm - the step beyond Edmonds-Karp; optional deep dive.
- Kuhn's Algorithm - Maximum Bipartite Matching - augmenting-path matching in its simplest form.
Reference Textbook (Online)
- Sedgewick & Wayne, "Algorithms, 4th Edition" booksite - Graphs section and Undirected Graphs. Concise implementations in Java with commentary; useful as a second exposition.
Use Rules
- If the question is "which algorithm fits this problem," go to ADM first.
- If the question is "why is this algorithm correct, or how fast," go to CLRS first.
- If you want a compact implementation you can read straight through, use Sedgewick or cp-algorithms.com.
- Open one chunk for one concept gap; do not wander through a whole chapter by default.
- Watch videos only if reading is not working; the MIT lectures are the preferred fallback.
- Do not add extra resources unless the existing ones have demonstrably failed for a specific concept.