Design and Analysis of Algorithms (CS602),
Odd Semester, 2025-2026

The course consists of two lectures per week. The goal of the course is to study design paradigms for algorithms and their analysis. The basic course outline is as given in this page, but it may deviate a bit. Some familiarity about basics of programming and some basic data structures will be assumed.

Course Instructor: Abhranil Chatterjee
Teaching Assistants:
- Kakadiya Harshkumar Pravinbhai
- Khushwant Kaswan
- Vansh Kunwar
- Varad Prabhakar Shinde

General Information:

Class Timing:	Monday 15:30-16:45, Tuesday 14:00-15:15 Room No. LH-4, Lecture Hall Complex.
Grading Policy:	Mid-sem: 30, End-sem: 40, Internal evaluation: 30

Study material:

Books

(B1) Algorithms Illuminated Part 1-4
Tim Roughgarden
Cambridge University Press.

(B2) Introduction to Algorithms
T. H. Cormen, C. E. Leiserson, R. L. Rivest and C. Stein
Prentice Hall India.

(B3) Algorithm Design
J. Kleinberg and Eva Tardos
Pearson Education (Indian edition).

(B6) The Art of Computer Programming, Vol. 1-4A
D. E. Knuth
Addison-Wesley.

Lectures (classwise):

Lecture (Dates)	Topics
Lecture 1 (August 4, 2025)	Course content and grading policy Formal definitions and introduction to the word-RAM model Analysis (running time and correctness) and asymptotic notation Proof of correctness for recursion and loops (loop invariant) Correctness of insertion-sort and merge-sort (overview) Introduction to quick-sort and an in-place partition algorithm
Lecture 2 (August 5, 2025)	In-place partition algorithm and its proof of correctness Analysis of the quick-sort algorithm Finding the median in worst-case deterministic linear time
Lecture 3 (August 9, 2025) Working Monday	Revisiting binary search (discarding a portion of the input) Median finding algorithm (revisited) Integer multiplication: Karatsuba algorithm Recursive analysis: recursion tree, master theorem Proof of the master theorem
Lecture 4 (August 11, 2025)	Proof of the master theorem (complete proof) Karatsuba algorithm revisited Toom-Cook algorithm for integer multiplication Different representations of polynomials
Lecture 5 (August 12, 2025)	Closest-pair problem (full details)
Lecture 6 (August 18, 2025)	Fast Fourier Transform Faster Polynomial Multiplication
Lecture 7 (August 19, 2025)	Fast Fourier Transform (continued) Introduction to Dynamic Programming Maximum Weighted Independent Set in Path Graphs
Lecture 8 (August 25, 2025)	Maximum Weighted Independent Set in Path Graphs (continued) Introduction to Memoization Knapsack Problem
Lecture 9 (September 1, 2025)	Longest Common Subsequence Longest Increasing Subsequence Matrix Chain Multiplication
No Lecture (September 2, 2025)	First Quiz
Lecture 10 (September 8, 2025)	Matrix Chain Multiplication (continued) Introduction to Optimal Binary Search Tree Introduction to Arithmetic Parenthesization
Lecture 11 (September 9, 2025)	Optimal Binary Search Tree Arithmetic Parenthesization Introduction to Greedy Algorithms
Lecture 12 (September 13, 2025)	Huffman Coding
Midterm Week (September 13, 2025)
Lecture 13 (September 23, 2025)	Amortized Analysis Binary Heaps
Lecture 14 (October 7, 2025)	Graphs: Representations and Application Graph Traversal: BFS and DFS, their applications
Lecture 15 (October 11, 2025)	Finding Strongly Connected Components
Lecture 16 (October 13, 2025)	Single-Source Shortest Path Algorithm DP based approach: Bellman-Ford Algorithm Greedy approach: Dijkstra Algorithm
Lecture 17 (October 14, 2025)	Minimum Spanning Tree Optimal Substructure and Greedy Choice Property Prim's Algorithm: Comparison with Dijkstra's Algorithm Revisiting DP based approach to find a shortest path: Floyd-Warshall Algorithm
Lecture 18 (October 21, 2025)	Union-Find Data Structure: Analysis Kruskal's Algorithm
Lecture 19 (October 25, 2025)	Introduction to Network Flow Basic Definitions and Identities
Lecture 20 (October 27, 2025)	Ford-Fulkerson Algorithm Detailed Analysis
Lecture 21 (November 1, 2025)	Introducing Reduction: an Algorithm Design Paradigm Bipartite Perfect Matching Turing Reduction and Many-One Reduction
Lecture 22 (November 3, 2025)	Second Quiz NP-completeness, Cook-Levin Theorem Proving NP-completeness
Lecture 23 (November 4, 2025)	Introduction to Approximation Algorithms Approximation algorithms for Minimum Vertex Cover and Metric TSP Introduction to Randomization
Lecture 24 (November 10, 2025)	Analysis of Randomized Quick-Sort Randomized Approximation Algorithm for Max 3CNF Introduction to Parameterized Complexity Color Coding: FPT Algorithm for Longest Path Problem
Lecture 25 (November 11, 2025)	Revisiting Randomized Quick-Sort Introducing Linear Programming, Parallel Algorithm, and Streaming Algorithm

Design and Analysis of Algorithms (CS602), Odd Semester, 2025-2026

Design and Analysis of Algorithms (CS602),
Odd Semester, 2025-2026