CS 170: Efficient Algorithms and Intractable Problems

Lecture Notes #

Algorithms for Integer Arithmetic Divide and Conquer (Master Theorem) Matrix Multiplication Sorting Median Finding Fast Fourier Transform (FFT) Graphs Greedy Algorithms Minimum Spanning Trees Huffman Coding Horn Formulas Dynamic Programming Linear Programming Network Flow Duality Zero-Sum Games Reductions Search Problems, P NP Randomized Algorithms Streaming Lower Bounds