Algorithms and Data Structures
Course outline
 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.
Prerequisites
 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.
Details
 Classes will be held Tue 11:30-1 pm and Thu 4 - 5:30 in A-201.

Classes begin on August 8th.

Evaluation will be on the basis of assigments (40%), a mid-term (20%), a final exam (30%), and a class presentation (10%). The weightage of these may be slightly modified later.

Reference material
 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

  • Algorithm Design by Kleinberg and Tardos
  • Algorithms by Dasgupta, Papadimitriou and Vazirani
  • Introduction to Linear Optimization by Dimitris Bertsimas
  • The Design of Approximation Algorithms by Williamson and Shmoys
  • Approximation Algorithms by Vazirani
  • Randomized Algorithms by Motwani and Raghavan

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.

Lectures
Aug 8
 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.

Aug 10
 An O(n log n) for polynomial multiplication using the Fast Fourier Transfom

References: Chapter 30 from CLRS.

Aug 22
 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: 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.

Aug 26
 Lower bound for the min and max problem. Dynamic programming - optimal binary search trees. Greedy algorithms - activity selection and Huffman coding.

References: The lower bound proof is from the lecture notes of R. Chandrasekaran, available here. Optimal BSTS are from CLRS Section 15.5. The greedy algorithms are from Chapter 16 in CLRS.

Aug 29
 Matroids and greedy algorithms. The unit-size job scheduling problem. Dijkstra's algorithm for single-source shortest path.

References: CLRS Chapter 16 for matroids, Section 24.3 for Dijkstra's algorithm.

Aug 31
 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.

Sep 5 and 7
 A randomized primality testing algorithm by Miller and Rabin. Kavitha will be taking these classes.

References: CLRS Section 31.8.

Sep 14
 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

Sep 19
 Red-black trees.

References: Class notes. There are a number of youtube videos that you may also find helpful.

Sep 21
 Maximum flows and minimum cuts. Ford-Fulkerson, Edmonds-Karp, and the preflow-push algorithms.

References: Class notes, as well as Sections 26.1, 26.2 from CLRS.

Sep 26
 The preflow-push algorithm.

References: Class notes, an example, as well as Section 26.4 from CLRS.

Sep 28
 Continuing the preflow-push algorithm. Maximum matching in bipartite graphs.

References: My notes. Lecture notes from a course taught by Naveen Garg.

October 5
 Maximum matching in general graphs. Berge's Lemma for general graphs, and Tutte's theorem.

References: My notes. Lecture notes from Naveen Garg.

October 10
 Global min-cut - Karger's algorithm and Karger-Stein.

References: My notes. Lecture notes from a course by Russell Impagliazzo

October 12
 Randomized binary search trees, and a randomized algorithm for 2SAT.

References: My notes. Lecture notes from a course taught at Harvard.

October 17
 MaxSat, Set Balancing, and derandomization.

References: My notes. Notes by Leen Stougie.

October 24
 Balls-and-bins, and hashing.

References: My notes. For balls-and-bins, the first of part Anupam Gupta's notes. For hashing, Section 8.4 of the book by Motwani and Raghavan.

October 26
 Hashing and Perfect (Static) Hashing.

References: My notes. Sections 8.4 and 8.5 of the book by Motwani and Raghavan.

November 2
 Linear programming: basic structure, exponential algorithms, and writing problems as LPs.

References: My notes. Jeff Erickson's notes, until Section 26.3.

November 7
 Linear programming: total unimodularity and duality.

References: My notes. Jeff Erickson's notes, continued from Section 26.3. We didn't do the proof of strong duality. I couldn't find a good reference for total unimodularity, so please refer to my notes.

November 9
 Linear programming: duality, complementary slackness, and application to max-flow min-cut theorem.

References: My notes. Luca Trevisan's notes.

November 16, 17
 Kavitha took these classes on stable matching and matching polytopes.
November 21, 23
 Complexity classes: P, NP, co-NP, polynomial-time reductions and NP-hardness. Hardness of independent set and subset-sum. An O(log n) approximation by a greedy algorithm for set cover.

References: My notes. 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. The greedy algorithm for set cover is from Section 35.3 (note that this does the unweighted version, but the proof is easily extendible to the weighted version).

November 28
 Primal-dual and rounding algorithms for set cover

References: My notes. Chapters 14 and 15 from "Approximation Algorithms" by Vijay Vazirani.

Assignment Policies
  • Each student gets 6 15 late days for assignments, which can be used in any combination, and for any reason (e.g., you could turn in assignment 2 six days late, assignment 3 six days late, and assignment 5 three days late).
  • The first assignment that is late after exhausting these late days will be graded out of 50% of the total marks. Any further late assignments will not be graded at all. Any assignment turned in more than 7 days late will not be graded at all.
  • You may discuss the problems with others in the class, but you must write up the solution by yourself, in your own words.
  • Please write in your submission the people with whom you discussed the problems, as well as any references you used.
  • Please write clearly and legibly, and include how you arrived at the solution! All algorithms must be accompanied by proofs of correctness and runtime analysis, unless otherwise stated.
Assignments