| Date |
Day |
Topic (Link to Lecture
Notes) |
Book Chapter |
| |
Fundamentals |
|
| Jan 18 |
T |
Course
Intro, Karatsuba multiplication |
Notes: Chapters 1-5, 11, 13 and 23 of
the textbook are regarded as prerequisite material for the course. |
| Jan 20 |
Th |
Math Foundations:
asymptotics, recurrences |
1,2,3,4,5 |
| |
Probability,
Sorting and Order Statistics |
|
| Jan 25 |
T |
Probability
Intro. Worst/Avg/Expected case. Quicksort |
6,8 |
| Jan 27 |
Th |
Avg case
vs. Expected case (cont). Linearity of expectation. Randomized selection |
6,10 |
| Feb 1 |
T |
Deterministic
selection. Lower bounds for comparison sorts. Counting and Bucket sort |
9,10 |
| Feb 3 |
Th |
Radix
sort. Tail inequalities. Hashing |
6,9,12 |
| |
Data
Structures |
|
| Feb 8 |
T |
Universal
hashing Quiz 1 (1/2 lecture). |
12 |
| Feb 10 |
Th |
Binary
search trees. Red-Black trees |
13,14,15 |
| Feb 15 |
T |
Red-Black
trees (cont). Skip-lists. Tries. Splay trees |
Lecture Notes |
| |
Fundamental
Algorithm/Analysis Techniques |
|
| Feb 17 |
Th |
Amortized
analysis |
18 |
| Feb 22 |
T |
Amortized
analysis (cont). Dynamic Programming |
18,16 |
| |
Graph
Algorithms |
|
| Feb 24 |
Th |
DFS,
BFS, Shortest Paths |
23,25 |
| Feb 29 |
T |
Shortest
Paths (cont), MST, Designing Algorithms |
25,24,Lecture Notes |
| Mar 2 |
Th |
Midterm |
| Mar 7 |
T |
Union-Find |
22 |
| Mar 9 |
Th |
Union-Find
(cont). Flow Networks: Max Flow, Min Cut |
27 |
| Mar 14 |
T |
Max
Flow (cont), Bipartite Matching |
27 |
| Mar 16 |
Th |
Linear
Programming |
25 |
| |
Computational
Complexity |
|
| Mar 21 |
T |
P,
NP, and NP-Completeness |
36 |
| Mar 23 |
Th |
NP-Completeness
(cont) |
36 |
| Mar 28 |
T |
Spring break; no classes. |
| Mar 30 |
Th |
Spring break; no classes. |
| Apr 4 |
T |
Approximation
Algorithms |
37 |
| Apr 6 |
Th |
Hardness
of Approximation |
Lecture Notes |
| Apr 11 |
T |
Hardness
of Approx (cont)
Quiz 2 (1/2 lecture). |
Lecture Notes |
| |
Context-Based
Algorithmics |
|
| Apr 13 |
Th |
Context-based
algorithmics. External Memory Algorithms. B-trees |
19, Lecture Notes |
| Apr 18 |
T |
External
Sorting. Synopsis Data Structures |
Lecture Notes |
| Apr 20 |
Th |
Synopsis
Data Structures (cont). Online Algorithms |
Lecture Notes |
| Apr 25 |
T |
Parallel
Algorithms |
30 |
| Apr 27 |
Th |
Distributed
Algorithms |
Lecture Notes |
| May 2 |
T |
Cryptography
and Number-theoretic algorithms |
33 |
| |
| May 4 |
Th |
Summary
and Overview |
| May 8 |
M |
Final exam |