[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 concepts & useful math 3.1,A,B,3.2
T 2 Sep
1 (sol'n) Th 4 Recurrences 4
  T 9
Probabilistic analysis 5
Th 11
Sorting & Sorting-like Algorithms
Sorting 6-8
T 16 Hurricane Ike aftermath
Th 18 Sorting (continued) 6-8
2 (sol'n) T 23
Order statistics 9
Convex Hull 33.1,33.3
  Th 25
3 (sol'n) T 30 Tree-based Data Structures
Skip Lists 10,12,13, This paper
4 (sol'n)
Project deadline 1
Th 2 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 Heaps (continued) 19-20
String Algorithms
String Matching 32
6 (sol'n) T 21
Exam 1 (sol'n) Th 23 Tries  
  T 28 Optimization
Network flow 26
Th 30
7 (sol'n)
Project deadline 3
T 4 Nov
Linear Programming 29
  Th 6
8 (sol'n) T 11
  Th 13 NP-Completeness
NP-completeness 34,Handout
9 (sol'n) T 18
  Th 20
10 (sol'n) T 25
Approximation 35
  Th 27 Thanksgiving holiday
Project deadline 4 T 2 Dec Approximation 35
  Th 4
11 (sol'n) F 5 Finals & Winter holiday
Exam 2 (sol'n) W 17