LECTURES
- course introduction,
Official Course Outline
(slides)
Data Structures
- balanced search trees
(slides)
rotations, AVL trees, 2-3 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
- disjoint-sets 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 (Gale-Shapley)
- network flows 1
(PDF)
flow networks, flows, residual graphs, augmenting paths, Ford-Fulkerson
- 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)
(B-F code in Python)
Bellman-Ford, Floyd-Warshall
Divide and Conquer
-
mergesort (review), closest pair of points in 2D
(PDF)
- Karatsuba multiplication, Master method
(PDF)
- determininistic quicksort and select, median-of-median-of-5'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, union-find
Exercises:
SCCs, DAGs
Exercises:
Dijkstra's algorithm
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:
Bellman-Ford, Floyd-Warshall
Midterm 2
exam and
solutions
Exercises:
closest pair of points
Exercises:
master method
Exercises:
selection
Exercises:
average case
Exercises:
randomized select
Exercises:
lower bounds and linear sorting
Exercises:
data compression
(final exam) &
(solutions)
|