1. Review of concepts needed for analyzing running time of algorithms, and the subquadratic algorithm for polynomial multiplication. 2. Divide-and-Conquer for closest pair in the plane. 3. Probability spaces, events, and the randomized protocol for contention resolution. 4. Conditional probability, independence of events, and the randomized min-cut algorithm. 5. Random variables, linearity of expectation, universal family of hash functions and their applications. 6. Competitive analysis of the deterministic and randomized marking algorithms for caching. 7. Dynamic programming for the weighted interval scheduling problem. 8. Dynamic programming for the segmentation problem. 9. Kleinberg's paper on algorithmic issues in the small world phenomenon. 10.Flow and algorithms for computing the maximum flow. 11.Application of maximum flow to image segmentation and maximum matching. 12.Polynomial time reducibility. Reductions between independent set and vertex cover, from vertex cover to set cover, 3CNF-SAT to independent set, 3CNF-SAT to 3-Colorability. 13.Efficient verifiers and NP. 14.NP completeness, and NP-completeness of independent set, vertex cover, set cover, and 3-colorability assuming the NP-completeness of 3CNF-SAT 15.Sketch of 3CNF-SAT's NP-completeness. 16.The class co-NP. The proof that PRIMES is in NP. Significance of the intersection of NP and co-NP. 17.If factoring is NP-hard, NP = co-NP. If any problem that is in NP as well as co-NP is NP-hard, then NP = co-NP. 18. Approximation algorithms for vertex cover and set cover. 19. Approximation algorithm for the k-center problem. 20. Edge disjoint paths and a poly-time approximation scheme for the knapsack problem. 21. Local search for finding a stable configuration for a Hopfield neural network. The max-cut problem. 22. Nash equilibria.