![[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 concepts & useful math | 3.1,A,B,3.2 | ||||
| T | 2 | Sep | |||
| 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 | |||
| Skip Lists | 10,12,13, This paper | ||||
| 4 (sol'n) | T | 30 | |||
| Project deadline 1 | Th | 4 | Oct | Amortization & Splay trees | 17,Handout |
| T | 7 | ||||
| Heaps | 19-20 | ||||
|
5
(sol'n) Project deadline 2 |
Th | 9 | |||
| T | 14 | Mid-semester holiday | |||
| Th | 16 | String Algorithms | |||
| String Matching | 32 | ||||
| 6 (sol'n) | T | 21 | Tries | ||
| Exam 1 (sol'n) | Th | 23 | Optimization | ||
| Network flow | 26 | ||||
| T | 28 | ||||
| Th | 30 | ||||
|
7
(sol'n) Project deadline 3 |
T | 4 | Nov | Linear Programming | 29 |
| Th | 6 | ||||
| T | 11 | ||||
| 8 (sol'n) | Th | 13 | NP-Completeness | ||
| NP-completeness | 34,Handout | ||||
| T | 18 | ||||
| Th | 20 | ||||
| 9 (sol'n) | T | 25 | |||
| Approximation | 35 | ||||
| Th | 27 | Thanksgiving holiday | |||
| Project deadline 4 | T | 2 | Dec | Approximation | 35 |
| Th | 4 | ||||
| 10 (sol'n) | F | 5 | Finals & Winter holiday | ||
| Exam 2 (sol'n) | W | 17 | |||