CMSC 451: Design and Analysis of Computer Algorithms
University of Maryland, Fall 2026
Instructor: Runzhou Tao
Staff:
| Name | Office Hours | |
|---|---|---|
| Prof. Runzhou Tao | rztao@umd.edu | Wed. 2-3PM at IRB 5160, by appointment, or after class |
| Mattias Ehatamm | mehatamm@umd.edu | Tues. 2-3PM at AVW 4160 & Fri. 2-3PM on Zoom |
| Hongzheng Zhu | hzhu1238@umd.edu | Mon. 11-12AM at AVW 4160 & Thurs. 4-5PM on Zoom |
Time: Mon & Wed 3:30pm - 4:45pm
Location: CSI 2117
Description: This course provides a further treatment of concepts addressed in earlier algorithms classes and introduces several advanced concepts. Students will learn about different types of algorithms and tools for reasoning about them. The syllabus includes topics such as Graph Algorithms, Greedy Algorithms, Dynamic Programming, NP-Completeness, Randomized Algorithms, and Quantum Algorithms.
Generics
Prerequisite: Minimum grade of C- in CMSC351. Students are expected to be familiar with the following topics, and if not should refresh their understanding:
- Basic programming concepts
- Basic calculus
- Discrete math (combinatorics, probability, graph theory, proof by induction, set theory)
- Analysis of algorithms (big-O notation, recurrence relations)
- Data Structures (stacks, trees, lists, heaps)
Canvas: link
Syllabus: see below
In general, please send your questions/requests via Piazza or email. We will reply as soon as possible.
Evaluation: quizzes (75%), final exam (25%). Details in the policy page.
Textbooks & Lectures
We will mainly use notes (available online or our own) for lectures. The following textbooks cover most of the content we will discuss, though other sources may be superior for certain topics.
- Algorithm Design, by Jon Kleinberg and Eva Tardos, Addison-Wesley, 2005.
- Introduction to Algorithms, (3rd Edition), by T. Cormen, C. Leiserson, R. Rivest, and C. Stein, McGraw Hill, 2009.
Syllabus
Below is the tentative schedule (subject to frequent updates, with most currently TBD). Reading assignments and references will be included.
| Date | Week | Lecture | Reading |
|---|---|---|---|
| 08/31 | 1 | Introduction to Algorithm Design Slides Notes | Understanding Science through the Computational Lense by Richard Karp, Kleinberg and Tardos 2.1, 2.2, 2.4 |
| 09/02 | Asymptotic Notations and Graph Basics Notes | Kleinberg and Tardos 2.2, 3.1 | |
| 09/07 | 2 | Labor Day | |
| 09/09 | Depth First Search, Cycles and Strong Components Notes | Kleinberg and Tardos 3.2, 3.5, 3.6 | |
| 09/14 | 3 | Graph Shortest Paths: Dijkstra and Bellman-Ford | |
| 09/16 | Greedy Algorithms for Scheduling | ||
| 09/21 | 4 | Quiz 1 (In class) | |
| 09/23 | Randomized Algorithms | ||
| 09/28 | 5 | Greedy Approximation: Set Cover | |
| 09/30 | DP: Weighted Interval Scheduling | ||
| 10/05 | 6 | DP: LCS and Edit Distance | |
| 10/07 | Quiz 2 (In class) | ||
| 10/12-13 | 7 | Fall Break | |
| 10/14 | DP: Chain Matrix Multiplication | ||
| 10/19 | 8 | DP: All-Pairs Short Paths and Floyd-Warshall | |
| 10/21 | Network Flows: Basic Concepts | ||
| 10/26 | 9 | Network Flows: Basic Concepts | |
| 10/28 | Quiz 3 (In class) | ||
| 11/2 | 10 | Network Flows: Algorithms | |
| 11/4 | Network Flows: Circulations and Applications | ||
| 11/9 | 11 | NP-Completeness: Basic Definitions | |
| 11/11 | NP-Completeness: 3SAT and Independent Set | ||
| 11/16 | 12 | Quiz 4 (In class) | |
| 11/18 | NP-Completeness: Clique, Vertex Cover, and Dominating Set | ||
| 11/23 | 13 | Approximation: Vertex Cover and TSP | |
| 11/25-29 | Thanksgiving Break | ||
| 11/30 | 14 | Approximation: Subset Sum | |
| 12/2 | Quiz 5 (In class) | ||
| 12/7 | 15 | Quantum Algorithms | |
| 12/9 | Final Review |