|
This a graduate course on algorithms and data structures. It will be co-taught by Kavitha Telikepalli and me; I will teach the first half, and Kavitha the second. 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. |
|
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 Mon and Wed 2-3:30 pm.
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. Aparna Shankar made some nice notes on primality testing, available here. |
|
|
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. Integer multiplication by Karatsuba's algorithm.
References: Chapter 30 from CLRS. My notes. Further references: for the Karatsuba algorithm, see the course handout by Babai. | |
Dynamic programming - computing Fibonacci numbers, longest increasing subsequence, and optimal binary search trees.
References: My notes. Chapter 3 from Jeff Erickson's book, available here (leaving out Sections 3.7, 3.8, 3.10). | |
Huffman coding. Matroids and greedy algorithms.
References: My notes. CLRS Chapter 17 for greedy algorithms and matroids. | |
Matroids continued - The unit job scheduling problem. Submodular functions and the greedy algorithm.
References: My notes. CLRS Chapter 17 for greedy algorithms and matroids. Lecture notes by Jan Vondrak. | |
Faster algorithms using better data structures for Dijkstra's algorithm: min heaps and amortized analysis.
References: CLRS Section 24.3 for Dijkstra's algorithm, Chapter 6 for min heaps. My notes. | |
Fibonacci heaps.
References: CLRS Chapter 19 for Fibonacci heaps. My notes. | |
Kruskal's algorithm for minimum spanning trees, and the union-find data structure.
References: Sariel Har-Peled's notes, available here. My notes. | |
The union-find data structure. Red-black trees.
My notes: 1 and 2. There are a number of youtube videos which may also be helpful. | |
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. |
|
|
|
|
|
|