contents amortized analysis further reading exercises projects lower bounds introduction to lower bounds proofs lower bounds on searching lists searching in unsorted lists searching in sorted lists finding the maximum value adversarial lower bounds proofs state space lower bounds proofs finding the ith best element optimal sorting further reading exercises projects patterns of algorithms dynamic programming the knapsack problem all-pairs shortest paths randomized algorithms randomized algorithms for finding large values skip lists numerical algorithms exponentiation largest common factor matrix multiplication random numbers the fast fourier transform further reading