Hall-Janko Graph
Index
Home
Syllabus
Lectures
Handouts
Grades

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