CS601: Algorithms and Complexity (2021-22 Sem I)

Course Contents:

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: Undecidability, Polynomial time and the Complexity classes NP, co-NP. NP-hardness and NP-completeness.

Randomization: Random variables, Linearity of expectation, Applications like approximate max-cut, quicksort, min-cut.

Course not recommended for students who have done or will do CS218/CS218m because of the large overlap.

Pre-requisites: Comfort with abstraction. Basic Run-time analysis, O-notation, Recursion. Basic probability and combinatorics. Basic data structures -- array, list, stack. Basic graph algorithms -- cycles, trees, depth-first search, breadth-first search. Take this Self Assessment Quiz to check your pre-requisites.




Slides for Lectures 1-10

Homework (Not for grading, Updated on Aug 30)

Quizzes on Moodle: Quiz 1 Quiz 2 Quiz 3

Assigment 1 Solution

Greedy Algorithms and Dynamic Programming

Slides for Lecture 11-18

Homework (Not for grading, updated on Sep 29)

Quizzes on Moodle: Quiz 4 Quiz 5

Midsem Week Sep 10-18 Midsem solutions

Bipartite Matching

Slides for Lecture 19-23

Homework (not for grading, updated on Oct 10)

Quizzes on Moodle: Quiz 6 Quiz 7

Randomized Algorithms

Slides for lectures 24-27

Homework (not for grading, updated on Oct 16)


Analysis for sampling without replacement

Assignment 2 Solution

Approximation Algorithms

Slides for Lectures 28-29

Homework (not for grading, updated on Oct 24)

Quiz 9

NP, NP-completeness

Slides 1 Slides 2

Homework (not for grading, updated on Oct 30)

Endsem solutions