15-451 Fall 2000 Schedule

TOPICS                                           Date             Chapters
-------------------------------------------------------------------------
   Fundamentals

1.    Course intro, algorithm examples           08/29            1, 2, 9.5
2.    Math Foundations: asymptotics, recurrences 08/31            3, 5

   Sorting and Order Statistics
3.    Randomized quicksort, Probability intro    09/05            6.4
4.    Linear-time Selection (rand and det)       09/07            6.5
5.    Sorting Lower bounds (det and rand)        09/12            
   
   Data Structures
6.    Balanced search trees: B-trees             09/14            4.3.3
7.    Amortized Analysis                         09/19
8.    Balanced search trees: Splay trees         09/21
9.    Radix sort, tries, and **QUIZ**            09/26		  
10.   Hashing: Universal and Perfect             09/28            4.4
11.   Hashing (contd)                            10/03

   Dynamic Programming
12.   Dynamic Programming & memoizing            10/05		  5.10,6.11

   Graph Algorithms
13.   Basic Graph Algorithms                     10/10		  7.1-7.8
14.   Fibonacci heaps                            10/12		  4.3.2
15.   **MIDTERM**                                10/17            
16.   Graph Algs (contd)                         10/19            
17.   Union-Find                                 10/24            4.5
18.   Max Flow and Matchings                     10/26            7.10,7.11
19.   Max Flow (contd)                           10/31            
20.   Linear Programming                         11/02            10.3

   Computational Complexity
21.   NP-Completeness                            11/07            11
22.   NP-Completeness (contd) + **QUIZ**         11/09            
   
   Numerical Algorithms
23.   Fast Fourier Transform                     11/14            9.4,9.6
24.   Crypto and number-theoretic algs           11/16            9.1-9.3
25.   (contd)                                    11/21            

   Modern Topics
26.   Zero-Knowledge proofs                      11/28
27.   Approximation Algorithms                   11/30            11.5.2
28.   On-line Algorithms                         12/05            
29.   Machine learning algorithms                12/07
30.   Summary                                    12/12

Final exam is Mon Dec 18 08:30a.m.-11:30a.m in PH 100.
Notes:
  1. Each quiz will be 1/2 hour long. The midterm will take the full class period.