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 |