Syllabus: 15-750 Spring 2007

This page is still under construction.

For the moment this is the syllabus from Spring 2006. There will be a large overlap this last year. There are more topics to be added, and the number of lectures and order of the topics may change.

Lec. Day DW Topic Reading Homework Lecturer
Jan 15 M Martin Luther King Day No Class GM
1 Jan 17 W Introduction and Strassen's Algorithm Lec 1 Kz HW 0 out GM
2 Jan 19 F Binomial Heaps Lec 5 Kz, Lec 8 Kz, Chap 19 CLRS GM
3 Jan 22 M Fibonacci Heaps Lec 9 Kz, Chap 20 CLRS GM
4 Jan 24 W Size of Fibonacci Trees and BST introduction Lec 12 Kz, Chap 12-14 CLRS GM
5 Jan 26 F Treaps (Random Search Trees) Lec 13 Kz GM
6 Jan 29 M Splay Trees Lec 13 Kz HW1 out GM
7 Jan 31 W Splay Trees HW0 due GM
8 Feb 2 F Dynamic Programming: LCS and Picket Fence Painting Chap 15 CLRS GM
9 Feb 5 M Dynamic Programming: Uniquely Decipherable Codes Handout GM
10 Feb 7 W Computational Geometry: Introduction and Sweep Line Intro Sweep-Line GM
11 Feb 9 F Sorting, Convex Hull, and 2D Random Incremental Convex Hull Handout HW1 due HW2 out GM
12 Feb 12 M Linear Programming: 2D Random Incremental Handout GM
13 Feb 14 W More Linear Programming CLRS Chap 29 GM
14 Feb 16 F Max Flow Introduction Kz 16 GM
15 Feb 19 M Max Flow Kz 17 HW2 due -- SIAM workshop DS
16 Feb 21 W Depth First Search Lec 4 Kz, Chap 22 CLRS GM
17 Feb 23 F Review Session DG
18 Feb 26 M Midterm I
19 Feb 28 W Strongly Connected Components Sleator's Notes Baase HW3 out GM
20 Mar 2 F FFT Lec 35 Kz, Chap 30 CLRS GM
21 Mar 5 M Simple String Matching Algorithms Chap 32 CLRS GM
22 Mar 7 W FFT and Approximate String Matching Handout1 Handout2 HW3 due; HW4 out GM
Mar 9 F Mid-Semester Break
Mar 12 M Spring Break
Mar 14 W Spring Break
Mar 16 F Spring Break
23 Mar 19 M Resistive Model of a Graph Doyle and Snell GM
24 Mar 21 W Random Walks HW4 due GM
25 Mar 23 F No Class: CSD Open House
26 Mar 26 M Solving Linear Systems Chap 28 CLRS GM
27 Mar 28 W Iterative Methods for Solving Linear Systems HW5 out GM
28 Mar 30 F Parallel Algorithms Chap2 Synthesis of Parallel Algorithms GM
29 Apr 2 M Parallel Algorithms GM
30 Apr 4 W Parallel Algorithms GM
31 Apr 6 F Multiplicative Weight Update Algorithms Avrim Blum's Notes and this Survey Paper HW5 due DG
32 Apr 9 M Parallel Maximal Independent Set; Midterm Review W5409 8PM Lecs 36 and 37 Kz GM
33 Apr 11 W Midterm II CESC Conference
34 Apr 13 F Planar Graph Separators Lec 15 Kz related paper GM
35 Apr 16 M Representing Planar Graphs Lec 14 Kz Todd's Talk GM
36 Apr 18 W Competitive Algorithms Sleators Notes HW6 out GM
Apr 20 F Spring Carnival
37 Apr 23 M Review Midterm 2 DG and DS
38 Apr 25 W Competitive Algorithms Sleators Notes; Part 2 GM
39 Apr 27 F NP-Completeness Lec 21-25 Kz, Chap 34 CLRS HW6 due GM
40 Apr 30 M NP-Completeness GM
41 May 2 W NP-Completeness GM
42 May 4 F Approximation Algorithms CRLS Chap 35 GM
May 9 W Final Review 1:30-3 PM Wean 5409 DG GM DS
May 10 Th Final 1-4PM SH 125

Last modified: Mon May 7 12:34:03 EDT 2007