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 for midterm 1, dynamically updated
Annoucements:
- Recitation F no longer exists, it merged into E (same time, F12noon, MM103) instead.
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 GHC 7501, 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 7101, 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 GHC8102, 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
Thu Feb 5	String Hashing	quiz 2

Tue Feb 10	Union find, merging sets	visit from Citadel
Thu Feb 12	Stacks/queues and amortized analysis I	hw3 out, due Feb 22, early course feedback (ECF) visit from Eberly Center
Tue Feb 17	Amortized analysis II
Thu Feb 19	Midterm 1	DP, range operations

Tue Feb 24	Greedy algorithms, exchange method	hw 4 out, due Mar 8
Thu Feb 26	Greedy, regret method, flows I: Ford-Fulkerson	quiz 3, Mar 2--6 spring break
Tue Mar 10	Flows II: maxflow-mincut, capacity scaling.	hw 5 out, due Mar 13
Thu Mar 12	Greedy, regret method, flows III / intro to linear programs	quiz 4
Tue Mar 17	Linear programming duality.	oral hw3 out, due week of Mar 22-27
Thu Mar 19	Zero sum games	quiz 5

Tue Mar 24	TBD	TBD
Thu Mar 26	TBD	hw6 out, due Apr 12, TBD
Tue Mar 31	TBD	TBD
Thu Apr 2	Midterm 2	amortized analysis, greedy, flows, linear programs

Tue Apr 7		no lecture Apr 9 due to carnival
Tue Apr 14	TBD	TBD + oral hw4 out, due week of Apr 20 - 24
Thu Apr 16	TBD	TBD + quiz 6
Tue Apr 21	TBD	TBD
Thu Apr 23	TBD	TBD

TBD, 3 hrs	Final exam	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.