CMSC 451Design and Analysis of Computer AlgorithmsSamir KhullerSpring 2009

 Home Handouts Lectures Syllabus
 General Information

Class Time

Tue-Thu 9:30-10:45am

Room

CSI 1122

Course Info

Text

Algorithm Design, Jon Kleinberg, Eva Tardos

Personnel

 Instructor Teaching Assistant Name Samir Khuller Barna Saha Email samir@cs.umd.edu barna@cs.umd.edu Office AVW 3369 AVW 1112 Office hours Mon 3-4, Thu 11-12 Tue 4:15-5:30, Wed 4:15-5:30

 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:

CMSC 451 Forum

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

Some applets related to algorithms taught in the class Applets

 Handouts

Homeworks will be due at the beginning of class on the due date. Late homeworks will not be accepted, so turn in whatever you have done.

 Handout Handed out Comments Solutions Solution Posted Average 1/28/09 Total=50 Solution 1 2/06/09 34.72 (Median=37) 2/7/09 Total=50 Solution 2 2/18/09 30.55 (Median=38) 2/16/09 Total=50 Solution 3 3/02/09 25.72 (Median=30) 2/25/09 Total=50 Solution 4 3/06/09 36.9 (Median=40) 3/14/09 Total=50 Solution 5 04/01/09 30.29 (Median=35) 4/2/09 Total=40 04/17/09 18.11 (Median=16) 4/17/09 Total=50 04/29/09 26.86 (Median=27) 4/30/09 Total=50 5/8/09 34 (Median=40)

 Lectures

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