Lecture Schedule
 course introduction,
Official Course Outline
(slides)
Data Structures
 balanced search trees
(slides)
rotations, AVL trees, 23 trees
 hashing
(slides)
hash functions & authentication, closed hash tables: linear vs. quadratic probing
 heaps
(slides)
building a heap in O(n log n) vs. O(n), indexed heaps for changing priorities
 disjointsets and union/find
(PDF)
equivalence relations, union by size/height, path compression
Graph algorithms
 directed graphs
(PDF)
strongly connected components (SCC), directed acyclic graphs (DAG), topological orderings
 single source shortest paths
(PDF)
graphs with positive edge weights, Dijkstra's algorithm
 minimum spanning trees
(PDF)
cut property, Prim and Kruskal's algorithms
 bipartite graphs
(PDF)
matching, stable marriages (GaleShapley)
 network flows 1
(PDF)
flow networks, flows, residual graphs, augmenting paths, FordFulkerson
 network flows 2 (PDF)
max flow = min cut, finding maximal match in bipartite graphs
Dynamic Programming
 interval scheduling
(PDF)
greedy approaches, weighted interval scheduling, DP and memoization
 segmented least squares
(PDF)
 sum of subsets, knapsack
(PDF)
 shortest paths in a graph with negative weights
(PDF)
(BF code in Python)
BellmanFord, FloydWarshall
STUDY BREAK
Divide and Conquer

mergesort (review), closest pair of points in 2D
(PDF)
 Karatsuba multiplication, Master method
(PDF)
 determininistic quicksort and select, medianofmedianof5's
(PDF)
Probability and information theory
 what do we mean by "average case"?
(PDF)
amortization, discrete probability: random variables, linearity of expectation
 randomized quicksort and select
(PDF)
expected runtimes
 lower bounds for comparison sorting, sorting in linear time
(PDF)
decision trees, counting sort, bucket sort, more probability: independence
 data compression
(PDF)
optimal prefix codes, Huffman coding, run length coding

Exercises, Exams, etc.
Exercises:
balanced search trees
Exercises:
hashing, hashtables
Exercises:
heaps and priority queues
Exercises:
disjoint sets, unionfind
Assignment 1 (PDF) (code)
(solution)
(test code for grading)
Exercises:
SCCs, DAGs
Exercises:
Dijkstra's algorithm
Assignment 2  (PDF) & (code) (solutions)
Exercises:
Minimal spanning trees
Midterm 1
exam and
solutions
Exercises:
Bipartite graphs
Exercises:
Network flows 1
Exercises:
Network flows 2
Exercises:
Interval scheduling
Exercises:
Segmented least squares
Exercises:
Subset sum and knapsack
Exercises:
BellmanFord, FloydWarshall
Midterm 2
exam and
solutions
Exercises:
closest pair of points
Exercises:
master method
Exercises:
selection
Assignment 3
(PDF) &
(code) & (solutions)
Assignment 4
(PDF) & (code) ,
solutions:
Q1 &
Q2
Exercises:
average case
Exercises:
randomized select
Exercises:
lower bounds and linear sorting
Exercises:
data compression
(final exam) &
(solutions)
