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

Home

Handouts

Lectures

Syllabus

 

General Information

 

Class Time  

Tue-Thu 9:30-10:45am

Room

CSI 1122

Course Info

Syllabus(PDF format)

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:

Please register to
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

Homework 1

1/28/09

Total=50

Solution 1

2/06/09

34.72 (Median=37)

Homework 2

2/7/09

Total=50

Solution 2

2/18/09

30.55 (Median=38)

Homework 3

2/16/09

Total=50

Solution 3

3/02/09

25.72 (Median=30)

Homework 4

2/25/09

Total=50

Solution 4

3/06/09

36.9 (Median=40)

Homework 5

3/14/09

Total=50

Solution 5

04/01/09

30.29 (Median=35)

Homework 6

4/2/09

Total=40

Solution 6

04/17/09

18.11 (Median=16)

Homework 7

4/17/09

Total=50

Solution 7

04/29/09

26.86 (Median=27)

Homework 8

4/30/09

Total=50

Solution 8

5/8/09

34 (Median=40)

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