Algorithms and Data Structures Course outline 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. 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 Mon and Wed 2-3:30 pm 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. 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 23 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. Other references: Sections 33.4 and 9.3 from CLRS. Aug 26 Lecture 0. Focusing on the basics, including asymptotic analysis and notation, loop invariants, merge sort, and writing proofs. Other references: Section 2.3 and Chapter 3 from CLRS. Aug 28 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. Aug 30 Dynamic programming: Longest increasing subsequence, and optimal BSTs. Other references: Chapter 3 from Jeff Erickson's book, available here (particularly Sections 3.6 and 3.9). Sep 4 Greedy algorithms: Huffman coding. Matroids and greedy algorithms. Other references: CLRS Chapter 17. Sep 6 Continued with matroids from previous class. Greedy job selection with penalties. Other references: CLRS Chapter 17. Sep 11 Dijkstra's algorithm: with min-heaps, and with Fibonacci heaps. For the latter, we only managed to describe and analyse the decr-key operation. Other references: CLRS Section 24.3 for Dijkstra's algorithm, Chapter 6 for min heaps, and Chapter 19 for Fibonacci heaps. Sep 20 Kruskal's algorithm for MSTs, and the union-find data structure: here. Other references: Sariel Har-Peled's notes, available here. Sep 25 Red-black trees: here. Other references: There are a number of youtube videos which may also be helpful. Sep 27 Red-black trees continued, and an introduction to max flows. Other references: Sections 26.1, 26.2 from CLRS. Oct 4 Max flow, min-cuts, and Ford-Fulkerson. The Edmonds-Karp algorithm. Other references: As previously. Oct 10 The Edmonds-Karp algorithm. The Preflow-Push algorithm. Other references: As previously. Oct 16, 18, 23, 25, 28 Kavitha took these classes, covering global min-cut (algorithms by Karger and Karger-Stein), Miller-Rabin primality testing, randomized quicksort, and online paging. Oct 30 Randomized binary search trees, and a randomized algorithm for 2-SAT. My notes. These notes are from an earlier version of the course, and may have some (minor) errors. Other references: Lecture notes from a course taught at Harvard. Nov 1 Derandomization. Again, the notes are from an earlier version of the course, and may have some (minor) errors. Other references: Notes by Leen Stougie. Nov 6 Matchings in bipartite graphs. Notes are from an earlier ... etc. Other references: Notes by Naveen Garg. Nov 8 Matchings in general graphs. Again, the notes are from an earlier version of the course, and may have some (minor) errors. Other references: Notes by Naveen Garg. Nov 13 Linear progamming, and integrality. Other references: Jeff Erickson's notes. Nov 20 Linear progamming duality. Other references: Luca Trevisan's notes. Nov 22 An algorithm for vertex cover in bipartite graphs, using LP integrality. Linear progamming duality. Complexity classes: P, NP, and NP hardness. Other references: Chapter 34 in CLRS, up to the beginning of 34.3. Nov 27 NP hardness reductions. A greedy O(log n)-approximation algorithm for set cover (notes). Other references: 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). Nov 29 Two LP based algorithms for Set Cover. Other references: Chapters 14 and 15 from "Approximation Algorithms" by Vijay Vazirani.
 Assignment Policies Please read the assignment policies carefully. You are encouraged to discuss the problems with others in the class, but you must write up the solution by yourself, in your own words. Do not try and search for solutions online. Please write in your submission the people with whom you discussed the problems, as well as any references you used. Assignments can be submitted late only in exceptional circumstances. You must inform me, and get my consent to submit an assignment late, at least a day before the assignment submission deadline. The first assignment that is late without prior approval 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 6 days late will not be graded at all. 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 Assignment 1, due Sep 12. Assignment 2, due Sep 27 October 4. Assignment 3, due October 25. Assignment 4, updated November 9, due November 15 20. Assignment 5, due December 6.