CMSC 451: Design and Analysis of Algorithms

Spring 2015

Home | Syllabus/Homeworks | Schedule | Resources




The following is a tentative schedule of topics, subject to change.

Weekly Schedule

Week Topic Subtopic Reading
1 Introduction to Algorithms Stable Marriage (SK, JC)
Intro to graphs (JC)
KT 1.1
Man-optimality proof
2 Graphs: connectivity BFS, DFS (JC)
2-edge connectivity (JC)
KT 3.2-3.4
Lecture slides
Old notes on bridges
Properties of DFS
Proof of Menger's Theorem
3 Graphs Strongly Connected Components (SK)
MSTs (SK)
CLRS on SCC
KT 4.5
4 Greedy Algs for Graphs (Snow Day)
MSTs, Dijkstra's (JC)
KT 4.4
5 Greedy Algorithms Quiz 1, Interval Scheduling (SK) KT 4.1 (Greedy Chapter)
Scheduling to maximize profit
6   Review Session (JC)
(Snow Day)
Review problems
Thin Connectivity Notes
Thin Connectivity paper
7 Dynamic Programming Midterm 1 in class (SK)
Weighted Interval Scheduling (SK)
KT 6.1
-- Spring Break    
8 Dynamic Programming Knapsack (SK)
All pairs shortest path (SK)
KT 6.4
KT 6.8
Floyd-Warshall notes
9 Dynamic Programming Sequence Alignment (JC)
Matchings (JC)
KT 6.6
Hall's Theorem proof
Matching notes, plus alternative proof of Hall's Theorem
10   Review Session (SK)
Midterm 2 in class (SK, JC)
 
11 Network Flows Intro to network flows (SK, JC) Network Flow slides by Kevin Wayne
12 Network Flows Flow algs and scheduling (SK) Periodic scheduling notes
13 NP-completeness   NP complete notes
14 NP-completeness   Clique is NP-complete
Subset Sum is NP-complete
Notes on NP-completeness of Vertex Cover
15 Special Topics