Algorithms
General information
Course code: CSS.201.1
Instructors: Kavitha Telikepalli & Piyush Srivastava
Schedule: Monday/Wednesday, 1400-1530, A-201, starting August 17
The following is a tentative list of topics for the class.
- Recursive algorithms (median-finding, fast Fourier transform)
- Greedy algorithms (Dijkstra’s algorithm, MST algorithms, the “perceptron”)
- Fibonacci heap and Union-Find data structures
- Max-flow algorithms
- Randomized algorithms (global min-cut, Miller-Rabin primality testing, hashing, online paging)
- Introduction to linear programming
- Introduction to NP-completeness
- Introduction to approximation algorithms
Lecture notes
The repository for the lecture notes for the course is here. It may not be accessible from outside the TIFR network.
2022-10-17. Karger’s randomized global min-cut algorithm. (KT)
2022-10-14. Mid-term examination.
2022-10-12. Further algorithmic applications of \(s-t\) max-flows. Circulations.
2022-10-10. Applications of \(s-t\) max-flow. \(s-t\) min-cuts with vertex weights.
2022-10-05. No class. (दसरा)
2022-10-03. More refined analyses of the number of non-saturating push operations with the “maximum-height” heuristic. Implementtion issues.
2022-09-28. The preflow-push-relabel algorithm. Bounding the number of relabel, saturating push, and non-saturating push operations in the generic algorithm.
2022-09-26. Dinitz’s blocking flow algorithm.
2022-09-21. Bipartite maximum matching and maximum flow. Maximum \(s-t\) flow in strongly polynomial time: the Dinitz-Edmonds-Karp implementation.
2022-09-19. Maximum \(s-t\) flow with capacities. The Ford-Fulkerson algorithm. Weak and strong duality between maximum \(s-t\) flows and minimum capacity \(s-t\) cuts.
2022-09-14. Fibonacci heaps.
2022-09-12. Analysis of disjoint set forests with union-by-rank and path compression. Introduction to potential function based ammortized analysis through dynamic arrays.
2022-09-07. Greedy optimization for matroids. Data structure: disjoint sets. Introduction to aggregate analysis via dynamic arrays.
2022-09-05. Greedy algorithms: interval scheduling with unit reward, unit-length scheduling with positive rewards and deadlines, maximum weight acyclic subgraphs/minimum weight spanning trees. Matroids.
2022-08-31. No class. (गणेश चतुर्थी)
2022-08-29. Dynamic programming continued: LIS, and optimizing the “trivial” dynamic program. Longest common subsequence. Pseudo-polynomial time algorithm for the 0-1 knapsack. Dynamic programming with “greedy” elements: Dijkstra’s shortest path algorithm and Huffman encoding. Discussion on appropriate data structures for such algorithms.
2022-08-24. Divide and conquer continued: Convolution and the fast Fourier transform. Karatsuba’s integer multiplication algorithm. Dynamic programming: Longest increasing subsequence (LIS).
2022-08-22. No class (First-year students’ orientation programme)
2022-08-17. The Perceptron algorithm as an example of a greedy algorithm and of the use of potential functions in analysis. Divide and conquer: linear time selection.
Homeworks etc.
Homeworks are available here. (The link may not be accessible from outside the TIFR network.)
References
Relatively affordable Indian editions are available for most of the books below.
- Algorithm Design. Jon Kleinberg and Éva Tardos.
- Design and analysis of algorithms: A contemporary perspective. Amit Kumar and Sandeep Sen.
- Introduction to Algorithms. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.
- A fourth edition has just come out with additional material, but it may not yet be available as an Indian edition. The earlier editions are available in an Indian edition.
- The Design and Analysis of Computer Algorithms. Alfred V. Aho, John E. Hopcroft, and Jeffrey D. Ullman.
- Approximation Algorithms. Vijay V. Vazirani.