Reading Assignments

From S. Dasgupta, C. Papadimitriou, U. Vazirani's, Algorithms

• Reading for weeks of January 21st and January 28th: Chapter 0 (Importance of Efficient Algorithms and Algorithm Analysis, Review of Big-O Notation), and Chapter 1: Sections 1.1-1.4 (Algorithms for Integers and Applications)
• Reading for Week of February 5th: Master Theorem, Mergesort, Finding the Median of an Array, Integer and Matrix Multiplication (Sections 2.2, 2.3, 2.4, 2.5, 2.1)
• Reading for Week of February 12th: Finding the Median of an Array, Integer and Matrix Multiplication (Sections 2.4, 2.5, 2.1)
• Reading for Week of February 19th: Fast Fourier Transform (Section 2.6)
• Reading for Week of February 26th: Data Structures for Greedy Algorithms: Binary Heaps and Disjoint-Set Data Structure (Section 4.5, 5.1.4)
• Reading for Week of March 4th and week of March 11th: Dijkstra's Algorithm, Prim and Kruskal's Algorithms (4.4,5.1)
• Reading for Week of March 18th: 0-1 Knapsack, Edit Distance, and Matrix-Chain Multiplication Problems (Sections 6.4, 6.3, 6.5)
• Reading for Week of March 25th: Shortest paths in DAG's, Breadth-first and Depth-first travels (Sections 6.1, 6.2, 3.2, 3.3, 4.2)
• Reading for Week of April 8th: Ford-Fulkerson Algorithm for finding a maximum flow in a network (Section 7.2)
• Reading for Week of April 15th: Max Matching Algorithm (Section 7.3)
• Reading for Week of April 22nd: Hard problems, Classes P and NP (Sections 8.1 and 8.2)
• Reading for Week of April 29th: NP-Complete Reductions (Sections 8.3)
• Reading for Week of May 6th: Approximation Algorithms (Sections 9.2)