CMU 15-451: Algorithm Design and Analysis
15-451 is CMU's advanced algorithms course: amortized analysis, network flow, linear programming and duality, NP-completeness and approximation, online and randomized algorithms. It's the senior-level capstone of the theory track after 15-210 and 15-251.
Fennie is independent and not affiliated with Carnegie Mellon University. This is an unofficial study guide.
What makes it hard
The problems require design under unfamiliarity at a higher bar than anything before: exams hand you problems that don't resemble homework and grade the algorithm, the proof, and the analysis together. The toolbox is broad and the course assumes you can deploy all of 210 and 251 without review. Gaps from those courses resurface here with interest.
What you'll cover
- • Amortized and potential-function analysis
- • Network flow and matchings
- • Linear programming and duality
- • NP-completeness and reductions
- • Approximation algorithms
- • Online and randomized algorithms
The 15-451 study guide
How to study for CMU 15-451, step by step.
- 1
Rehab the prerequisite toolbox first
451 deploys 210's design patterns and 251's proof rigor without slowing down. Audit both honestly in week one. Old gaps are the most common reason strong students struggle here.
- 2
Design cold, then calibrate against solutions
For every practice problem, produce your best algorithm and analysis before reading anything. The exam skill is original design under time, and it only builds through honest attempts.
- 3
Learn each technique's problem signature
Learn what makes a problem smell like flow, like LP, or like an amortized argument. Build the signature map deliberately. Exams test the choice of tool as much as its execution.
- 4
Practice reductions in both directions
NP-completeness problems reward fluency in transforming problems into one another. Work many reductions and articulate the pattern of each. The gadget intuition is trainable.
- 5
Re-solve homework from a blank page before exams
Reproducing a design and its full analysis without notes is the closest rehearsal for exam conditions. If you can't re-derive it, you recognized it rather than learned it.
Today
Today's 15-451 plan
What a Fennie Daily Plan looks like for 15-451. Yours is built from your own syllabus and adapts every day to your deadlines and progress.
First plan free, no card required. Fennie is independent and unaffiliated with your school.
FAQ
Is 15-451 hard?
It's the theory track's senior bar: exams present unfamiliar problems and grade design, proof, and analysis together, assuming 210 and 251 fluently. Students who practice cold design and keep the full toolbox deployable do well; recognition-level preparation gets exposed.
How does 15-451 differ from 15-210?
210 builds the foundation with its parallel cost framework; 451 goes wider and deeper (flow, LP duality, approximation, online algorithms) at a higher design difficulty, in a conventional sequential setting. Think of 451 as the course interviews and research both draw from.
How do I study for 15-451 exams?
Cold-design practice under time: unfamiliar problems, full algorithm-proof-analysis writeups, then line-by-line calibration against solutions. Build an explicit map of which problem features suggest which technique. Tool selection is half of every exam question.
More CMU courses
15-112: Fundamentals of Programming and Computer Science
15-112 is CMU's famous accelerated introduction to programming in Python: control flow, functions, data structures, recursion, OOP, and efficiency, ending in an open-ended term project. Its public course website and the related CMU CS Academy platform give it a search footprint far beyond Pittsburgh.
15-110: Principles of Computing
15-110 is CMU's gentler introduction to computing, covering Python programming plus computing concepts like data representation, algorithms, and the limits of computation. It's designed for students who aren't CS majors or who want a runway before 15-112, and it's one of the largest courses on campus.
15-122: Principles of Imperative Computation
15-122 teaches imperative programming with correctness front and center: contracts, loop invariants, and reasoning about code in the C0 teaching language before transitioning to real C. It covers data structures from stacks and queues through hash tables, trees, and graphs, and it's the second course of the CMU CS core.
15-150: Principles of Functional Programming
15-150 teaches functional programming in Standard ML: types, recursion and induction, higher-order functions, and reasoning about programs as mathematical objects. It runs alongside 15-122 in the CMU CS core, and for most students it's the first time programming and proof become the same activity.