|
|
|
David Mount's lecture notes (DM): We will mainly follows these excellent lecture notes.
|
Topic
|
References
|
|
Introduction to Algorithm Design |
DM, Lecture 1 |
|
Algorithm Design: The Stable Marriage Problem |
DM, Lecture 2 |
|
Algorithm Design Review: Mathematical Background |
DM, Lecture 3 |
|
Quicksort and Linear-Time Selection
|
pdf |
|
Heaps and Heapsort
|
pdf |
|
Sorting in Linear
Time
|
pdf |
|
Greedy Algorithms for Scheduling |
DM, Lecture 4 |
|
Introduction to Graphs: Definitions, Representations,
Traversals |
DM, Lecture 5 |
|
Dijkstra's Algorithm for Shortest Paths |
DM, Lecture 6 |
|
Greedy Algorithms for Minimum Spanning Trees |
DM, Lecture 7 |
|
Greedy Algorithms: Huffman Coding |
DM, Lecture 8 |
|
Divide and Conquer:: Mergesort and Inversion Counting |
DM, Lecture 9 |
|
Dynamic Programming: Weighted Interval Scheduling |
DM, Lecture 11 |
|
Dynamic Programming: Chain Matrix Multiplication |
DM, Lecture 13 |
|
Dynamic Programming: All-Pairs Shortest Paths and Floyd-Warshall
Algorithm |
DM, Supplemental Lecture 6 |
|
Network Flows: Basic Definitions |
DM, Lecture 14 |
|
Network Flows: The Ford-Fulkerson Method |
DM, Lecture 15 |
|
NP-Completeness: General Definitions |
DM, Lecture 18 |
|
NP-Completeness: Reductions |
DM, Lecture 19 |
|
Cook's Theorem, Satisfiability, and Independent Set |
DM, Lecture 20 |
|
Approximation Algorithms: Vertex Cover |
DM, Lecture 22 |
|