Here you can view or download the notes (postscript or pdf files) that we use in class. DO NOT depend solely on these notes as many details are missing. You should read the textbook and take notes in class.

	Date	Topics	Files	Reading
Introduction and Review.	Sept 02	Introduction and Review	ps pdf	Chapter 1.1-4.2
Divide and Conquer.	Sept 04	Maximum contiguous subarray problem	ps
	Sept 04	Polynomial multiplication	ps
	Sept 09	Randomized selection and randomized quicksort	ps	Chapter 7
	Sept 11	Deterministic linear-time selection	ps pdf	Chapter 9.2, 9.3
Graph Algorithms.	Sept 16, Sept 18	Depth-first search and its applications	ps pdf	Chapter 22.3
	Sept 18, Sept 23	Minimum spanning tree and Prim's algorithm	ps pdf	Chapter 23
	Sept 25	Kruskal's algorithm	ps pdf	Chapter 23
	Sept 25	Disjoint set union and find	ps pdf	Chapter 21.3
	Sept 30	Dijktra's algorithm	ps pdf	Chapter 24.3
Dynamic Programming.	Oct 02, Oct 07	0-1 Knapsack	ps pdf
	Oct 09	Matrix chain multiplication	ps pdf written notes (jpeg) 1 2 3 4	Chapter 15.2, 15.3
	Oct 14, Oct 16	All-pairs shortest paths	ps pdf written notes (jpeg) 1 2 3 4 5 6 7 8	Chapter 25.1, 25.2
Greedy Algorithms.	Oct 21	Fractional Knapsack	ps pdf written notes (jpeg) 1 2 3 4	Chapter 16.2
	Oct 23, Oct 28	Huffman coding	ps pdf written notes ps pdf	Chapter 16.3
More Algorithms.	Oct 30, Nov 04	String Matching	ps pdf written notes ps pdf	Chapter 32.1, 32.4
NP-completeness.	Nov 06, Nov 11, Nov 13	Introduction to NP	ps pdf	Chapter 34.1, 34.2
	Nov 18, Nov 20, Nov 25	Polynomial time reduction	ps pdf written notes (jpeg) 1 2 3 4	Chapter 34.3, 34.5
	Nov 27, Dec 2	Approximate algorithms	ps pdf	Chapter 35.1, 35.2