CMSC 451
Design and Analysis of Computer Algorithms
Samir Khuller
Spring 2009

Home

Handouts

Lectures

Syllabus

Announcements

Final is on May 15th (8--10am).

Quiz (30 mins) will be on Feb 19th. Average for Quiz 1 is 21.44, median is 24.

Average for Midterm is 77.29, median is 81.

Class forum:

Homework 6 is now due on the class of 16th April.

Some applets related to algorithms taught in the class Applets

Handouts

Lectures

Date	Topic	Reading (in the book/handout)	Video Lectures
Lecture 1:01/27	General overview	Chapter 1	Video 1
Lecture 2:01/29	Stable marriage problem, proof of optimality	Chapter 1	Video 2
Lecture 3:02/03	DFS, BFS, Strong Connectivity	Chapter 2-3	Video 3
Lecture 4:02/05	Directed DFS, Strong Components	See CLRS	Video 4
Lecture 5: 02/10	Topological Sort	Chapter 3	NO TAPE
Lecture 6:02/12	Cut nodes	Biconnected Components Biconnected Components Algorithm	NO TAPE
Lecture 7:02/17	Minimum Spanning Tree, basic MST proofs of correctness Kruskal/Prim/Boruvka algorithm for MST	Chapter 4	Video 7
Lecture 8:02/19	MST finished Brief matroid discussion QUIZ	Section 4.1	Video 8
Lecture 9:02/24	Interval scheduling Interval Graphs/Graph Coloring	Chapter 4.1	Video 9
Lecture 10:02/26	Amortized analysis UNION-FIND data structure Interval graph coloring	Chapter 17 from CLRS Chapter 4.1	Video 10
Lecture 11:03/03	Amoritzed Analysis/Interval Graph Coloring	Chapter 4	Video 11
Lecture 12: 03/05	Dijkstra Algorithm Bellman-Ford Algorithm	Chapter 4.4 from CLRS	Video 12
Lecture 13:03/10	Bellman-Ford and Negative Cycle Detection REVIEW	Sample Exam	NO TAPE
Lecture 14: 03/12	MIDTERM	Singly connected graphs	NO TAPE
Lecture 15: 03/24	Midterm Discussion		NO TAPE
Lecture 16: 03/26	Dynamic Programming Knapsack	Chapter 6.3	Video 16
Lecture 17: 03/31	Dynamic Programming Weighted Interval Scheduling Segmented Least Squares	Chapter 6	Video 17
Lecture 18: 04/02	All pairs shortest paths: Sequence Alignment	Chapter 6 Shortest Paths from CLRS	Video 18
Lecture 19: 04/07	Divide and conquer closest pair algorithm Long number multiplication	Chapter 5 (5.1--5.5)	Video 19
Lecture 20: 04/09	Counting Inversions Recurrences Tennis Scheduling	Chapter 5 Tennis Handout Lecture notes from Peter Fontana Notes	NO TAPE
Lecture 21: 04/14	Flows	Chapter 7.1-7.3	Video 21
Lecture 22: 04/16	Bipartite Matching	Bipartite Matching	Video 22
Lecture 23: 04/21	Flows and an application	Chapter 7	Video 23
Lecture 24: 04/23	Max Flow-Min Cut Theorem/NP-Completeness	NP-Completeness Chapter 8.1-8.4	Video 24
Lecture 25: 04/28	Reduction from Independent Set to Vertex Cover problem Reduction from 3SAT to Independent Set problem	NP-Completeness Slides	NO TAPE
Lecture 26: 04/30	Reduction from 3SAT to SUBSET SUM problem	Section 34.5.5 from CLRS	Video 26
Lecture 27: 05/05	Reduction from SUBSET SUM to PARTITION problem Reduction from PARTITION to Scheduling with release time/deadline		NO TAPE
Lecture 28: 05/07	Course wrap-up and REDUCTION from PARTITION to SCHEDULING		Video 28
Lecture 29: 05/12	Review (TSP and Chain Matrix Mult) Intro to approximations.		Video 29