| Day |
Date |
Instr |
Topics Covered |
Notes and Readings |
| Tue |
Jan 15 |
Gary |
Lecture 1: Introduction Strassen |
ClassNotes |
| Wed |
Jan 16 |
|
Recitation 1 - Recurrences, Big-Oh, Strassen space — Assignment 1 out |
recitation notes |
| Thu |
Jan 17 |
Gary |
Lecture 2: Dynamic Programming: Optimal BST |
ClassNotes ClassNotes-II |
| Tue |
Jan 22 |
Gary |
Lecture 3: Dynamic programing II |
ClassNotes |
| Wed |
Jan 23 |
|
Recitation 2 - TBD — |
|
| Thu |
Jan 24 |
Gary |
Lecture 4: BST, Treaps and QuickSort — Assignment 1 Due |
ClassNotes - Slides Kozen Chap 13 Assigment 2
|
| Tue |
Jan 29 |
Danny |
Lecture 5: Amortized Analysis |
Notes1 Notes2 Notes3 |
| Wed |
Jan 30 |
|
Recitation 3 - TBD — |
|
| Thu |
Jan 31 |
Danny |
Lecture 6: Splay Trees |
lecture notes |
| Tue |
Feb 05 |
Danny |
Lecture 7: Graphs I (DFS) |
DFS, Strong Components Bi-Connected Components |
| Wed |
Feb 06 |
|
Recitation 4 - TBD — |
|
| Thu |
Feb 07 |
Danny |
Lecture 8: Graphs II (Fibonacci Heaps) |
Notes |
| Tue |
Feb 12 |
Danny |
Lecture 9: Graphs III (Matchings) |
Notes |
| Wed |
Feb 13 |
|
Recitation 5 - TBD — |
|
| Thu |
Feb 14 |
Danny |
Lecture 10: All Pairs Shortest Paths |
Bellman-Ford, Floyd-Warshall Dijkstra |
| Tue |
Feb 19 |
Gary |
Lecture 11: Computational Geometry I: Intro + Sweepline |
ClassNotes |
| Wed |
Feb 20 |
|
Recitation 6 - Quiz and short discussion |
|
| Thu |
Feb 21 |
Gary |
Lecture 12: Computational Geometry II: 2D-LP + Backwards Analysis |
ClassNotes BKOS Chap 4 |
| Tue |
Feb 26 |
Gary |
Lecture 13: Computational Geometry III: 2D Convex Hull |
ClassNotes BKOS Chap 1 Lecture Notes |
| Wed |
Feb 27 |
|
Recitation 7 - Review LP and Convex Hull and Min Radius containing discus |
|
| Thu |
Feb 28 |
Gary |
Lecture 14: Computational Geometry IV: Closest Pair using Hashing |
ClassNotes Har-Peled Chap 1 |
| Tue |
Mar 05 |
TAs |
Lecture 15: Midterm Review |
|
| Wed |
Mar 06 |
|
Recitation 8 - TBD — |
|
| Thu |
Mar 07 |
|
Midterm - No Class |
|
| Tue |
Mar 12 |
|
Spring Break - No Class |
|
| Wed |
Mar 13 |
|
Spring Break - No Class |
|
| Thu |
Mar 14 |
|
Spring Break - No Class |
|
| Tue |
Mar 19 |
Danny |
Lecture 16: Maximum Flow I |
lecture notes |
| Wed |
Mar 20 |
|
Recitation 9 - The image foreground background problem |
Kleinberg-Tardos 7.10 |
| Thu |
Mar 21 |
Danny |
Lecture 17: Maximum Flow II |
lecture notes Min-Cost Flow |
| Tue |
Mar 26 |
Gary |
Lecture 18: Linear Programming I |
ClassNotes Readings: CLRS Chaper 29 Avrim's notes |
| Wed |
Mar 27 |
|
Recitation 10 - TBD — |
|
| Thu |
Mar 28 |
Gary |
Lecture 19: Linear Programming Duality II |
ClassNotes :: Trevisan Chap 5,6,15 :: Gordon's Notes
|
| Tue |
Apr 02 |
Gary |
Lecture 20: Parallel Algorithms I |
ClassNotes |
| Wed |
Apr 03 |
|
Recitation 11 - TBD — |
|
| Thu |
Apr 04 |
Gary |
Lecture 21: Parallel Algorithms II: Prefix Sum and Apps |
ClassNotes :: Reid-Miller Chap 2 :: Blelloch Prefix Sum |
| Tue |
Apr 09 |
Gary |
Lecture 22: Parallel Algorithms III: List Ranking |
ClassNotes |
| Wed |
Apr 10 |
|
Recitation 12 - TBD — |
|
| Thu |
Apr 11 |
Gary |
Lecture 23: Parallel Algorithms IV: Parallel Tree Contraction |
ClassNotes |
| Tue |
Apr 16 |
Danny |
Lecture 24: Competitive Analysis I |
lecture notes |
| Wed |
Apr 17 |
|
Recitation 13 - TBD — |
|
| Thu |
Apr 18 |
|
Spring Carnival - No Class |
|
| Tue |
Apr 23 |
Danny |
Lecture 25: Competitive Analysis II |
lecture notes |
| Wed |
Apr 24 |
|
Recitation 14 - TBD — |
|
| Thu |
Apr 25 |
Danny |
Lecture 26: String Matching -- KMP and Karp-Rabin |
lecture notes |
| Tue |
Apr 30 |
Danny |
Lecture 27: Suffix Arrays and Suffix Trees |
lecture notes with figures |
| Wed |
May 01 |
|
Recitation 15 - TBD — |
|
| Thu |
May 02 |
Danny |
Lecture 28: Aproximation Algorithms -- set cover, shortest superstring |
lecture notes |
| Tue |
May 07 |
|
Final: 8:30-11:30AM, DH A302 - No Class |
|
| Thu |
May 09 |
Danny |
Lecture 29: Review Session, Sunday May 5, 7pm. Ignore the date to the left. |
last fall's final |