CS124 Course Outline

Spring 1997
Harvard University

Jan 29 (W)	Administrivia.  
		Introduction to analysis of algorithms: 
		insertion sort, mergesort, O-notation	
		Reading: Chapter 1, Section 2.2

Feb 3 (M)	Asymptotic notation.
		Divide and conquer: quicksort, Strassen's algorithm,
		recurrences.
		Reading: Sections 2.1, 8.1-8.2,31.2.

Feb 5 (W)	Recurrences, summations.
		Reading: Chapters 3-4, excluding Section 4.4.
		Problem Set 1 Handed out.

Feb 10 (M)	Randomized algorithms; randomized quicksort, probability.
		Reading: Sections 6.1-6.3, 8.3-8.4

Feb 12 (W)	Median, order statistics.
		Reading: Chapter 10.
		Problem Set 2 Handed out.

		*** Feb 14 (F)	 Problem Set 1 Due ***

Feb 17 (M)	Holiday-President's Day
	
Feb 19 (W)	Sorting; heapsort, priority queues, dynamic sets,
		amortized cost analysis.
		Reading: Chapter 7.
		Problem Set 3 Handed out.

		*** Feb 21 (F)	 Problem Set 2 Due ***

Feb 24 (M)	Sorting: lower bounds, counting sort, radix sort.
		Reading: Chapter 9, excluding 9.4

Feb 26 (W)	Data structures: hashing, collision resolution, chaining,
		universal hashing.
		Reading: Chapter 12, excluding Section 12.4
		Problem Set 4 Handed out.

		*** Feb 28 (F)	 Problem Set 3 Due ***

Mar 3 (M)	Data structures: binary search trees, tree walks, 
		relation to quicksort.
		Reading: Chapter 13, excluding Section 13.4.

Mar 5 (W)	Data structures: red-black trees, rotations, insertion, 
		deletion.
		Reading: Chapter 14.
		Problem Set 5 Handed out.

		*** Mar 7 (F)	 Problem Set 4 Due ***

Mar 10 (M)	Dynamic programming: longest common subsequence. 
		Reading: Chapter 16, excluding Section 16.4. Section 23.1.

Mar 12 (W)	Dynamic programming (Cont.) and review.
		Problem Set 6 Handed out.
	
		*** Mar 14 (F)	 Problem Set 5 Due ***

Mar 17 (M)	Midterm exam

Mar 19 (W)	Greedy algorithms: activity selection, 
		minimum-spanning tree (Prim's algorithm)
		Reading: Sections 17.1-17.3, Chapter 24.
		Problem Set 7 Handed out.

		*** Mar 21 (F)	 Problem Set 6 Due ***

Mar 22-30	Spring Recess

Mar 31 (M)	Minimum spanning tree (Kruskal's algorithm); 
		disjoint-set union; amortized analysis.
		Reading: Sections 24.2, 22.1-22.3, 18.1-18.2.

Apr 2 (W)	Graph algorithms: depth-first search, topological sort, 
		breadth-first-search.
		Reading: Sections 23.2-23.4.
		Problem Set 8 Handed out.

		*** Apr 4 (F)	 Problem Set 7 Due ***

Apr 7 (M)	Graph algorithms: Single-source shortest paths, 
		Dijkstra's algorithm, Bellman-Ford algorithm, dag shortest paths.
		Reading: Chapter 25.
	
Apr 9 (W)	Graph algorithms: all-pairs shortest paths, matrix multiplication, 
		Floyd-Warshall algorithm, difference constraints.
		Reading: Chapter 26, excluding Section 26.4.
		Problem Set 9: Challenge Assignment 1 Handed out.

		*** Apr 11 (F)	 Problem Set 8 Due ***

Apr 14 (M)	Network flow
		Reading: Sections 27.1-27.2

Apr 16 (W)	Network flow: augmenting paths, residue graph, max-flow min-cut, 
		Ford-Fulerson
		Reading: Sections 27.2-27.3

Apr 21 (M)	Network flow (Cont.)
		
Apr 23 (W)	Sorting networks
		Reading: Chapter 28.
		Problem Set 10: Challenge Assignment 2 Handed out.

Apr 28 (M)	Wrap-up and Review
		*** Apr 28 (M)	 Problem Set 9: Challenge Assignment 1 Due ***

Apr 30 (W)	PS9 Presentations by Students

May 3-14	Reading Period
		*** May 5 (M)	 Problem Set 10: Challenge Assignment 2 Due ***

May 16 (F)      Final Exam at 2:15pm Jefferson 250