- [E] Algorithms, by J. Erickson
- [CLRS] Introduction to Algorithms, third edition, by T. Cormen, C. Leiserson, R. Rivest, and C. Stein
- [DPV] Algorithms, by S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani
- [KT] Algorithm Design, by Jon Kleinberg, �va Tardos

- [V] Algorithms and complexity, by E. Viola

```
Please send additional bugs to Manu.
NOT FIXED NEITHER IN SLIDES NOR VIDEOS
Counting sort analysis: big-Oh should be big-Theta.
odd-even-merge: for i should go to n-3, not n-1.
The h-k-1 in the slide about selecting the h-th smallest element should be h-k.
DP & Video 16 at time 7:05 n = 3 should be n = 5
In the activity selection pseudocode, when we add we should add a[m], not a[i].
In the heap lecture video (Video 22):
Starting from 13:45, 10 should be 1.
There is a typo on the left-hand graph on the flow slides 16 and 17. The 30/30 in the middle edge should be 0/30.
FIXED IN divide-and-conquer-annotated BUT NOT on videos and not on non-annotated version:
Mergesort base case is high = low, not high-low < 1
Same for quicksort
Partition: Do j-- while A[j] > A[hi] -> Do j-- while A[j] > A[hi] & i < j
Running time bound for selecting h-th smallest element: inequalities are on the wrong side.
```

Bubblesort [CLRS, Problem 2-2]

Countingsort [CLRS, 8.2]

Radixsort [CLRS, 8.3]

Mergesort [E, 1.4], [CLRS, 2.3]

Quicksort [E, 1.5], [CLRS, 7]

Oblivious mergesort [V, 2.1]

Median [E, 1.8], [CLRS, 9.3]

Closest pair [CLRS, 33.4]

Karatsuba's integer multiplication [E, 1.9], [KT 5.5]

Strassen's matrix multiplication [CLRS, 4.2]

Fast Walsh-Hadamard transform [V, 2.2]

Polynomials and fast Fourier transform [CLRS, 30], [KT, 5.6]

Coin-change problem

Longest common subsequence [CLRS, 15.4]

Subset sum [E, 3.8]

Dynamic programming in economics [V, 3.1]

Activity selection [E, 4.2], [CLRS, 16.1]

Binary search trees [CLRS 12.1, 12.2] [V 4]

Rotations [CLRS 13.2] [V 4]

AA Trees [V 4]

Hash functions [CLRS 11]

Heaps [CLRS 6]

Graph representations [E 5.4], [CLRS 22.1]

Breadth-first search [E 8.4], [CLRS 22.2]

Bellman-Ford [E 8.7] [CLRS 24.1]

Dijkstra [E 8.6], [CLRS 24.3]

All-pairs shortest-path via matrix multiplication [E 9.7], [CLRS 25.1]

Floyd Warshall [E 9.8], [CLRS 25.2]

Johnson's algorithm [E 9.4], [CLRS 25.3]

3SAT reduces to CLIQUE [CLRS 34.5.1]

CLIQUE to VERTEX-COVER [CLRS 34.5.2]

3SAT reduces to SUBSET-SUM [CLRS 34.5.5]

3SAT reduces to 3COLOR [E 12.10]

Flow networks [E 10.1 - 10.3] [CLRS 26.1] (our notation is closer to edition 2 CLRS)

Ford-Fulkerson [E 10.4] [CLRS 26.2]

Edmonds-Karp [E 10.6] [CLRS 26.3]

Maximum bipartite matching [E 11.3], [CLRS 26.4]

The linear programming problem [CLRS 29.1, 29.2]

The simplex algorithm [CLRS 29.3]

Duality [CLRS 29.4]

2-approximation for VERTEX-COVER [CLRS 35.1]

2-approximation for weighted VERTEX-COVER [KT 11.6]

Vector programs, randomized rounding, and max-cut