CMSC 451: Section 0101

Lecture Notes

This page has links to the lecture notes. I try to make the lecture notes available as soon as possible. (Unfortunately, this is sometimes not until shortly before each class.) If you do not see the lecture notes posted by the afternoon after class, please send me an email reminder. Unless otherwise indicated, all readings are from the recommended text by Kleinberg and Tardos (KT) or Dasgupta, Papadimitriou, and Vazirani (DPV). For example, KT:1 means Chapter 1 of Kleinberg and Tardos.

All the lecture notes in one file: cmsc451-fall17-lects.pdf

Date	Num	Title	Reading
08/29 Tue	01	Introduction to Algorithm Design	KT:1,2; DPV:1
08/31 Thu	02	Graph Basics	KT:3; DPV:3
09/05 Tue	03	Guest Lecture by Prof. Samir Khuller. See Section 3.4 of DPV and my own lecture notes on Cycles and Strong Components	KT:3; DPV:3
09/07 Thu	04	Guest Lecture by Prof. Samir Khuller. See Khuller's lecture notes and my own lecture notes on Bridges and 2-Edge Connectivity
09/12 Tue	05	Graph Shortest Paths: Dijkstra and Bellman-Ford	KT: 4.4, 6.8; DPV: 4.4 – 4.6
09/14 Thu	06	Greedy Algorithms: Huffman Coding (Updated 9/18)	KT: 4.8; DPV: 5.2
09/19 Tue 09/21 Thu	07	Greedy Algorithms for Scheduling	KT: 4.1 and 4.2
09/26 Tue	08	Greedy Approximation: The k-Center Problem	KT: 11.2; DPV: 9.2.2
09/28 Thu	09	Greedy Approximation: Set Cover	KT: 11.3; DPV: 5.4
10/03 Tue	10	Dynamic Programming: Weighted Interval Scheduling	KT: 6.1
10/05 Thu 10/10 Tue	11	Dynamic Programming: Longest Common Subsequence	KT: 6.6; DPV 6.3
10/12 Thu	12	Dynamic Programming: Chain Matrix Multiplication	DPV: 6.5
10/17 Tue 10/19 Thu	13	Dynamic Programming: Floyd-Warshall Algorithm (Updated 10/21)	DPV: 6.6
10/24 Tue		Review for the Midterm Exam
10/26 Thu		Midterm Exam
10/31 Tue	14	Network Flows: Basic Definitions	KT: 7.1
11/02 Thu	15	Network Flows: The Ford-Fulkerson Algorithm	KT: 7.2, 7.3
11/07 Tue	16	Network Flows: Algorithms	KT: 7.1, 7.3, 7.5
11/09 Thu 11/14 Tue	17	Network Flows: Extensions (Updated 10/16)	KT: 7.7
11/16 Thu	18	NP-Completeness: General Definitions	DPV: 8, KT: 8
11/21 Tue	19	NP-Completeness: Reductions	DPV: 8.2, KT: 8.1
11/28 Tue	20	NP-Completeness: 3SAT and Independent Set	DPV: 8.3, KT: 8
11/30 Thu	21	NP-Completeness: Clique, VC, and Dominating Set	DPV: 8.3, KT: 8.4
12/5 Tue	22	Approximations Algorithms: Vertex Cover and TSP	DPV: 9.2, KT: 11.3
12/7 Thu		Final Review

Return to CMSC 451 Home — The cool image at top of page is a portion of the Hall-Janko Graph, a strongly-regular graph on 100 vertices, where every vertex has 36 neighbors.

Web Accessibility