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 | By appointment or After class |
| Mattias Ehatamm | mehatamm@umd.edu | Tues. 2-3PM & Wed. 2:30-3:30PM at AVW 4160 |
| Hongzheng Zhu | hzhu1238@umd.edu | Mon. 11-12AM & Thurs. 4-5PM at AVW 4160 |
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, and
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)
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 | Understanding Science through the Computational Lense by Richard Karp, Kleinberg and Tardos 2.1, 2.2, 2.4 |
| 09/02 | Graph Basics and Depth First Search | ||
| 09/07 | 2 | Cycles and Strong Components | |
| 09/09 | Graph Shortest Paths: Dijkstra and Bellman-Ford | ||
| 09/14 | 3 | Greedy Algorithms for Scheduling | |
| 09/16 | Quiz 1 (In class) | ||
| 09/21 | 4 | Randomized Algorithms 1 | |
| 09/23 | Randomized Algorithms 2 | ||
| 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 | NP-Completeness: 3SAT and Independent Set | |
| 11/18 | Quiz 4 (In class) | ||
| 11/23 | 13 | NP-Completeness: Clique, Vertex Cover, and Dominating Set | |
| 11/25-29 | Thanksgiving Break | ||
| 11/30 | 14 | Approximation: Vertex Cover and TSP | |
| 12/2 | Approximation: Subset Sum | ||
| 12/7 | 15 | Quiz 5 (In class) | |
| 12/9 | Final Review |