![[Rice University]](http://www.cs.rice.edu/CS/images/ricelogo.gif)
|
|
COMP 482 / ELEC 420: Design and Analysis of Algorithms |
In this course, you should deepen your knowledge about algorithm analysis. Furthermore, you will use those skills while exploring a number of important classes of algorithms and data structures. You will also examine the limits of practical computation, in the form of NP-completeness.
Course administrative information
| Assignments Due | Date | Topic | CLRS Reading | ||
|---|---|---|---|---|---|
| T | 26 | Aug | Course overview | 1-2 | |
| Th | 28 | Algorithm Analysis | |||
| Asymptotic notation & concepts | 3.1 | ||||
| T | 2 | Sep | |||
| Math background | A,B,3.2 | ||||
| 1 (sol'n) | Th | 4 | Recurrences | 4 | |
| T | 9 | ||||
| Th | 11 | Probabilistic analysis | 5 | ||
| 2 (sol'n) | T | 16 | Sorting & Sorting-like Algorithms | ||
| Sorting | 6-8 | ||||
| Th | 18 | Order statistics | 9 | ||
| Convex Hull | 33.1,33.3 | ||||
| 3 (sol'n) | T | 23 | |||
| Th | 25 | Tree-based Data Structures | |||
| Tries | |||||
| 4 (sol'n) | T | 30 | Skip Lists | 10,12,13, This paper | |
| Project deadline 1 | Th | 4 | Oct | ||
| T | 7 | Amortization & Splay trees | 17,Handout | ||
|
5
(sol'n) Project deadline 2 |
Th | 9 | |||
| Heaps | 19-20 | ||||
| T | 14 | Mid-semester holiday | |||
| Th | 16 | Heaps | 19-20 | ||
| 6 (sol'n) | T | 21 | Optimization & Other Numerical Algorithms | ||
| Network flow | 26 | ||||
| Exam 1 (sol'n) | Th | 23 | |||
| T | 28 | ||||
| Th | 30 | Linear Programming | 29 | ||
|
7
(sol'n) Project deadline 3 |
T | 4 | Nov | ||
| Th | 6 | ||||
| Fast Fourier Transform | 30 | ||||
| 8 (sol'n) | T | 11 | |||
| Th | 13 | ||||
| NP-Completeness | |||||
| NP-completeness | 34,Handout | ||||
| 9 (sol'n) | T | 18 | |||
| Th | 20 | ||||
|
10
(sol'n) Project deadline 4 |
T | 25 | |||
| Approximation | 35 | ||||
| Th | 27 | Thanksgiving holiday | |||
| T | 2 | Dec | Approximation | 35 | |
| Th | 4 | ||||
| 11 (sol'n) | F | 5 | Winter holiday | ||
| Exam 2 (sol'n) | W | 17 | |||