Click for more information

CMSC 451
Design and Analysis of Computer Algorithms
Julián Mestre
Summer 2004

Home

Handouts

Lectures

Syllabus

 

General Information

 

Class Time  

Mon-Fri 9:30-10:50am

Room

CSI 1122

Course Info

Syllabus (also in PDF format)

Text

Introduction to Algorithms, 2nd Edition, T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, McGraw-Hill, 2002.

Personnel

 

Instructor

Teaching Assistant

Name

Julián Mestre

Srinivas Kashyap

Email

jmestre@cs.umd.edu

raaghav@cs.umd.edu

Office

AVW 3212

AVW 1151

Office hours

Mon, Wed, Fri 11:00am-12:00

Tue, Thu 1:00-3:00pm

If you cannot make these office hours, please send email to arrange another time.

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

Homework 1

Jul 12

Due Jul 16

Solutions 1

Homework 2

Jul 16

Due Jul 26

Solutions 2

Homework 3

Jul 23

Due Jul 30

Solutions 3

Homework 4

Aug 03

Due Aug 09

 

Homework 5

Aug 09

Due Aug 16

Solutions 5

Homework 6

Aug 13

Due Aug 18

Solutions 6

Lectures

 

Date

Topic

Reading (in CLRS)

Lecture Notes

Jul 12

Course Introduction
Breadth First Search

Sec 22.1-2

 

Jul 13

Depth First Search

Sec 22.3

 

Jul 14

Topological Sort

Sec 22.4

 

Jul 15

Strongly Connected Components
Articulation points

Sec 22.5

Articulation points

Jul 16

Minimum spanning trees

Sec 23.1

 

Jul 19

Kruskal's Algorithm

Sec 23.2

 

Jul 20

Prim's Algorithm

Sec 23.2

 

Jul 21

Maximum capacity path
Single source shortest path

Sec 24.0

Maximum capacity

Jul 22

Bellman-Ford Algorihtm
Shortest paths in directed acyclic graphs

Sec 24.1-2

 

Jul 23

Dijkstra's Algorithm

Sec 24.3

 

Jul 26

Greedy Algorithms / Matroids

Sec 16.4

 

Jul 27

Task scheduling

Sec 16.5

 

Jul 28

Huffman Codes

Sec 16.3

 

Jul 29

Matrix-chain multiplication

Sec 15.3

 

Jul 30

Solutions for Homework 3

   

Aug 02

Review for the midterm

   

Aug 03

Midterm

   

Aug 04

Longest common subsequence

Sec 15.4

 

Aug 05

Sequence alignment
0-1 Knapsack

   

Aug 06

Optimal Binary Seach Trees
All-pairs shortest path

Sec 15.5
Sec 25.1

 

Aug 09

Floyd-Warshall
Toothpick Game

Sec 25.2

Toothpick Game

Aug 10

NP-completeness

Sec 34.1-2

NP-completeness 1

Aug 11

Reductions

Sec 34.3

 

Aug 12

NP-complete problems

Sec 34.5

 

Aug 13

More NP-complete problems

Sec 34.5

NP-completeness 2

Aug 16

Approximation Algorithms
Vertex Cover

Sec 35.0-1

 

Aug 17

Traveling-salesman problem

Sec 35.2

 

Aug 18

k-center

   

Aug 19

Review

   

Aug 20

Final

   

Acknowledgments

 

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

Also I would like to thank Dr. Khuller for letting me use some of his handouts for the class.