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 |