Syllabus: 15-750 Spring 2008

This page is still under construction.

For the moment this is the syllabus from Spring 2007. 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
1 Jan 14 M Introduction and Strassen's Algorithm Lec 1 Kz HW0 out GM
2 Jan 16 W Binomial Heaps Lec 5 Kz, Lec 8 Kz, Chap 19 CLRS GM
3 Jan 18 F Fibonacci Heaps Lec 9 Kz, Chap 20 CLRS GM
Jan 21 M Martin Luther King Day No Class
4 Jan 23 W Size of Fibonacci Trees and BST introduction Chap 12-14 CLRS GM
5 Jan 25 F Splay Trees Lec 12 Kz HW0 due HW1 out GM
6 Jan 28 M Splay Trees GM
7 Jan 30 W Treaps (Random Search Trees) Lec 13 Kz GM
8 Feb 1 F Dynamic Programming: LCS and Picket Fence Painting Chap 15 CLRS GM
9 Feb 4 M Dynamic Programming: Uniquely Decipherable Codes Handout GM
Feb 6 W No Class
10 Feb 8 F Computational Geometry: Introduction and Sweep Line Intro Sweep-Line HW1 due HW2 out GM
11 Feb 11 M Sorting, Convex Hull, and 2D Random Incremental Convex Hull Handout GM
12 Feb 13 W Linear Programming: 2D Random Incremental Handout GM
13 Feb 15 F Analysis of 2D Random Incremental Algorithm for LP GM
14 Feb 18 M More Linear Programming CLRS Chap 29, presentation, notes on LP AKS
15 Feb 20 W Max Flow Introduction Kz 16 GM
16 Feb 22 F Max Flow Lec 17 Kz HW2 due GM
17 Feb 25 M Review Session YW
18 Feb 27 W Midterm I HW3 out
19 Feb 29 F DFS Intro Class-Notes GM
20 Mar 3 M Strongly Connected Components Class-Notes Sleator's Notes Baase GM
21 Mar 5 F FFT Class-Notes Lec 35 Kz, Chap 30 CLRS GM
Mar 7 F Spring Break
Mar 10 M Spring Break
Mar 12 W Spring Break
Mar 14 F Spring Break
22 Mar 17 M Simple String Matching Algorithms Chap 32 CLRS Class-Notes HW3 due; HW4 out GM
23 Mar 19 W FFT and Approximate String Matching Handout1 Handout2 Class-Notes GM
24 Mar 21 F Resistive Model of a Graph Class-Notes Doyle and Snell GM
25 Mar 24 M Random Walks and Electricity Class-Notes GM
26 Mar 26 W Solving Linear Systems, Direct Methods Chap 28 CLRS Class-Notes GM
27 Mar 28 F No Class: CSD Open House GM
28 Mar 31 M Linear System Solvers: Iterative Class-Notes GM
29 Apr 2 W Parallel Algorithms: Parallel models, Work and time, Prefix-sum, List-Ranking Class-Notes Chap1 from Synthesis of Parallel Algorithms HW4 due; HW5 out GM
30 Apr 4 F Parallel Algorithms: More List-ranking, Parallel Tree Contraction Class-Notes Chap2 SPA GM
31 Apr 7 M Parallel Maximal Independent Set Class-Notes Lec 36 and 37 Kz GM
32 Apr 9 W Parallel Maximal Independent Set GM
Apr 10 Th Midterm Review W5409 8PM Wean 5409 AS YW
33 Apr 11 F Midterm II CSD Retreat
34 Apr 14 M Planar Graph Separators Class-Notes Lec 15 Kz related paper GM
35 Apr 16 W Representing Planar Graphs Class-Notes Lec 14 Kz; Todd's Talk HW5 due; HW6 out GM
Apr 18 F Spring Carnival
36 Apr 21 M Planar Graph Separators; NP-Completeness Class-Notes Lec 21-25 Kz, Chap 34 CLRS GM
37 Apr 23 W NP-Completeness Class-Notes GM
38 Apr 25 F NP-Completeness Class-Notes GM
39 Apr 28 M Competitive Algorithms Class-Notes Sleator's Notes ARVO Conference AS
40 April 30 W Competitive Algorithms Class-Notes Sleator's Notes; Part 2 GM
41 May 2 F Last class: Approximation Algorithms Class-Notes HW6 due GM
May 6 Tues Final Review at 8PM Location: Wean 5409 AS YW GM
May 8 Th Final 08:30am-11:30am Location: Hamerschlag Hall B103

Last modified: Wed Apr 9 20:52:31 EDT 2008