15-451 Spring 2007 Schedule
"CLRS", "DPV" and "KT" columns show readings in the respective texts.
Schedule still subject to change. Note quiz date change!
Date
Topic
CLRS
DPV
KT
Due
1.
01/16
Intro & Admin. Karatsuba/Strassen.
2.1,2.5
2.
01/18
Asymptotic analysis, solving recurrences
1-4
0, 2.1-2.2
2.1-2.2,5.2
3.
01/23
Probabilistic analysis, Randomized Quicksort
5,7
p.29
13.3,13.12
Mini 1 due
4.
01/25
Linear-time Selection (randomized and deterministic)
9
2.3-2.4
13.5
5.
01/30
Sorting/searching lower bounds
8.1
2.4
Hwk 1 due
6.
02/01
Tight upper/lower bounds II
7.
02/06
Amortized Analysis
17
Mini 2 due
8.
02/08
Search trees: B-trees, treaps
12,18
9.
02/13
Radix sort, tries
8
Hwk 2 pres
10.
02/15
Hashing: universal & perfect hashing
11
1.5
13.6
11.
02/20
Dynamic Programming + QUIZ
15
6
6.1-6.7
Mini 3 due
12.
02/22
Graph Algorithms I
22,23
3,4.1-4.3, 5.1
3
13.
02/27
Graph Algorithms II
21
4.4,6.8-6.10
14.
03/01
Midterm Review
15.
03/06
MIDTERM
16.
03/08
Graph Algorithms III
24,25
4.4-4.7
4.5-4.6
Hwk 3 due
17.
03/20
Network Flows and Matchings I
26
7.1
7
18.
03/22
Network Flows and Matchings II
19.
03/27
Linear Programming
29
7.4, 7.6
11.6
Week of Hw 4
presentations
20.
03/29
NP-Completeness I
34
8
8.1-8.3
21.
04/03
NP-Completeness II
8.4-8.10
Mini 4
22.
04/05
Approximation Algorithms
35
9.2
11
23.
04/10
On-line algorithms
HW 5 due
24.
04/12
Number-theoretic algs I+ QUIZ
31
1.1-1.4
25.
04/17
Number-theoretic algs II
26.
04/24
Number-theoretic algs III (FFT)
30
2.6
5.6
Week of Hw 6
presentations
27.
04/26
Game Theory (zero-sum & general-sum games)
7.5
12.7
28.
05/01
Machine Learning Theory
Mini 5
29.
05/03
Fair division, envy-free cake-cutting