Design and Analysis of Algorithms II

Advanced analysis and proof structure

An advanced algorithm argument still needs a contract, correctness proof, and resource bound. Identify which resource matters: arithmetic operations, bits, comparisons, memory transfers, or communication. Arithmetic on unbounded integers is not automatically constant time. Recurrences can depend on unequal subproblem sizes or random choices, so a familiar master-theorem template may not apply. Begin from the actual decomposition and justify any simplification. Tight bounds require matching upper and lower arguments rather than confidence from a few measurements.

References: Jeff Erickson — Algorithms and advanced lecture notes

Amortized analysis and potential functions

Amortized analysis bounds the total cost of a sequence without assuming a random distribution over operations. The accounting method saves credit on cheap operations to pay for expensive ones; the potential method stores that credit in a function of the data structure. Define the potential and show that it stays within the conditions used by the proof. A low amortized bound does not imply a low worst-case latency for each individual operation, which matters in interactive or real-time systems.

References: Jeff Erickson — Algorithms and advanced lecture notes

Worked dynamic-array doubling argument

Start with an empty array whose capacity grows by doubling. Over n appends, each append writes one new element, and resizing copies capacities 1,2,4,... below the final size. That geometric sum is less than 2n, so fewer than 3n element writes and copies suffice under the simple cost model, aside from constant initialization work. Total cost is O(n) and amortized append is O(1). One resizing append still costs Theta(n), and allocation or element-copy costs can change the model.

References: Jeff Erickson — Algorithms and advanced lecture notes

Randomized algorithms and guarantees

A Las Vegas algorithm always returns a correct result but has random running time; a Monte Carlo algorithm bounds resources while permitting an error probability. State whether expected complexity holds for every fixed input over internal randomness or only for a distribution of inputs. Repetition can amplify confidence when runs are suitably independent, but repeating a biased or correlated procedure may not provide the claimed gain. Track failure probability through the whole algorithm rather than quoting one subroutine's guarantee.

References: Jeff Erickson — Algorithms and advanced lecture notes

Graph and geometric algorithms

Advanced graph methods often rely on a structural property such as a cut, residual path, separator, or embedding. A maximum-flow method must preserve capacity constraints and flow conservation while modifying residual capacities. Geometric algorithms also face degeneracy: collinear points, coincident coordinates, and precision error can violate an implementation's hidden assumptions. Separate an ideal real-number proof from a robust implementation. State how ties and exact predicates are handled so that correctness survives more than general-position examples.

References: Jeff Erickson — Algorithms and advanced lecture notes

Approximation and hard optimization problems

An approximation ratio compares a feasible solution with an optimum under a precise objective. For minimization, a factor-two guarantee means cost at most twice optimum; it does not mean an additive error of two. A reduction establishing hardness is different from an approximation-preserving reduction. Pseudopolynomial dynamic programming can be useful when numeric values are small even if it is not polynomial in encoded input length. Choose between exact, parameterized, approximation, and heuristic methods based on constraints and required guarantees.

References: Jeff Erickson — Algorithms and advanced lecture notes

Practice & worked answers

Original exercises for this guide.

Public notes & references

Course sources establish the scope above. Reference materials support the explanations; linked lecture notes and books remain with their authors.

• Carleton COMP 4804 — Fall 2026 outline ↗Course scope · Fall 2026
• Jeff Erickson — Algorithms and advanced lecture notes ↗Open author textbook
• Carleton COMP 4804 — Fall 2026 advanced algorithm scope ↗Topic map