[Rice University]

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

Schedule
(Tentative and approximate. Will be updated throughout the semester.)
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