This repository contains lecture notes, assignments, and resources for the CSS.201.1 Algorithms course conducted at the Tata Institute of Fundamental Research (TIFR) during the August–November 2024 semester.
The course was instructed by Prof. Umang Bhaskar, and these notes were scribed and compiled by Soham Chatterjee.
The course focuses on the design and analysis of algorithms, exploring classical and advanced techniques across several domains.
Key topics include divide-and-conquer strategies, dynamic programming, greedy algorithms, graph algorithms, randomized methods, approximation techniques, and complexity theory.
Instructor: Prof. Umang Bhaskar
Scribe & Notes Author: Soham Chatterjee
Semester: August – November 2024
Institute: Tata Institute of Fundamental Research (TIFR)
Official Course Page: https://www.tcs.tifr.res.in/~umang/algos24.html
The repository includes detailed, typeset lecture notes covering the following topics:
- Closest Pair of Points — Naive and divide-and-conquer approaches
- Median Finding in Linear Time — Deterministic selection algorithms
- Polynomial Multiplication — FFT and Schönhage-Strassen techniques
- Dynamic Programming — LIS, optimal BSTs, and more
- Greedy Algorithms — Matching, Huffman encoding, and matroids
- Graph Algorithms — Dijkstra, Kruskal, maximum flow, global min-cut
- Advanced Data Structures — Fibonacci heaps, union-find, red-black trees
- Randomized Algorithms & Derandomization — 2-SAT, Max-SAT, set balancing
- Approximation Algorithms — LP relaxations, rounding techniques
- Complexity Theory — P vs NP, reductions, NP-completeness
The full table of contents can be found inside the notes.
The primary references for the course were:
- Introduction to Algorithms — Cormen, Leiserson, Rivest, and Stein (CLRS)
- Approximation Algorithms — Vijay V. Vazirani (Chapters 14, 15, 17)
- Additional materials and examples were provided during lectures.
These lecture notes were typeset in LaTeX using a custom eye-candy theme developed by the me: