floating balls
CMSC 451
Design and Analysis of
Computer Algorithms
Fall 2025
Dave Mount

Lectures

All Lecture Notes: cmsc451-fall25-lects.pdf
Handrwritten Notes: cmsc451-fall25-notes.pdf

The Notes section contains hand-written notes.

Date Lecture Title Notes
Tue 9/2 01 Introduction to Algorithm Design PDF
Thu 9/4 02 Graph Basics and Depth First Search PDF
Tue 9/9 03 Cycles and Strong Components PDF
Thu 9/11 04 Graph Shortest Paths: Dijkstra and Bellman-Ford PDF
Tue 9/16 05 Greedy Algorithms for Scheduling PDF
Thu 9/18   Quiz 1 (In class)  
Tue 9/23
Thu 9/25		 06 k-Center Clustering and Gonzalez’s Algorithm PDF
Tue 9/30 07 Greedy Approximation: Set Cover PDF
Thu 10/02 08 DP: Weighted Interval Scheduling PDF
Tue 10/07 09 DP: LCS and Edit Distance PDF
Thu 10/09   Quiz 2 (In class)  
Tue 10/14   No lecture (Fall Break)  
Thu 10/16 10 DP: Chain Matrix Multiplication PDF
Tue 10/21 11 DP: All-Pairs Short Paths and Floyd-Warshall PDF
Thu 10/23
Tue 10/28		 12 Network Flows: Basic Concepts PDF
Thu 10/30   Quiz 3 (In class)  
Tue 11/04 13 Network Flows: Algorithms PDF
Thu 11/06 14 Network Flows: Circulations and Applications PDF
Tue 11/11 15 NP-Completeness: Basic Definitions PDF
Thu 11/13
Tue 11/18		 16 NP-Completeness: 3SAT and Independent Set PDF
Thu 11/20   Quiz 4 (In class)  
Tue 11/25 17 NP-Completeness: Clique, Vertex Cover, and Dominating Set PDF
Tue 12/02 18 Approximation: Vertex Cover and TSP PDF
Thu 12/04 19 Approximation: Subset Sum PDF
Tue 12/09   Quiz 5 (In class)  
Thu 12/11   Final Review  

Web Accessibility