Note: Home works should be dropped off in the drop-box on Taylor breezeway.
Please be sure to clearly mark the course number (CS388G) on the front page.
Due date for HW 1-4 is on Thursday at 3 pm in the week following the
week the HW is handed out.
HW5 is due on Wednesday at 3 pm during Thanksgiving week.
| Wed, Aug 27 | Introduction; Strassen's algorithm; divide and conquer; recurrences | Sec 28.2, Ch 4 |
| Mon, Sep 1 | LABOR DAY, no class | No class |
| Wed, Sep 3 | Linear-time selection | Ch 9 |
| Mon, Sep 8 | Randomized algorithms; elementary probability; randomized selection and Quicksort |
Ch 5, 9
HW1 out |
| Wed, Sep 10 | Coupon collector problem, Markov's inequality, Chebyshev's inequality |
Ch 5
Quiz 1 |
| Mon, Sep 15 | Chernoff bounds; high-probability bounds for Quicksort | Ch 7 |
| Wed, Sep 17 | Hashing with chaining; universal hashing; perfect hashing |
Ch 11
HW1 due 3 pm Sep 18 |
| Mon, Sep 22 | Amortized analysis; table expansion and contraction |
Ch 17
HW2 out |
| Wed, Sep 24 | Search trees; splay tree | Ch 12 |
| Mon, Sep 29 | Splay tree | Quiz 2 |
| Wed, Oct 1 | Mergeable heaps; binomial heap |
Ch 19, 20
HW2 due 3 pm Oct 2 |
| Mon, Oct 6 | Fibonacci heap | Ch 20 |
| Wed, Oct 8 | TEST 1 | |
| Mon, Oct 13 | Disjoint sets |
Ch 21
HW3 out |
| Wed, Oct 15 | Alpha technique |
|
| Mon, Oct 20 | Tight analysis of disjoint sets | Quiz 3 |
| Wed, Oct 22 | Maximum flow |
Ch 26
HW3 due 3 pm on Oct 23 |
| Fri, Oct 24 | Maximum flow (Make-up class for Nov 26) | Ch 26 |
| Mon, Oct 27 | Maximum flow |
Ch 26
HW4 out |
| Wed, Oct 29 | Maximum flow and matchings | Ch 26 |
| Mon, Nov 3 | NP-completeness and reductions |
Ch 34
Quiz 4 |
| Wed, Nov 5 | Cook's theorem; approximation algorithms |
Ch 35
HW4 due 3 pm on Nov 6 |
| Mon, Nov 10 | Approximation algorithms; start LP | Ch 35, 29 |
| Wed, Nov 12 | TEST 2 | |
| Mon, Nov 17 | Linear Programming |
Ch 29
HW5 out |
| Wed, Nov 19 | Simplex LP algorithm | Ch 29 |
| Mon, Nov 24 | Online algorithms |
Quiz 5
|
| Wed, Nov 26 | No class, class moved to Oct 24; HW5 DUE TODAY | HW5 due 3 pm today |
| Mon, Dec 1 | Selected topics: Cache-oblivious algorithms, DFT, matroids, etc. | |
| Wed, Dec 3 | Selected topics |
|
| Fri, Nov 5, 4-6 pm | TEST 3 in WEL 2.256 (regular classroom), 4-6 pm |