Module 1: Algorithm Analysis & Design Paradigms

Primary text: The Algorithm Design Manual (Skiena)
Selective support: Introduction to Algorithms (CLRS) for proofs and rigor, Algorithms (Sedgewick) for implementation views, Grokking Algorithms for accessible alternates, Competitive Programming (Halim) for exercise volume

This guide is the primary teacher. You do not need to read the source books front-to-back to complete this module. You do need to become operationally strong at asymptotic analysis, correctness reasoning, and paradigm selection before moving into data structures and graph algorithms.

---

Scope of This Module

This module is not a catalog of algorithms. It is where algorithmic reasoning becomes something you can defend.

What it covers in depth:

• Big-O, Omega, Theta as dominance relations and how to prove bounds
• analyzing loops, nested loops, and summations into closed-form complexity
• recurrence solution by substitution, recursion tree, and Master Theorem
• amortized analysis via aggregate, accounting, and potential methods
• loop invariants and iterative correctness proofs
• strong induction for recursive correctness, together with termination arguments
• brute force as a baseline, divide-and-conquer as a template, greedy with exchange arguments, backtracking with pruning
• dynamic programming: optimal substructure, overlapping subproblems, memoization vs tabulation, greedy-vs-DP discrimination
• testing and debugging discipline for algorithmic code
• reasoning about constants, cache behavior, and practical versus theoretical cost
• paradigm triage given a new problem with unknown structure

What it deliberately does not try to finish here:

• specific sort, heap, hash, or graph algorithms (Module 2 and Module 3)
• advanced DP variants like bitmask, digit, and SOS DP (Module 4)
• amortized data structures like splay trees or Fibonacci heaps (Module 5)
• advanced graph algorithms (Module 3)

This is the analytical foundation that Modules 2-5 rely on.

---

Before You Start

Answer these closed-book before starting the main path:

1. What does f(n) = O(g(n)) mean formally, and why do we need both a constant c and a threshold n0?
2. Given a doubly nested loop for i in range(n): for j in range(i): ..., why is the total work Theta(n^2) rather than Theta(n^3) or Theta(n)?
3. What is the difference between proving an algorithm correct by induction and proving it correct by testing?
4. Given T(n) = 2 T(n/2) + n, can you name the growth class without looking it up?
5. Why do some optimization problems admit a greedy solution while others need dynamic programming?

Diagnostic Interpretation

4-5 solid answers

• You are ready for the full path.

2-3 solid answers

• Continue, but expect extra time in the recurrences cluster and the greedy-vs-DP cluster.

0-1 solid answers

• Revisit Semester 1 Module 1 (proofs) and Module 3 (probability and expectation) briefly. Those modules built the induction and summation habits this module assumes.

---

What This Module Is For

Algorithm analysis is the language in which later engineering claims are made precise. Throughout the program you will repeatedly be asked:

• will this scale to n = 10^6? n = 10^9?
• can I prove this is correct without running a million tests?
• given a new problem, which paradigm applies, and why?
• when does constant-factor performance dominate theoretical complexity?

This module builds the analytical reasoning needed for:

• sorting, hashing, heaps, trees (Module 2)
• graph algorithms and their correctness (Module 3)
• dynamic programming at scale (Module 4)
• advanced data structures and amortized analysis (Module 5)
• systems work where complexity analysis meets cache, memory, and distribution

You are learning to think about algorithms without handwaving.

---

Concept Map

---

How To Use This Module

Work in order. The later clusters only make sense if the earlier analytical habits are stable.

Cluster 1: Asymptotic Analysis and Mathematical Foundations

Order	Concept	Type	Focus
1	Big-O, Omega, and Theta Bound Growth, Not Time	PRIMARY	Formal definitions and how to prove bounds with constants
2	Loops and Summations Turn Code Into a Sum	PRIMARY	Translating iterative code into summations and evaluating them
3	Recurrences: Substitution, Recursion Tree, Master Theorem	PRIMARY	Three techniques for solving recursive complexity
4	Amortized Analysis: Aggregate, Accounting, Potential	SUPPORTING	Average cost per operation over worst-case sequences

Cluster mastery check: Can you take an unfamiliar algorithm's pseudocode and produce a tight Theta bound with a written justification?

Cluster 2: Algorithm Correctness and Termination

Order	Concept	Type	Focus
5	Loop Invariants Prove What the Loop Maintains	PRIMARY	Initialization, maintenance, termination argument for loops
6	Recursive Correctness by Strong Induction	PRIMARY	Base case, inductive step, lemmas for non-recursive work
7	Termination Needs a Decreasing Measure	SUPPORTING	Variants, well-founded orderings, and lexicographic measures

Cluster mastery check: Can you state a loop invariant or induction hypothesis before writing the code, and can you show termination without handwaving?

Cluster 3: Design Paradigms - Search, Divide-and-Conquer, Greedy

Order	Concept	Type	Focus
8	Brute Force Is a Baseline, Not an Insult	SUPPORTING	Systematic enumeration as the default and as an oracle
9	Divide-and-Conquer: Split, Solve, Combine	PRIMARY	Independent subproblems, combine step, recurrence
10	Greedy Needs an Exchange Argument	PRIMARY	Greedy-choice property and optimality proofs
11	Backtracking Is Pruned Enumeration	SUPPORTING	Extend, check, undo, and feasibility pruning

Cluster mastery check: Can you pick a paradigm for a new problem and justify the choice with either a recurrence, an exchange argument, or a pruning argument?

Cluster 4: Dynamic Programming as a Paradigm

