| title | slides | handout | contents |
|---|
| 1. Introduction. |
pdf |
pdf |
Fibonacci numbers, sorting problem, big-O notation. |
| 2. Divide-and-conquer algorithms. |
pdf |
pdf |
Multiplication, recurrence relations, matrix multiplication. |
| 3. Fast Fourier transform. |
pdf |
pdf |
Alternative representation of polynomials, complex roots of unity, interpolation. |
| 4. Decomposition of graphs. |
pdf |
pdf |
Depth-first search, connectivity in undirected graphs, topological sorting, strongly connected components. |
| 5. Paths in graphs. |
pdf |
pdf |
Breadth-first search, Dijkstra's algorithm, shortest paths in the presence of negative edges. |
| 6. Greedy algorithms. |
pdf |
pdf |
Activity-selection, Huffman encoding, set cover, vertex cover, SAT local search. |
| 7. Dynamic Programming. |
pdf |
pdf |
Edit distance, knapsack, chain matrix multiplication, shortest reliable paths, all-pairs shortest paths, TSP, independent sets in trees. |