Design and Analysis of Algorithms I
An introduction to the design and analysis of algorithms. Topics include: divide-and-conquer, dynamic programming, linear programming, greedy algorithms, graph algorithms, NP-completeness.
Study notes
Independent, AI-drafted study guide · Public sources linked below · Added November 5, 2026
Original guide aligned to the public Fall 2026 outline. The outline identifies course topics; explanations and exercises are independently written.
Specify the problem before choosing a technique
An algorithmic solution needs a precise input/output contract, a correctness argument, and a complexity analysis under a stated model. A few successful examples do not prove correctness. Loop invariants describe what remains true before and after each iteration; induction supports recursive algorithms. Distinguish worst-case, expected, and amortized bounds. An O(n log n) upper bound can also be true of a linear-time algorithm, so use a tight bound when the argument establishes one.
References: Jeff Erickson — Algorithms, free author text and notes
Divide-and-conquer and recurrences
Divide-and-conquer splits a problem into smaller instances, solves them, and combines their answers. Merge sort yields T(n)=2T(n/2)+Theta(n), so each recursion level contributes Theta(n) across Theta(log n) levels. A recurrence must include the number and size of subproblems and all nonrecursive work. Master-theorem cases apply only when their conditions hold; otherwise use a recursion tree, substitution, or another suitable tool. Account for rounding and base cases without letting them obscure asymptotic behavior.
References: Jeff Erickson — Algorithms, free author text and notes
Dynamic programming and a worked recurrence
Dynamic programming reuses answers to overlapping subproblems. Define the state in words, derive the recurrence from the final decision, state base cases, and choose an evaluation order respecting dependencies. For coin values 1, 3, and 4, define D[x] as the fewest coins totaling x. Set D[0]=0 and D[x]=1+min D[x-c] over valid coins. Then D[6]=2 using 3+3, while a largest-coin-first greedy rule takes 4+1+1 and uses three coins.
References: Jeff Erickson — Algorithms, free author text and notes
Greedy algorithms require a structural reason
A greedy algorithm commits to a locally attractive choice. Prove that some optimal solution can include that choice, often through an exchange argument, then solve the remaining problem. Earliest-finish interval scheduling works because replacing an optimal solution's first interval with one finishing no later leaves at least as much room afterward. A superficially similar rule can fail on a different objective, such as weighted scheduling. State the exact optimization problem before transferring a known greedy argument.
References: Jeff Erickson — Algorithms, free author text and notes
Graph algorithms and optimization models
Choose a representation matching the operations: adjacency lists support scanning sparse neighborhoods, while matrices provide direct edge queries at quadratic storage cost. Breadth-first search solves unweighted shortest paths. Dijkstra's usual correctness proof requires nonnegative edge weights; Bellman-Ford handles negative edges and can expose reachable negative cycles. A minimum spanning tree minimizes total connection cost, not source-to-vertex path lengths. Linear programming expresses linear objectives and constraints, but a fractional optimum may not satisfy an integer problem.
References: Jeff Erickson — Algorithms, free author text and notes
NP-completeness and direction of reductions
NP contains decision problems whose yes instances have certificates verifiable in polynomial time. To show a target problem is NP-hard, reduce a known hard problem to that target: a target solver would then solve the known problem. Reversing the direction establishes a different claim. Proving NP-completeness also requires membership in NP. A reduction must construct the new instance efficiently and prove both directions of the yes/no equivalence. Optimization and decision versions require an explicit relationship.
References: Jeff Erickson — Algorithms, free author text and notes
Practice & worked answers
Original exercises for this guide.
1. Why does storing D[x] alone suffice for the coin-count problem?
Show worked answer
After fixing the remaining total, earlier coin choices do not restrict future choices when supply is unlimited. The subproblem is fully described by x. If each coin type had a limited remaining supply, the state would need additional information.
2. To establish that problem B is NP-hard using known NP-hard A, which direction is required?
Show worked answer
Construct A <=p B. Transform an A instance into a B instance so that a polynomial B solver yields a polynomial A solver. B <=p A only shows that A can solve B and does not establish the desired hardness of B.
Public notes & references
Course sources establish the scope above. Reference materials support the explanations; linked lecture notes and books remain with their authors.
Topics
- divide-and-conquer
- dynamic programming
- linear programming
- greedy algorithms
- graph algorithms
- NP-completeness
Course catalogue
2026
Readings
- Algorithms, by Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani.
Prerequisites & course information
Also listed as MATH 3804 . Prerequisite(s): COMP 2402 and one of ( COMP 2804 or COMP 3805 or MATH 3825 or MATH 3855 ). Lectures and tutorials three to four and a half hours a week.