Order	Concept	Type	Focus
12	Optimal Substructure and Overlapping Subproblems	PRIMARY	The two properties that make DP applicable
13	Memoization Versus Tabulation	PRIMARY	Top-down caching vs bottom-up table fill, space optimization
14	Greedy Versus DP: When Each Is Justified	SUPPORTING	Discriminating paradigms with similar-looking inputs

Cluster mastery check: Given a new optimization problem, can you state the DP state and recurrence, and can you say why greedy does or does not apply?

Cluster 5: Analysis in Practice and Strategy Selection

Order	Concept	Type	Focus
15	Testing Beyond the Given Examples	SUPPORTING	Edge cases, stress testing, property-based checks
16	Debugging Complex Algorithms Systematically	PRIMARY	Minimal failing input, invariants, first divergence
17	Constants, Cache, and Practical Versus Theoretical	SUPPORTING	Why small n and memory layout change which algorithm wins
18	Choosing a Paradigm by Problem Structure	PRIMARY	A triage procedure for selecting paradigms under constraints

Cluster mastery check: Can you pick up a new problem, run the triage checklist, select a paradigm, and defend the choice in one paragraph?

Then work these practice pages:

Order	Practice path	Focus
1	Complexity Analysis Workshop	Asymptotic definitions, loop and recurrence drills, amortized arguments
2	Algorithm Correctness Lab	Loop invariants, induction proofs, termination measures
3	Design Paradigm Clinic	Paradigm classification, exchange arguments, DP state design
4	Code Katas	Timed implementation drills across every paradigm

Use Module Quiz after the concept and practice path. Use Reference and Selective Reading and Learning Resources only for targeted reinforcement.

---

Learning Objectives

By the end of this module you should be able to:

1. Prove f(n) = O(g(n)), Omega(g(n)), or Theta(g(n)) with explicit constants, and distinguish these from statements about wall-clock time.
2. Analyze iterative code by translating it into a summation and evaluating the sum in closed form.
3. Solve divide-and-conquer recurrences using substitution, recursion tree, and the Master Theorem.
4. Apply aggregate, accounting, and potential methods to bound amortized cost.
5. Prove iterative correctness using loop invariants and recursive correctness using strong induction.
6. Give a termination argument using a well-founded variant for any terminating algorithm you write.
7. Distinguish brute force, divide-and-conquer, greedy, backtracking, and dynamic programming, and select the correct one for a given problem.
8. Prove a greedy algorithm optimal by exchange argument or refute a proposed greedy with a counterexample.
9. Design a DP by stating the state, the recurrence, base cases, and the resulting runtime, and implement it both top-down and bottom-up.
10. Debug an algorithm systematically using minimal failing inputs and invariant checks, and justify algorithm choice against constants and cache behavior in addition to asymptotic cost.

---

Outputs

• an algorithm-analysis notebook with at least 25 worked complexity analyses (iterative, recursive, amortized)
• a correctness sheet with at least 8 loop-invariant proofs and 8 recursive-induction proofs
• a paradigm triage log: for each of at least 15 problems, record the classification, chosen paradigm, and a one-paragraph justification
• a stress-test harness: brute-force oracle plus random generator paired with at least 6 optimized implementations
• a DP catalog with state, recurrence, base cases, and both top-down and bottom-up code for at least 8 problems
• a debugging log naming at least 12 recurring mistakes (off-by-one base case, wrong DP state, greedy without exchange proof, stale cache, integer overflow, etc.)
• a short memo on constants and cache with at least two benchmarks you ran yourself
• a mistake journal of algorithmic intuition errors that you want your future self not to repeat
• a short write-up relating Module 1 analysis habits to the data-structure, graph, DP, and advanced-structure modules ahead

---

Completion Standard

You have completed Module 1 when all of these are true:

• you can classify an algorithm's complexity before running it
• you can state a loop invariant or induction hypothesis before writing the code, not after
• you can give a termination argument for any algorithm you implement
• you can pick a paradigm in minutes and defend the choice in one paragraph
• you can convert a DP recurrence into both top-down and bottom-up code without reference
• you have caught at least one real bug with a stress-test comparison against a brute-force oracle
• you can explain at least one case where constants or cache change which algorithm wins in practice

If the algorithm "works on the samples" but you cannot prove it correct and cannot bound its runtime, the module is not complete.

---

Reading Policy

• Concept pages are the main path.
• Local book chunks are selective reinforcement, not a second syllabus.
• Read only if stuck means try the concept page, self-check, and drill first.
• Optional deep dive means additional nuance or exercise volume, not required progression.
• Because this is the foundation for the rest of Semester 2, written analyses and proof sketches are required, not optional enrichment.

---

Suggested Weekly Flow

Day	Work
1	Concepts 1-2, one loop-analysis drill sheet
2	Concepts 3-4, solve at least 6 recurrences by hand
3	Concepts 5-7, write two loop-invariant proofs and two induction proofs
4	Concepts 8-9, implement brute-force + D&C solutions for two problems
5	Concepts 10-11, prove one greedy by exchange, refute another with a counterexample
6	Concepts 12-13, implement one DP both top-down and bottom-up
7	Concept 14 and Practice 1 + 2
8	Concepts 15-16 and Practice 3, including stress-test harness
9	Concepts 17-18, write paradigm triage for five unfamiliar problems
10	Practice 4 (code katas), quiz, mistake-log cleanup

---

Reference

If you need exact links into the local chunked books, use Reference and Selective Reading.

---

Rich Learning Pages

Worked Examples | Guided Labs | Case Studies | Mistake Clinic | Reading Guide | Capstone Thread