|
|
|
|
|
Topics
|
Notes
|
References*
|
|
Introduction
|
Introduction
|
pdf
|
1, 2.1, 2.2
|
|
Divide-and-Conquer
|
Merge sort
|
pdf
|
2.3, KT 5.3
|
|
The maximum subarray
problem
|
pdf
|
4.1
|
|
|
Integer and matrix
multiplication
|
pdf
|
4.2, 4.4, 4.5, KT 5.5
|
|
|
Randomized algorithms
|
pdf
|
5, Appendix C.1-C.4
|
|
Sorting
|
Quicksort and
linear-time selection
|
pdf
|
7, 9.2
|
|
|
Heaps and heapsort
|
pdf
|
6
|
|
|
Sorting in linear time
|
pdf
|
8
|
|
Greedy Algorithms
|
Greedy algorithms
|
pdf
|
16.1, 16.2
|
|
|
Huffman coding
|
pdf
|
16.3
|
|
Review
|
Midterm review
|
pdf
|
|
|
Dynamic Programming
|
1D dynamic programming
|
pdf
|
15.1, KT 6.1
|
|
|
2D dynamic programming
|
pdf
|
15.3, 15.4
|
|
|
DP over intervals
|
pdf
|
15.5, KT 6.5
|
|
Graph Algorithms
|
Introduction to graphs
|
pdf
|
Appendix B.4, B.5, 22.1
|
|
|
Basic graph algorithms
|
pdf
|
22.2-22.5
|
|
Minimum spanning trees
|
pdf
|
23, 21.1-21.3
|
|
Shortest paths
|
pdf
|
24.1-24.3, 24.5, 25.1,
25.2
|
|
|
Maximum flow
|
pdf
|
26.1-26.3, KT 7.12
|
|
Review
|
P vs NP; Review
|
pdf
|
|
* KT refers to the reference
book by Jon Kleinberg and Éva Tardos.
|
|