Algorithms Illuminated (Part 3) (Tim Roughgarden)（Z-Library）

# Algorithms Illuminated (Part 3): Greedy Algorithms and Dynamic Programming — Reading Guide ## 【One-Line Pitch】 A clear, language-agnostic deep dive into two of computer science's most powerful algorithm design paradigms—greedy algorithms and dynamic programming—with rigorous proofs and practical applications, ideal for self-learners, students, and practitioners who want to move beyond memorizing algorithms to truly understanding why they work. ## 【Book Arc】 - **Opening (~0%–10%)**: Introduces the two core paradigms—greedy algorithms (myopic, irrevocable decisions) and dynamic programming (systematic problem decomposition)—and sets up the first case study: minimizing weighted sum of completion times in scheduling, establishing the "special cases → candidate algorithm → proof" methodology. - **Early (~10%–23%)**: Develops the scheduling problem fully, introducing the key insight that sorting jobs by weight-to-length ratio is optimal, and proves correctness via exchange arguments (swapping inverted job pairs). Transitions into Huffman codes for lossless compression. - **Early–Middle (~23%–39%)**: Covers Huffman coding in depth: fixed-length vs. variable-length prefix-free codes, the greedy forest-merging algorithm, its O(n log n) implementation, and a correctness proof blending induction with exchange arguments. Includes worked examples and chapter summaries. - **Middle (~39%–48%)**: Shifts to minimum spanning trees (MSTs), defining the problem precisely (acyclic, spanning edge subsets with minimum total cost), then introducing Prim's algorithm as the first MST solution, noting its resemblance to Dijkstra's shortest-path algorithm. - **Middle (~48%–end of excerpts)**: Analyzes Prim's algorithm implementations—naive O(mn) versus heap-based O((m+n) log n)—and frames MST as a "for-free primitive" (near-linear time), positioning it alongside sorting and shortest paths as a preprocessing tool worth using liberally. ## 【Key Takeaways】 - **Greedy algorithms are easy to devise but rarely correct** (Opening): The book's central warning—most greedy heuristics fail, but a few killer applications (scheduling, Huffman codes, MSTs) are provably optimal. The value is in learning which problems admit greedy solutions and how to prove correctness. - **The "special cases first" method is a repeatable design process** (Early): When developing a greedy algorithm, solve simplified versions (e.g., equal job lengths, equal weights) to intuit the right rule—here, scheduling by weight-to-length ratio. This methodology transfers to your own algorithm design problems. - **Exchange arguments prove greedy optimality** (Early): The scheduling proof works by showing any non-greedy schedule has an "inversion" (adjacent out-of-order jobs), and swapping such pairs only improves the objective. This technique—plus induction—recurs throughout the book, including in Huffman's correctness proof. - **Huffman codes achieve optimal lossless compression** (Early–Middle): By merging the two lowest-frequency symbols iteratively, Huffman's algorithm produces a prefix-free code with minimum average encoding length. The tree visualization (leaves = symbols, root-leaf paths = codewords) makes the problem geometrically intuitive. - **Prefix-free codes are binary trees** (Middle): The key conceptual bridge—any prefix-free code corresponds to a tree where average encoding length equals average leaf depth. This reframing turns a coding problem into a tree-optimization problem, enabling greedy and DP solutions. - **Minimum spanning trees are a "for-free primitive"** (Middle): With heap-based Prim running in O((m+n) log n)—near-linear time—MST computation is cheap enough to run as preprocessing even when you're unsure how it will help. This "stock your toolbox" philosophy encourages liberal use of fast algorithms. - **Prim's algorithm is Dijkstra's cousin** (Middle): The structural similarity to shortest-path algorithms (growing a tree from a start vertex, using a heap for efficiency) means mastery of one transfers to the other—a recurring theme of the book's interconnected treatment of graph algorithms. ## 【Reading Tips】 - **Deep-read the scheduling chapter (Chunk #4–7)**: The "special cases → candidate → proof" arc is the book's methodological core. Work through the exchange argument carefully; it's the template for all later correctness proofs. - **Skim the Huffman worked examples (Chunk #10–11)**: The larger example with six symbols is illustrative but mechanical. Focus instead on the proof structure (induction + exchange) and the tree visualization, which are the transferable insights. - **Pay attention to running-time analyses**: The book consistently pairs each algorithm with its complexity (e.g., O(n log n) for Huffman, O((m+n) log n) for heap-based Prim). These "for-free primitive" discussions are practical gold for real-world engineering decisions. - **Expect a proof-heavy middle section**: If you're primarily an applications-focused reader, you can skim the formal proofs on first pass and return to them later. The intuitive explanations and examples carry the practical content. - **Use the end-of-chapter problems**: The book includes hints/solutions and programming projects with test data at algorithmsilluminated.org—these are essential for converting passive understanding into working implementations. ## 【Coverage Limits】 This guide covers the greedy algorithms portion (scheduling, Huffman codes, MSTs/Prim) in detail from the excerpts. The dynamic programming half of the book (knapsack, sequence alignment, shortest paths, optimal search trees) is mentioned in the preface but not covered in the sampled material—expect a separate treatment there. ##