Algorithms and Complexity

General information

Course Number : CS 601
Instructor : Mrinal Kumar
Email : first name AT cse DOT iitb DOT ac DOT in
Lectures: Monday and Thursday 2pm-3:30pm
Office hours: Monday 1pm-2pm, CC 308

Teaching assistants

Office hours for TAs: Thursdays 1pm-2pm, in Meeting Room 321 in CC Building.

Logistics

The lectures/office hours will be in person, and we will use Moodle for announcements and discussions. An MS Teams page has been set up by the TAs and details shared on Moodle. The page can be used for discussions.

Grading

Grades will be based on a mid-sem (25%), a final (40%), two in-class quizzes (30%) and class participation (5%).
There will be a few problem sets through the course that will not be graded (but are highly recommended).

Description

This is a fairly standard first course aimed at studying the basic principles of algorithm design and a short introduction to computational complexity. The course is open for CS Masters/PhD students, and is NOT recommended for anybody who has done or will do CS218/CS213/CS218 minor/CS213 minor due to significant overlap. I will assume some familiarity with the material in a typical undergraduate class on data structures and algorithms. The course would be largely mathematical, and will involve design of algorithms as well as formal proofs of correctness and bounds on performance of such algorithms.

We will see some of the algorithm design paradigms/techniques and their applications to design algorithms for various computational problems. We will also discuss the notion of computational hardness and see some of the strategies for coping with computational hardness. We will also spend a few lectures looking at the role of randomness in algorithm design.

References

We will follow the textbooks by Kleinberg and Tardos and the one by Cormen et al. for a large part of the course. Both these books contain a fairly large number of exercises and I highly encourage you to check them out.

Schedule