CMSC 451: Schedule

Course Schedule

Week of:	Tuesday	Thursday
Jan 29 & 31	Course Intro and Review Course Syllabus Lect 1: Introduction to Algorithm Design	Review Lect 2: Review: Stable Marriage Problem
Feb 5 & 7	Review Lect 3: Review: Mathematical Background	Basic Graph Review Lect 4: Basic Graph Algorithms: BFS and DFS
Feb 12 & 14	Depth-First Search Lect 5: Applications of DFS	Biconnectivity Lect 5 (cont): Applications of DFS
Feb 19 & 21	Greedy Algorithms Lect 6: Interval Scheduling and Fractional Knapsack	Greedy Algorithms Lect 7: Huffman Coding
Feb 26 & 28	Greedy Graph Algorithms Lect 8: Minimum Spanning Trees and Kruskal's Algorithm	Greedy Graph Algorithms Lect 9: Dijkstra's Algorithm for Shortest Paths
Mar 4 & 6	Dynamic Programming Lect 10: Longest Common Subsequence	Dynamic Programming Lect 11: Weighted Interval Scheduling
Mar 11 & 13	Dynamic Programming Lect 12: All-Pairs Shortest Paths and the Floyd-Warshall Algorithm	Dynamic Programming Lect 12 (cont): All-Pairs Shortest Paths and the Floyd-Warshall Algorithm
Mar 18 & 20	Spring Break	Spring Break
Mar 25 & 27	Dynamic Programming Lect 13: Chain Matrix Multiplication	Review for the Midterm Lect 14: Midterm Review
Apr 1 & 3	Midterm Exam	Network Flows Lect 15: Network Flows (updated 4/8)
Apr 8 & 10	Network Flows Lect 15 (cont): Network Flows (updated 4/8)	Network Flows Lect 16: Applications and Extensions of Network Flow
Apr 15 & 17	NP-Completeness Lect 17: Languages and the Class NP	NP-Completeness Lect 18: Reductions
Apr 22 & 24	NP-Completeness Lect 19: Cook's Theorem, 3SAT, and Independent Set	NP-Completeness Lect 20: Clique, Vertex Cover, and Dominating Set
Apr 29 & May 1	NP-Completeness Lect 21: Hamiltonian Path	Approximation Algorithms Lect 22: Vertex Cover and TSP
May 6 & 8	Approximation Algorithms Lect 23: Set Cover and Bin Packing	Approximation Algorithms Lect 24: The k-Center Problem
May 13	Review for the Final Lect 25: Final Review	Final Exam: Fri, May 16, 8-10am

Midterm Exam

The mideterm exam will be Tuesday, Apr 1 in class. The exam will be closed-book, closed-notes, but you are allowed one "cheat-sheet", front and back.

Final Exam

The final exam will be Friday, May 16, 8:00-10:00 am. More information will be forthcoming.