Topic Readings Due Friday
1: January 16 Overview; Fibonacci numbers Notes, Sections 1-3; CLR, Chapters 2, 7 .
2: January 18 Algorithm design; recurrences Notes, Sections 4-7; CLR, Chapters 3, 4 Homework 1
3: January 23 Graphs and trees Notes, Sections 8-10; CLR, Section 23.1 .
4: January 25 DFS, topological sort Notes, Sections 11-14; CLR, Sections 23.3, 23.4 Homework 2
5: January 30 Connected components Notes, Section 15; CLR, Section 23.5 .
6: February 1 BFS, Dijkstra's algorithm Notes, Sections 16, 17; CLR, Sections 23.2, 25.1, 25.2 Homework 3
7: February 6 Bellman-Ford algorithm Notes, Sections 18-21; CLR, Sections 25.3, 25.4 .
8: February 8 Minimum spanning trees Notes, Section 22; CLR, Chapter 24 Homework 4
9: February 13 Disjoint sets Notes, Sections 23-25; CLR, Chapter 22 .
10: February 15 MIDTERM I covers Lectures 1-8 (no, not 9) Homework 5
11: February 20 Huffman coding Notes, Sections 26, 27; CLR, Sections 17.1-17.3 .
12: February 22 Dynamic programming I Notes, Sections 28-31; CLR, Sections 16.1-16.3 Homework 6
13: February 27 Dynamic programming II Notes, Sections 32, 33; CLR, Sections 26.1, 26.2 .
14: March 1 Linear programming I Notes, Sections 34, 35 Homework 7
15: March 6 Linear programming II Notes, Sections 36-38 .
16: March 8 Network flows Notes, Sections 39-43; CLR, Sections 27.1-27.3 Homework 8
17: March 13 NP-completeness I Notes, Sections 44-47; CLR, Sections 36.1-36.3 .
18: March 15 NP-completeness II Notes, Section 48 Project 1
19: March 20 NP-completeness III Notes, Sections 49, 50; CLR, Sections 36.4, 36.5 .
20: March 22 NP-completeness IV Notes, Section 51; CLR, Section 37.1 Homework 9
March 26-30 Spring Recess . .
21: April 3 NP-completeness V Notes, Section 51; CLR, Section 37.2 .
22: April 5 Matrix multiplication I Notes, Sections 52-55; CLR, Sections 31.1, 31.2 Homework 10
23: April 10 Matrix multiplication II Notes, Sections 56-59; CLR, Sections 31.4, 31.5 .
24: April 12 MIDTERM II covers Lectures 1-21 (no, not 22 or 23) Homework 11
25: April 17 Fourier transforms Notes, Sections 60-62; CLR, Sections 32.1, 32.2 .
26: April 19 Computational geometry I CLR Sections 35.1, 35.2 Homework 12
27: April 24 Computational geometry II CLR Section 35.3 .
28: April 26 Number theory I Notes, Sections 65-69; CLR, Sections 33.1, 33.2 Homework 13
29: May 1 Number theory II Notes, Sections 70-74; CLR, Sections 33.3, 33.4 .
30: May 3 Number theory III Notes, Sections 75, 76; CLR, Sections 33.5-33.7 Homework 14
31: May 8 Review . .