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

Lectures

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

The Notes section contains hand-written notes.

Date Lecture Title Notes
Tue 01/28 01 Introduction to Algorithm Design PDF
Thu 01/30 02 Graph Basics and Depth-First Search PDF
Tue 02/04 03 Cycles and Strong Components PDF
Thu 02/06
Tue 02/11		 04 Shortest Paths: Dijkstra and Bellman-Ford PDF
Thu 02/13 05 Greedy Algorithms for Scheduling PDF
Tue 02/18
Thu 02/20		 06 k-Center Clustering and Gonzalez's Algorithm PDF
Tue 02/25 07 Greedy Approximation: Set Cover PDF
Thu 02/27 08 DP: Weighted Interval Scheduling PDF
Tue 03/04 09 DP: Longest Common Subsequence and Edit Distance PDF
Thu 03/06
Tue 03/11		 10 DP: Chain Matrix Multiplication PDF
Thu 03/13 11 DP: All-Pairs Shortest Paths and Floyd-Warshall PDF
Tue 03/25 12 Network Flow: Basic Concepts PDF
Thu 03/27 13 Network Flow: Algorithms PDF
Tue 04/01
Thu 04/03
Thu 04/08		   Review and Midterm Exam  
Thu 04/10 14 Network Flow: Extensions and Applications PDF
Tue 04/15 15 NP-Completeness: Definitions PDF
Thu 04/17 16 NP-Completeness: Reductions PDF
Tue 04/22 17 NP-Completeness: 3SAT and Independent Set PDF
Thu 04/24 18 NP-Completeness: Clique, VC, and DS PDF
Tue 04/29 19 NP-Completeness: Hamiltonian Cycle PDF
Thu 05/01 20 Approximation: Vertex Cover and TSP PDF
Tue 05/06
Thu 05/08		 21 Approximation: Subset Sum PDF

Web Accessibility