CMSC 451: Design and Analysis of Computer Algorithms

University of Maryland, Fall 2026

Instructor: Runzhou Tao

Staff:

Name Email 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. 2:20-3:20PM at AVW 4160 & Thurs. 4-5PM on Zoom
Chenxin Yu cy1229@umd.edu Wed. 5-6PM at IRB 5th floor

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.

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 Notes Kleinberg and Tardos 4.4, 6.8
09/16   Greedy Algorithms for Scheduling Notes Kleinberg and Tardos 4.1, 4.2
09/21 4 Quiz 1 (In class)  
09/23   Greedy Approximation: Set Cover and Stone Merging Notes Kleinberg and Tardos 4.8, 11.3
09/28 5 DP: Weighted Interval Scheduling Notes Kleinberg and Tardos 6.1, 6.2
09/30   DP: LCS and Edit Distance Notes Kleinberg and Tardos 6.6
10/05 6 DP: Chain Matrix Multiplication Notes CLRS 15.2
10/07   Quiz 2 (In class)  
10/12-13 7 Fall Break  
10/14   Randomized Algorithms Notes Kleinberg and Tardos 13.1, 13.2
10/19 8 DP: All-Pairs Short Paths and Floyd-Warshall Notes CLRS 25.2
10/21   Network Flows: Basic Concepts Notes Kleinberg and Tardos 7.1, 7.2
10/26 9 Network Flows: Basic Concepts Notes Kleinberg and Tardos 7.2, 7.3
10/28   Quiz 3 (In class)  
11/2 10 Network Flows: Algorithms Notes Kleinberg and Tardos 7.3, 7.4
11/4   Network Flows: Circulations and Applications Notes Kleinberg and Tardos 7.5, 7.7
11/9 11 NP-Completeness: Basic Definitions Notes Kleinberg and Tardos 8.1, 8.3
11/11   NP-Completeness: 3SAT and Independent Set Notes Kleinberg and Tardos 8.2, 8.4
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