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 teaching source | Default escalation for asymptotic intuition, paradigm selection, and war-story debugging lessons |
| Introduction to Algorithms (CLRS) | Selective support for rigor | Use for formal asymptotic definitions, the Master Theorem, loop-invariant-style correctness proofs, greedy and DP elements, and amortized analysis |
| Algorithms (Sedgewick) | Selective support for implementation | Open when you want a second implementation perspective on mergesort, quicksort, priority queues (mostly Module 2 content); rarely needed in Module 1 |
| Grokking Algorithms (Bhargava) | Accessible alternate explanation | Use when a concept page lands too tersely; it trades rigor for intuition |
| Competitive Programming (Halim) | Exercise support and problem triage | Use for paradigm-classification practice and for its many worked problems |
Resource Map by Cluster
Cluster 1: Asymptotic Analysis and Mathematical Foundations
| Need | Best local chunk | Why |
|---|---|---|
| formal big-O definition | CLRS: Asymptotic notation, formal definitions | Cleanest formal presentation with worked proofs |
| intuitive big-O | Skiena: Big-Oh notation | Best first pass before CLRS rigor |
| growth rate ordering | Skiena: Growth rates and dominance relations | Useful hierarchy and intuitive comparisons |
| loop analysis and summations | Skiena: Logarithms and summations | Summation techniques applied to algorithm analysis |
| iterative analysis worked example | CLRS: Analyzing algorithms (insertion sort) | Full step-by-step counting example |
| substitution method | CLRS: Substitution method for recurrences | Formal induction-based technique |
| recursion tree method | CLRS: Recursion tree method | Visual approach when Master Theorem does not apply |
| Master Theorem | CLRS: Master method | Canonical reference for the three cases |
| D&C recurrences in context | Skiena: Solving divide-and-conquer recurrences | Skiena's accessible view of D&C recurrences |
| amortized - aggregate | CLRS: Aggregate analysis | Simplest amortized method |
| amortized - accounting | CLRS: The accounting method | Credit-based intuition |
| amortized - potential | CLRS: The potential method | Strongest amortized technique |
| amortized - dynamic arrays | CLRS: Dynamic tables | The canonical worked example |
Cluster 2: Algorithm Correctness and Termination
| Need | Best local chunk | Why |
|---|---|---|
| loop invariant worked example | CLRS: Insertion sort | The canonical loop-invariant proof |
| correctness discipline | CLRS: Analyzing algorithms | Shows analysis alongside correctness |
| induction for recursion | Skiena: Induction and recursion | Natural bridge between induction and recursive algorithms |
| induction worked proof | Skiena: Prove sum i = n(n+1)/2 by induction | Reinforces the proof mechanics |
| recursive objects framing | Skiena: Recursive objects | Useful for thinking recursively about data |
| termination in D&C context | CLRS: Designing algorithms | Worked D&C example including termination |
Cluster 3: Design Paradigms - Search, Divide-and-Conquer, Greedy
| Need | Best local chunk | Why |
|---|---|---|
| brute force framing | Skiena: Selecting the right jobs | Shows brute force as the first step in design |
| systematic enumeration | Skiena: Constructing all permutations | Canonical example of exhaustive generation |
| complete search | Competitive Programming: Complete search | Contest-oriented brute force with sizing advice |
| recursive brute force | Competitive Programming: Recursive complete search | Good template for backtracking-style enumeration |
| D&C template | Skiena: Divide and conquer | Best operational introduction |
| D&C worked example (mergesort) | Skiena: Mergesort | Canonical D&C algorithm in context |
| D&C design | CLRS: Designing algorithms | Rigorous D&C template |
| D&C alternate exposition | Competitive Programming: Divide and conquer | Contest perspective, different examples |
| activity selection greedy | CLRS: Activity-selection problem | Canonical greedy with exchange proof |
| elements of greedy | CLRS: Elements of the greedy strategy | General framework for greedy correctness |
| greedy worked examples | CLRS: Huffman codes | Non-trivial greedy with proof |
| greedy patterns | Competitive Programming: Greedy | Common greedy patterns with sample problems |
| backtracking | Skiena: Backtracking | Extend / check / undo framing |
| pruning | Skiena: Search pruning | How to kill subtrees you do not need to search |
| backtracking worked example | Skiena: Sudoku | Real case study of aggressive pruning |
Cluster 4: Dynamic Programming as a Paradigm
| Need | Best local chunk | Why |
|---|---|---|
| why naive recursion fails | Skiena: Fibonacci by recursion | Shows exponential blowup motivating DP |
| memoization fix | Skiena: Fibonacci by caching | Direct top-down cure |
| DP canonical example | CLRS: Rod cutting | Both top-down and bottom-up implementations |
| elements of DP | CLRS: Elements of dynamic programming | Optimal substructure and overlapping subproblems formally |
| DP illustration | Competitive Programming: DP illustration | Walks through state/recurrence/transition |
| DP vs greedy tension | CLRS: Offline caching (greedy vs DP) | Same problem space where paradigm choice matters |
| limits of DP | Skiena: Limitations of dynamic programming | Where DP state explodes (TSP etc.) |
| accessible DP intro | Grokking: Dynamic programming (Part 1) | Alternate low-friction explanation |
Cluster 5: Analysis in Practice and Strategy Selection
| Need | Best local chunk | Why |
|---|---|---|
| testing discipline | Competitive Programming: Master the art of testing code | Practical testing heuristics under pressure |
| debugging under pressure | Skiena: War story - Hard against the clock | Realistic failure mode and recovery |
| debugging lesson | Skiena: War story - And then I failed | How small mistakes cascade |
| implementation bug narrative | Skiena: War story - Give me a ticket on an airplane | Real bug, real fix |
| another bug narrative | Skiena: War story - Skiena for the defense | Illustrates correctness-vs-testing tension |
| RAM model | Skiena: The RAM model of computation | Why asymptotic cost is an idealization |
| constants matter | Skiena: Reasoning about efficiency | Practical vs theoretical performance |
| growth hierarchy review | Skiena: Esoteric functions | The less-common growth rates you still meet |
| algorithms as a technology | CLRS: Algorithms as a technology | Why algorithm choice pays off in practice |
| paradigm triage | Skiena: Modeling the problem | How to cast a messy problem into paradigm-ready form |
| paradigm selection review | Skiena: Chapter notes on algorithm design | Skiena's retrospective on paradigm selection |
| sizing & constraints | Competitive Programming: Do algorithm analysis | Short rule of thumb on n vs paradigm |
Exercise Support Chunks
Use these when concept pages are understood but fluency is weak:
- Skiena: Chapter 1 exercises
- Skiena: Chapter 2 exercises
- Skiena: Chapter 2 exercises (Part 2)
- Skiena: Chapter 4 exercises and chapter notes
- Skiena: Chapter 7 (backtracking) context
- Skiena: Chapter 8 exercises (DP)
- Skiena: Chapter 8 exercises (Part 2)
- Competitive Programming: Solutions to chapter 1 exercises
- Competitive Programming: DP classical examples
External Resources (Read-If-Curious)
Only use these if you want a second exposition or a supplementary problem source. The module is completable from the local chunks alone.
- MIT OCW 6.006 Fall 2011 - Lecture Notes - asymptotic complexity lectures and recitation notes.
- MIT OCW 6.046J Spring 2015 - Lecture Notes - design-and-analysis coverage of D&C, DP, greedy, amortized.
- Algorithms by Jeff Erickson (free PDF) - excellent alternate textbook, especially strong on induction, greedy, and DP.
- Competitive Programmer's Handbook (Laaksonen, free PDF) - compact reference for paradigm patterns plus many practice problems.
- VisuAlgo: Recursion and DP visualizer - step-by-step animations of recursion trees and memoization.
- CP Algorithms - catalog of named algorithms with correctness sketches and implementations; especially useful for D&C, DP, and greedy lookups.
- CMU 15-451 Algorithm Design and Analysis - Lecture Notes - rigorous notes on amortized analysis, randomized algorithms, and advanced DP.
- CMU 15-210 Parallel and Sequential Data Structures and Algorithms - loop-invariant-style correctness proofs with a parallel twist.
- Erik Demaine's 6.006 Spring 2020 lectures (video + notes) - Demaine's updated treatment of recurrences, DP, and amortization.
- Ulrich Drepper - What every programmer should know about memory (PDF) - definitive reference for cache behavior and constant-factor reasoning.
- Hypothesis docs - property-based testing library used in concept 15 drills.
Transfer Curriculum Pointers (within this module)
Every concept page now includes a Transfer / Where This Shows Up Later section. These are the curriculum anchors those sections reference:
- S1 M2 (Counting) - binomial identities, pigeonhole, generating functions underlying summation-based analysis.
- S1 M3 (Probability) - expected-case analysis, concentration bounds, randomized pivot selection.
- S1 M5 (Problem solving) - triage discipline reused in paradigm selection (concept 18).
- S4 (Systems) - cache-complexity, memory hierarchy, external-memory algorithms (concepts 1, 9, 13, 17).
- S5 (OS / scheduling) - fairness, queueing, amortized quantum accounting (concepts 4, 10, 14).
- S6 (Databases) - query-planner cost models, LSM compaction as amortized analysis, join algorithm triage (concepts 4, 14, 17, 18).
- S7 M5 (Architecture / ADRs) - fitness functions as asymptotic-plus-constants claims; paradigm triage as architectural decisions (concepts 1, 17, 18).
- S8 (Distributed systems) - capacity planning, tail-latency analysis, Amdahl-shaped constants atop asymptotic skeletons (concepts 1, 4, 17).
Use Rules
- If you are stuck on a complexity analysis, go to Skiena first (Cluster 1 chunks).
- If you need formal rigor or a clean proof template, go to CLRS.
- If you need an accessible second exposition, consult Grokking.
- If you need exercise volume or paradigm contest problems, use Competitive Programming.
- Open one chunk for one concept gap; do not wander through a whole chapter sequence by default.
- If rereading does not fix the problem, stop and rewrite the analysis in your own words before reading more.