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

Complete the prerequisite diagnostic: loop tracing, indexing, subsets, induction, and proof versus testing. These come from earlier programming and mathematics modules. Big-O, recurrences, and greedy/DP selection are taught here, so they are not entry requirements.

Use the assessment map to see the required evidence. Code and proofs are assessed together; no percentage implies an elite population ranking.

---

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 and Completion Standard

• Written attempts for 15 practice problems, corrections, and changed cases for missed concepts.
• Four learner lab functions, passing public checks, a reproducible report, and completed evidence template.
• Both memoized and tabulated coin change from practice C4, with state and dependency reasoning.
• A measurement/proof memo and an independent seven-competency assessment, followed by a delayed changed-case recheck.

The rubric requires each competency to pass. The instructor guide separates authored, executed, externally reviewed, and piloted status. This finite exercise sequence replaces earlier arbitrary counts of proofs, implementations, and notebook entries.

---

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 Study Sequence

Allow roughly 45–65 focused hours, around 5–7 weeks at ten hours per week. These are author estimates awaiting learner pilots, not a ten-day deadline. Independent prerequisite repair and optional deep reading may add time.

Phase	Work	Hours
Entry	Diagnostic and focused repair	2–4
Analysis	Concepts1–4, examples 1–3, practice A	8–12
Correctness	Concepts5–7, example4, practice B	7–10
Design	Concepts8–14, examples 5–6, practice C	10–14
Executable work	Labs A–D, interleaved with the matching lessons	9–11
Evidence and assessment	Concepts15–18, measurement memo, assessment, repair, recheck	9–14

The 3–7-day retention delay is calendar time, not extra focused hours. Begin with worked examples, use the downloadable labs, and consult the reading guide for targeted reinforcement.

---

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