|
This a graduate course on algorithms and data structures. Topics that I plan to cover include: basic programming paradigms (recursion, divide and conquer, greedy, dynamic programming), data structures (union-find, heaps), graph algorithms (shortest paths, spanning trees, network flows, matching, min-cut), randomized algorithms, linear programming and duality, semi-definite programming, approximation algorithms, online algorithms. |
|
We will assume knowledge of the basics of algorithms and analysis and data structures, including basic sorting and searching algorithms, graph traversal, solving recurrences, big-oh notation, and NP-completeness. These prerequisites may be obtained from the CLRS reference book. |
|
Classes will be held Tue 4-5:30 pm and Fri 2 - 3:30 in A-201.
Classes begin on August 17th. Evaluation will be on the basis of assigments (50%), a mid-term (20%), and a final exam (30%). The weightage of these may be slightly modified later. |
|
The topics we cover will mostly be from the book Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein, for the first part of the course. However, our treatment and notation will differ. Other good reference materials are
Our treatment will often differ from that in books, and I may cover topics out of order. I will post an outline of topics covered in each lecture below, including source material. |
|
|
An O(n log n) algorithm for finding the closest pair of points in the plane. An O(n) algorithm for finding the median of a set of numbers.
References: Sections 33.4 and 9.3 from CLRS. My notes. | |
An O(n log n) for polynomial multiplication using the Fast Fourier Transfom
References: Chapter 30 from CLRS. My notes. | |
Integer multiplication by the Karatsuba algorithm. Matrix multiplication using Strassen's algorithm. Computing the min and max of an array, and lower bounds. Dynamic programming - the coin change problem.
References: My notes. Further references: for the Karatsuba algorithm, see the course handout by Babai. Strassen's matrix multiplication is from CLRS Section 4.2. The min-max problem is from CLRS Section 9.1. | |
Dynamic programming - optimal binary search trees. Matroids and greedy algorithms. The unit-size job scheduling problem.
References: My notes. Optimal BSTS are from CLRS Section 15.5, and CLRS Chapter 17 for greedy algorithms and matroids. | |
Jaikumar will conduct these classes, on primality testing. | |
Faster algorithms using better data structures for Dijkstra's algorithm: min heaps and Fibonacci heaps.
References: CLRS Section 24.3 for Dijkstra's algorithm, Chapter 6 for min heaps, and Chapter 19 for Fibonacci heaps. My notes: 1, 2. | |
Kruskal's algorithm for minimum spanning trees, and the union-find data structure.
References: Sariel Har-Peled's notes, available here. My notes are here | |
Union-find continued. Maximum flows and minimum cuts. Ford-Fulkerson, Edmonds-Karp.
References: Class notes, as well as Sections 26.1, 26.2 from CLRS. | |
Edmonds-Karp continued. The preflow-push algorithm.
References: Class notes, example, as well as Sections 26.4 from CLRS. | |
The preflow-push algorithm continued. All-pairs shortest paths algorithm (Johnson's algorithm).
References: Class notes, an example, as well as Sections 25.3, 26.4 from CLRS. | |
Maximum matching in bipartite graphs.
References: My notes. Lecture notes from a course taught by Naveen Garg. | |
Maximum matching in bipartite and general graphs. Berge's Lemma for general graphs, and Tutte's theorem.
References: My notes. Lecture notes from Naveen Garg. | |
Maximum matching in general graphs (contd). Randomized binary search trees.
References: My notes, and Naveen Garg's notes above. | |
Global min-cut - Karger's algorithm and Karger-Stein.
References: My notes. Lecture notes from a course by Russell Impagliazzo | |
Randomized algorithms for 2SAT and Weighted Max SAT, derandomization. | |
Set Balancing and derandomization by pessimistic estimators. Introduction to linear programming, and an exponential time algorithm to solve a linear program.
References: My notes: (1) and (2). Jeff Erickson's notes, until Section 26.3. | |
Linear programming: total unimodularity.
References: My notes. Jeff Erickson's notes, continued from Section 26.3. I couldn't find a good reference for total unimodularity, so please refer to my notes. | |
Linear programming: duality, complementary slackness, and application to max-flow min-cut theorem.
References: My notes. Luca Trevisan's notes. We didn't do the proof of strong duality. | |
Computing mixed Nash equilibria in zero-sum games using linear programming duality.
References: My notes. Lecture notes by Costis Daskalakis. | |
Complexity classes: P, NP, co-NP, polynomial-time reductions and NP-hardness. Hardness of independent set and subset-sum.
References: My notes (these notes also contain the greedy algorithm for set cover). Chapter 34 in CLRS, though not Lemma 34.6, Theorem 34.9, 34.10, 34.13 (and others). Theorem 34.15 shows hardness of subset sum. | |
Linear programming based algorithms for set cover.
References: My notes. Chapters 14 and 15 from "Approximation Algorithms" by Vijay Vazirani. | |
A 2-approximation algorith minimum makespan scheduling.
References: My notes. Chapter 17 from "Approximation Algorithms" by Vijay Vazirani. |
|
|
|
|
|
|