# 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.