|
This a graduate course on algorithms and data structures. Topics that we 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. Topics may be added / removed, depending on interest and time available. |
|
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 Tuesday and Thursday 9:30 - 11 am in A-201.
Evaluation will be on the basis of assigments (50%), a mid-term (25%), and a final exam (25%). The weightage of these may be slightly modified later. Office hours are Wednesdays 9:30 - 11 am. |
|
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.
|
|
|
Logistics. 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 (incomplete).
Other references: Sections 33.4 and 9.3 from CLRS. | |
Completing median-finding in O(n) time. Polynomial multiplication via the DFT in O(n log n) time.
Other references: Chapter 30 from CLRS, excluding Section 30.3. | |
Dynamic programming: Longest increasing subsequence, and optimal BSTs. Note that the algorithm we actually did in class is different from the algorithm in the notes. In class, we had a one-dimensional table for the DP, where each entry stored the length of the LIS that ended in that entry.
Other references: Chapter 3 from Jeff Erickson's book, available here (particularly Sections 3.6 and 3.9). | |
A faster algorithm for Longest Increasing Subsequence. Greedy algorithms - matchings. | |
Greedy algorithms: Huffman coding. Matroids and greedy algorithms.
Other references: CLRS Chapter 17. | |
Continued with matroids from previous class. Greedy job selection with penalties. Started discussing Dijkstra's algorithm.
Other references: CLRS Chapter 17, and CLRS Section 24.3 for Dijkstra's algorithm. | |
Dijkstra's algorithm: with min-heaps, and with Fibonacci heaps.
Other references: CLRS Section 24.3 for Dijkstra's algorithm, Chapter 6 for min heaps, and Chapter 19 for Fibonacci heaps. | |
Kruskal's algorithm for MSTs, and the union-find data structure: here.
Other references: Sariel Har-Peled's notes, available here. | |
Red-black trees: here.
Other references: There are a number of youtube videos which may also be helpful. | |
Red-black trees continued, and an introduction to max flows.
Other references: Sections 26.1, 26.2 from CLRS. | |
Max flow, min-cuts, and Ford-Fulkerson. The Edmonds-Karp algorithm.
Other references: As previously. | |
The Preflow-Push algorithm.
Other references: As previously. | |
Randomized binary search trees, and a randomized algorithm for 2-SAT. My notes. As mentioned in class, the random variable Ti isn't really a random variable. The proof can be fixed to make it work, see the other references below.
Other references: Lecture notes from a course taught at Harvard. | |
Derandomization. Notes are from an earlier version of the course, and may have some (minor) errors.
Other references: Notes by Anna Karlin. | |
Global min-cuts. The algorithms of Karger and Karger-Stein
Other references: Notes by Aleksandar Nikolov. | |
Matchings in bipartite graphs.
Other references: Notes by Naveen Garg. | |
Class taken by Ramprasad, on bipartite matching using matrix scaling.
References: Survey by Martin Idel, and paper by Linial-Samarodnitsky-Wigderson. | |
Matchings in general graphs. The notes are from an earlier version of the course, and may have some (minor) errors.
Other references: Notes by Naveen Garg. | |
Linear progamming.
Other references: Jeff Erickson's notes. | |
LP integrality, and Linear progamming duality.
Other references: Luca Trevisan's notes. A good reference for the proof of strong duality is Chapter 4 in the book Introduction to Linear Optimization by Bertsimas and Tsitsiklis. | |
Completed Linear progamming duality.
Other references: As from the previous chapter. | |
Complexity classes: P, NP, and NP hardness.
Other references: Chapter 34 in CLRS, up to the beginning of 34.3. | |
Class 1: Two LP based algorithms for Set Cover. Set cover is defined here. These notes also contain an O(log n)-approximate deterministic algorithm for set cover, which we did not cover.
Class 2: Makespan minimization on unrelated machines: a 2-approximation algorithm. Other references: Chapters 14, 15, and 17 from "Approximation Algorithms" by Vijay Vazirani. |
|
|
|
|
|
|