Reading Assignments

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

• Reading for Week of January 20th: Importance of Efficient Algorithms and Algorithm Analysis, Review of Big-O Notation (Chapter 0), Arithmetic Operations (Section 1.1)
• Reading for Week of January 27th: Divide-and-Conquer Recurrences and the Master Method, Mergesort (Section 2.2, 2.3), Integer Multiplication, Finding Medians, Matrix Multiplication, Fast Fourier Transform (Sections 2.1, 2.4, 2.5, 2.6)
• Reading for Week of February 3rd: Matrix Multiplication, Fast Fourier Transform, Data Structures for Greedy Algorithms, Binary Heaps, Dijkstra's algorithm, Disjoint Set Data Structure (Sections 2.5, 2.6, 4.4, 4.5, 5.1)
• Reading for Week of February 10th: Data Structures for Greedy Algorithms, Binary Heaps, Paths in Graphs, Breadth-First Search, Dijkstra's algorithm, Disjoint Set Data Structure, Minimum Spanning Trees (Sections 4.1-4.5, 5.1)
• Reading for Week of February 17th: 0-1 Knapsack, Edit Distance, Matrix-Chain Multiplication, Shortest paths in DAG's (Sections 6.1-6.6)
• Reading for Week of March 3rd: Ford-Fulkerson Algorithm for finding a maximum flow in a network (Section 7.2)
• Reading for Week of March 10th: Bipartite Matching Algorithm, Search Problems, NP-Complete Problems (Section 7.3, 8.1, 8.2)
• Reading for Week of March 17th: Search Problems, NP-Complete Problems (8.1, 8.2)
• Reading for Week of March 24th: Search Problems, NP-Complete Problems (8.1, 8.2)
• Reading for Weeks of April 7th and April 14th: Approximation Algorithms (Section 9.2)