CMSC 451
Design and Analysis of Computer Algorithms
Samir Khuller
Fall 2005

Home

Handouts

Lectures

Syllabus

 

General Information

 

Class Time  

Tue-Thu 9:30-10:45am

Room

CSI 3120

Course Info

Syllabus(PDF format)

Text

Algorithm Design, John Kleinberg, Eva Tardos

Personnel

 

Instructor

Teaching Assistant

Name

Samir Khuller

Maryam Farboodi

Email

samir@cs.umd.edu

farboodi@cs.umd.edu

Office

AVW 3369

AVW 1112

Office hours

Mon 3-4, Thu 2-3

Tue 12-2, Wed 1-2

Dr. Khuller will be traveling next week. Send him email or see the TA next week.

Announcements

 

The final (COMPREHENSIVE) exam will be Friday, December 16, 8-10 am in CSIC 3120. The focus of the exam will be on the material covered after the midterm.

Please fill the online course evaluation form before Tuesday, Dec. 13 (11:55) at: Online Evaluation

You can pick up your homework 8 during the office hours on Tuesday, December 13.

The final is closed book and closed notes. You are NOT allowed to bring a cheat sheet.

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

Average

Homework 0

Sep 6

Due sep 13

Solution 0

80.81

Homework 1

Sep 13

Due Sep 22

Solution 1

66.04

Homework 2

Sep 22

Due Sep 29

Solution 2

52.5

Homework 3

Sep 29

Due Oct 13

Solution 3

59.32

Homework 4

Oct 13

Due Oct 20

Solution 4

68

Homework 5

Oct 27

Postponed to Nov 8

Solution 5

Better solution for problem 3

53.86

Homework 6

Nov 9

Nov 17

Solution 6

54.59

Homework 7

Nov 18

Nov 29

Solution 7

64.71

Homework 8

Dec 1

Dec 8

Solution 8

66.22

Lectures

 

Date

Topic

Reading (in the book/handout)

Sep 1

General overview; Stable marriage problem

Chapter 1

Sep 6

Stable marriage problem, proof of optimality; Graphs, Representation of graphs

Chapter 1

Sep 8

DFS, Order notation, BFS, Top sort

Chapter 2-3

Sep 13

Top sort, Directed DFS

Chapter 2-3

Sep 15

Cut nodes

Biconnected Components
Biconnected Components Algorithm

Sep 20

Strong connectivity and strong components

Chapter 22.5 from CLRS

Sep 22

Minimum Spanning Tree, basic MST proofs of correctness
Kruscal algorithm for MST

Chapter 4

Sep 27

MST finished
Heaps
Prim's algoritm
Finding maximum collection of disjoint intervals



Section 4.1

Sep 29

Amortized analysis
UNION-FIND data structure
Interval graph coloring

Chapter 17 from CLRS

Chapter 4.1

Oct 4

Huffman coding

Chapter 4

Oct 6

QUIZ: 45 minutes in class; closed notes, books, etc.
AVERAGE: 64.84

 

Oct 11

Dijkestra Algorithm
Bellman-Ford Algorithm

Chapter 4.4
from CLRS

Oct 13

Solving quiz problems
Dynamic Programming algorithm for KNAPSACK

 

Oct 18


Toothpick game

Chapter 6.1
Toothpick game

Oct 20

Practice problems for midterm exam
Singly connected graphs


Singly connected graphs

Oct 25

MIDTERM
AVERAGE: 60.33

 

Oct 27

Midterm discussion


Chapter 6.3

Nov 1

Dynamic Programming
Exercise 1 and 2 (solved exercises from book)
Line fitting problem



Chapter 6.3

Nov 3

Homework 5 discussion
Dynamic Programming
Sequence alignment



Chapter 6.6

Nov 8

2 algorithms for all pairs shortest paths:
First one from the book;
Second one Floyd Warshall


Chapter 6

Nov 10

Divide and conquer closest pair algorithm

Chapter 5

Nov 15

Randomized and deterministic SELECTION (median finding) algorithms

 

Nov 17

Devide and Conquer:
Long number multiplication;
Counting inversions

Chapter 5

Nov 22

NP-Completeness

NP-Completeness

Nov 29

Review of NP-Completeness
Reduction from Independent Set to Vertex Cover problem
Reduction from 3SAT to Independent Set problem
Introduction to Dominating Set problem

Chapter 8
 
 
 

Dec 1

Reduction from 3SAT to SUBSET SUM problem

Section 34.5.5 from CLRS

Dec 6

Reduction from SUBSET SUM to PARTITION problem
Reduction from PARTITION to Scheduling with release time/deadline
Reduction from Hamiltonian Cycle to Hamiltonian Path problem

 

Dec 8

Reduction from Vertex Cover to Dominating Set problem

 

This is the link to Dr Mount's lecture notes for cmsc451, Fall2003

Acknowledgments

 

I (Maryam Farboodi) would like to thank Dr. Mount for letting me use his 451 class page as a template for this page.