Class | Date | Day | Topic | Reading | Activity | Lecturer |
1 | 01/16 | Tue | Overview,Example | KS | ||
2 | 01/18 | Thu | Asymptotics, Recurrences | 1-5 | Asst 1 Ready | KS |
3 | 01/23 | Tue | Probabilistic analysis | 6, 8 | RB | |
4 | 01/25 | Thu | Selection | 10 | RB | |
5 | 01/30 | Tue | Lower Bounds | 9.1 | Asst 1 Due | KS |
6 | 02/01 | Thu | Balanced Trees | 11, 13, 14 | Asst 2 Ready | RB |
7 | 02/06 | Tue | Amortized Analysis | Quiz 1 | TA | |
8 | 02/08 | Thu | Splay Trees | RB | ||
9 | 02/13 | Tue | Radix Structures | Asst 2 Due | RB | |
10 | 02/15 | Thu | Hashing 1 | 12 | Asst 3 Ready | RB |
11 | 02/20 | Tue | Hashing 2 | RB | ||
12 | 02/22 | Thu | Dynamic Programming | 16 | KS | |
13 | 02/27 | Tue | Union-Find | 22 | Asst 3 Due | RB |
14 | 03/01 | Thu | Graph 1: Minimum Spanning Tree, Single-Source Shortest Path | 24, 25 | Asst 4 Ready | RB |
15 | 03/06 | Tue | Midterm | |||
03/08 | Thu | Mid-Semester Break | ||||
16 | 03/13 | Tue | Graph Exploration, Semirings | 23 | Asst 4 Due | KS |
17 | 03/15 | Thu | Strongly Connected Components | 26 | Asst 5 Ready | KS |
18 | 03/20 | Tue | Max Flow | 27 | KS | |
19 | 03/22 | Thu | Flow 2, Linear Programming | KS | ||
03/27 | Tue | Spring Break | ||||
03/29 | Thu | Spring Break | ||||
20 | 04/03 | Tue | NP 1 | 36 | Asst 5 Due | KS |
21 | 04/05 | Thu | NP 2 | Asst 6 Ready | KS | |
22 | 04/10 | Tue | Turing Machines and Cook's Theorem | Quiz 2 | RB | |
23 | 04/12 | Thu | Approximation Algorithms | 37 | RB | |
24 | 04/17 | Tue | Binary Decision Diagrams | Asst 6 Due | RB | |
25 | 04/19 | Thu | Number Theory 1 | 33 | Asst 7 Ready | KS |
26 | 04/24 | Tue | Number Theory 2 | KS | ||
27 | 04/26 | Thu | FFT | 32 | KS | |
28 | 05/01 | Tue | State Machines | Asst 7 Due | KS | |
05/03 | Thu | Review | RB |
The reading assingments all refer to Cormen, Leiserson, Rivest, "Introduction to Algorithms".
Lecture | T, Th | 12:00-13:20 | DH 2210 | R. Bryant/K. Sutner |
Section A | W | 12:30-13:20 | Scaife 220 | D. Pelleg |
Section B | W | 13:30-14:20 | Scaife 220 | R. Punkunus |
Section C | W | 14:30-15:20 | Scaife 220 | S. Chaki |
Section D | W | 15:30-16:20 | BH 235 A | RB/KS |
See Personnel for office hours, email addresses, and such like.