Date 
Day 
Topic (Link to Lecture
Notes) 
Book Chapter 

Fundamentals 

Jan 18 
T 
Course
Intro, Karatsuba multiplication 
Notes: Chapters 15, 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. RedBlack trees 
13,14,15 
Feb 15 
T 
RedBlack
trees (cont). Skiplists. 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 
UnionFind 
22 
Mar 9 
Th 
UnionFind
(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 NPCompleteness 
36 
Mar 23 
Th 
NPCompleteness
(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 

ContextBased
Algorithmics 

Apr 13 
Th 
Contextbased
algorithmics. External Memory Algorithms. Btrees 
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 Numbertheoretic algorithms 
33 

May 4 
Th 
Summary
and Overview 
May 8 
M 
Final exam 