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

Handouts

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.