CMSC 451: Design and Analysis of Algorithms

Spring 2013

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) KT 1.1
Man-optimality proof
2 Graphs Intro to Graphs, BFS (JC)
DFS (JC)
Strong connectivity (SK)
KT 3.1-3.4
CLRS on SC
3 Graphs Euler tours (JC)
MSTs (JC)
Single-Source Shortest Paths (JC)
KT 4.4-4.6
4 Graphs Bellman-Ford for SSSP (SK)
2-edge connectivity/bridge identification (SK,JC)
Matchings (SK)
Notes on bridge ID
Notes on matchings (pages 39-40)
5 Greedy Algorithms Scheduling (JC)
Huffman Codes and Data Compression (JC)
KT 4.1, 4.2, 4.8
Scheduling to maximize profit
6 Divide and Conquer Midterm review
Midterm 1
Closest Pair (SK)
KT 5.4
7 Divide and Conquer Closest Pair, cont'd (JC)
(Snow day)
Tennis problem (SK)
KT 5.4
8 Dynamic Programming Integer Multiplication (JC)
Weighted Interval Scheduling (JC)
Floyd-Warshall's algorithm (SK)
KT 5.5, 6.1
CLRS on Floyd-Warshall
-- Spring Break    
9 Dynamic Programming Floyd-Warshall (JC)
Knapsack (JC)
NIM games (SK)
 
KT 6.4
NIM games
10 Dynamic Programming Segmented Least Squares (JC)
Sequence Alignment (JC)
Midterm review
KT 6.3
KT 6.6
Alternate proof of Kruskal's alg
11 Network Flows Midterm 2
Network Flows (SK)
 
12 Network Flows Network Flows (SK, JC)
Periodic Scheduling (JC)
Baseball Elimination (JC)
KT 7.1, 7.2, 7.5, 7.12
Periodic Scheduling
13 NP-completenessIntro to NP-completeness (SK)
Reduction: 3-CNF-SAT to CLIQUE (JC)
KT 8.4-8.8
NP-C cartoon
CLRS on SAT to CLIQUE
14 NP-completeness Reductions, transitivity of reductions (JC)
Reductions, finding an optimal VC (JC)
(No lecture 5/3)
Finding an optimal VC via decision oracle
15 NP-completeness Reductions, approaches to intractable problems (SK)
Final review on 5/10 (JC)
CLRS on SAT to SUBSETSUM