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:
1. Kakadiya Harshkumar Pravinbhai (harshkumar24@cse.iitk.ac.in)
2. Khushwant Kaswan (khushwantk24@cse.iitk.ac.in )
3. Shivam Maurya (shivammrya24@cse.iitk.ac.in)
4. Vansh Kunwar Ji (vanshkunwarj25@iitk.ac.in)
5. Varad Prabhakar Shinde (vpshinde25@iitk.ac.in)

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	References
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

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

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