CS601: Algorithms and Complexity (2020-21 Sem I)

Online Mode:

All the course material is being put up here (accessible via IITB Gsuite account).

Please use the code qdhil2i to join the CS601 Team on MSTeams. I think it will only work if you are logged in to MS Teams via your iitb id (will need SSO).

Those who are not registered but still want to watch lectures/get emails, please fill this .

Regular Schedule (second week onwards): Wed, Fri. 9:30-11. We will come up with a way to divide these slots among the students.

Course Contents:

Principles of designing and analyzing algorithms: Basic principles like induction/recursion. Basic paradigms like Divide and Conquer, Dynamic Programming, Greedy Algorithms. Beyond the basics: Bipartite Matching, Network Flow. Reductions.

Complexity: Polynomial time and the Complexity classes NP, co-NP. NP-hardness and NP-completeness.

Randomization in Algorithm Design: Random variables, Linearity of expectation, Applications like approximate max-cut, quicksort, hashing.

Course not recommended for students who have done or will do CS218/CS218m because of the large overlap. They are welcome to watch lectures in the later part of the course.

Pre-requisites: You are expected to know some basic data structures and algorithms. Run-time analysis, O-notation, Recursion. Basic probability and combinatorics. Basic data structures -- array, list, stack. Basic graph theory -- cycles, trees, depth-first search, breadth-first search.

Take this Self Assessment Quiz to check your pre-requisites.

Grading: in-video quizzes, assignments, final exam (no clarity). Audit requirement: BC or above in final grading.

References: