15-451 - Algorithm Design and Analysis, Spring 2026

MW 12:30pm - 1:50pm in DH 2315

Course Information

Ed Discussion
Lecture Feedback Form
problem list (continuously updated)
Annoucements:
- Apr 23: on Friday Apr 14:
  - recitation A is canceled, merged with B (in Tepper 3500, same time, 10am).
  - Ava's office hours (originally F4-5pm) moved to next Monday Apr 27, 4-5pm on zoom.
- Apr 15: homework 6 solutions (and grades) posted.
- Jan 12: Recitation F has been merged into E (MM103 at same time (F12noon) ).
Instructors:
- Yang P. Liu
- Yang (Richard) Peng
office hours F 2pm - 4pm, GHC 7115 (after the Friday recitations).
TAs:
- Flora Cheng, OH Thursday 5-6pm GHC4101, Recitation A (F10am BH A36)
- Ryan Chernoff, OH Wednesday 11am-12noon GHC7501, Recitations B (F10am TEP 3500), D (F11am, WEH 5312)
- Thomas Damani, OH Wednesday 6-7pm GHC8115, Recitations E (F12noon, MM103), G (F1pm, WEH5310)
- Spencer Fisher, OH Saturday 3-4pm GHC6501, Recitations C (F11am, WEH5320), H (F1pm, WEH5312)
- Changxiang Gao, OH Tuesday 5-6pm GHC6501, Recitations D (F11am, WEH5312), G (F1pm, WEH5310)
- Yanru Guan, OH Wednesday 5-6pm GHC8115, Recitation A (F10am, BH A36)
- Ava Pun, OH Friday 4-5pm GHC 8115, Recitations B (F10am, TEP3500), D (F11am, WEH5312)
- Alicia Stepin, zoom OH, Thursday 4-5pm https://cmu.zoom.us/j/6850538577, Recitation C (F11am, WEH5320)
- Jolyne Wang, OH Wednesday 3-4pm GHC7101, Recitations E (F12noon, MM103), H (F1pm, WEH5312)

Schedule

Tue Jan 13	Introduction and course logistics	hw1 out, due Jan 18 (solutions)
Thu Jan 15	Knapsack Dynamic Programs
Fri Jan 16	recitation 1
Tue Jan 20	DAGs and Dynamic Programming	oral hw1 out, due week of Jan 26-30 (solutions)
Thu Jan 22	Prefix/Interval Dynamic Programming	quiz 1 (solutions)
Fri Jan 23	recitation 2
Tue Jan 27	Tree Dynamic Programming	hw2 out, due Feb 1 (solutions)
Thu Jan 29	Range Queries
Fri Jan 30	recitation 3
Tue Feb 3	Lazy Segment Trees and Geometric Applications	oral hw2 out, due Feb 8 - 11 (solutions)
Thu Feb 5	String Hashing	quiz 2 (solutions)
Fri Feb 6	recitation 4

Tue Feb 10	Union/Find of Disjoint Sets	visit from Citadel
Thu Feb 12	Amortized Analysis I	hw3 out, due Tu Feb 24, (solutions), early course feedback (ECF) visit from Eberly Center
Fri Feb 13	recitation 5
Tue Feb 17	Amortized Analysis II
Thu Feb 19	Midterm 1	DP, range operations, string hashes (problem list)
Fri Feb 20	recitation 6

Tue Feb 24	Greedy algorithms	hw 4 out, due Mar 1 (solutions)
Thu Feb 26	Path Packing and Maximum Flow	quiz 3 (solutions), Mar 2--6 spring break
Fri Feb 27	recitation 7
Tue Mar 10	Cuts and Capacity Scaling	hw 5 out, due Sunday Mar 15 9pm (solutions)
Thu Mar 12	Minimum Cost Flows and Intro to Linear Programming	quiz 4 (solutions)
Fri Mar 13	recitation 8
Tue Mar 17	Linear programming duality	oral hw3 out, due week of Mar 22-27 (solutions)
Thu Mar 19	Zero sum games	quiz 5 (solutions)
Fri Mar 20	recitation 9

Tue Mar 24	Online algorithms, prediction with expert advice
Thu Mar 26	Multiplicative weight update algorithm	hw6 out, due Sunday Apr 12 9pm (late Tuesday Apr 14 9pm) (solutions)
Fri Mar 27	recitation 10
Tue Mar 31	Midterm 2 Review / more on LPs (problem list)
Thu Apr 2	Midterm 2	amortized analysis, MST, flows, linear programs
Fri Apr 3	recitation 11

Tue Apr 7	Model of Computation, Selection, and Sorting
	no lecture Apr 9 due to Spring Carnival
Tue Apr 14	Comparison Model	oral hw4 out, due Apr 21 - 23 (solutions)
Thu Apr 16	Query Complexity	quiz 6 (takehome, solutions)
Fri Apr 17	recitation 12
Tue Apr 21	(optional)Binary Search Trees and Dynamic Optimality
Thu Apr 23	(optional)Linear Programming Algorithms
Fri Apr 24	review recitation (problem list)

Thu, Apr 30	Final exam, 1pm - 4pm, GHC 4401	data structures, optimization, computational models

Syllabus

The goals of this course are:

Understanding of the design and analysis on algorithms for a variety of problems.
Develop skills to reason about and prove properties of algorithms such as their correctness and running time.
Understand how data structures can provide efficient ways to quickly answer queries about data, and understand how these data structures can be used to build efficient algorithms.
Understand analysis techniques such as amortized analysis, probabilistic analysis, and minimax optimality.
Use the concept of approximation to find efficient algorithms for hard problems.
Learn techniques to effectively argue for the difficulty of some problems.

The course schedule is roughly in these four units:

Dynamic programming: knapsack, DAG, subset, prefix, interval, tree.
Data structures: (lazy) segment trees, merging small into large, amortized analysis with stacks and queues, string hashing/fingerprinting.
Greedy, flows (augmenting paths), capacity scaling, linear programming, duality, zero-sum games.
Other models of computation: approximation, online, streaming algorithms, lower bounds, RAM model (hashing).

Evaluation

Homework, 5%, Graded based on completion, 6 total.
Oral Homework, 10%, 4 total.
Quizzes, 15%, 6 with minimum dropped.
Exams, Midterm1 20% + Midterm2 20% + Final 30%

All problems that will be evaluated on in the course (through quizzes, oral HW, tests) will appear on homeworks during the preceding weeks. More details in this overlap and how it's sequenced:

Each homework will cosnist of 3 problems, released after Tuesday's lecture, and due Sundays at 3:00 PM.
Homework submission is graded on completion, but TAs will try to provide feedback before next Tuesday's lecture, at the start of which the homework will be discussed.
Quizzes will consist of a problem based on the previous week's homework. Changes will only involve simplifications.
Exams will also be based on problems that appeared on relevant homeworks. They are only partially cumulative, tentative content:
- Midterm 1: Thursday Feb 19 in class, covering dynamic programming and range operations.
- Midterm 2: Thursday Apr 2 in class, covering amortized analysis, greedy, and flows.
- Final exam: late Apr/early May, covers data structures, linear programs, and computational models.

Accomodations for Quizzzes

Students with disability accommodations have the option to either:

Take the quizzes during the usual lecture time without accommodations, with the 2 lowest scores dropped;
Distribute the 15% component equally among Midterm 1, Midterm 2, and the Final Exam, thus increasing their respective weights to 25% + 25% + 35%.

This selection must be made before Quiz 2. This is adapted from the policy from 15-259, Fall 2025.

Coding Components

Most topics in this course are implementable with fairly short programs (20-100 lines of standard style-guide C++). However, there are way too many such problems on the internet by this point, that one can even train LLMs on them by now. For example, just the AtCoder dynamic programming intro is 26 problem, and they release at least 7 problems a week...at 7am Pittsburgh time, on weekends.

So instead, we decided to treat auto-graders as a separate but related activity, via this discord server, with focus on the DP set mentioned above and the weekly AtCoder beginner contests. Note that modulo the overlap in personnel, this is completely disjoint from 15-451.