## 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 to check your pre-requisites.

References:

### Lectures

#### Basics

Slides for Lectures 1-10

Homework (Not for grading, Updated on Aug 30)

Quizzes on Moodle: Quiz 1 Quiz 2 Quiz 3

• Lecture 1 (July 29) Binary search and applications video

• Lecture 2 (Aug 2) Analyzing algorithms video
Reducing to a subproblem video

• Lecture 3 (Aug 3) Finding minimum and second-minimum in an array video

• Lecture 4 (Aug 5) Expected number of comparisons to compute min and second-min video

• Lecture 5 (Aug 9) Finishing expected number of comparisons video
Maximum subarray sum problem video

• Lecture 6 (Aug 10) Maximum subarray: strengthening the subproblem video
Repeated squaring video

• Lecture 7 (Aug 12) Finding visible lines: iterative approach video

• Lecture 8 (Aug 16) Finding visible lines: iterative approach (with sorting) video (mistakes in the video)

• Lecture 9 (Aug 17) Finding visible lines: divide and conquer video
Square of an integer: divide qnd conquer video

• Aug 19 Q&A session video

• Lecture 10 (Aug 26) Square of an integer: divide and conquer analysis video
Improved divide and conquer for squaring video
In the second video, the time complexity of various multiplication algorithms is described incorrectly. Here are the correct complexities.

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

• Lecture 11 (Aug 30) Greedy algorithms: interval scheduling video

• Lecture 12 (Aug 31) Interval scheduling 2 video
Interval scheduling: maximizing total length (DP) video

• Lecture 13 (Sep 2) Interval scheduling: maximizing total length, Subset Sum video

• Lecture 14 (Sep 6) Balanced Margins video

• Lecture 15 (Sep 7) Optimal Binary Search Tree video
Sequence Alignment video

Midsem Week Sep 10-18 Midsem solutions

• Lecture 16 (Sep 20) Summarizing Greedy and DP approaches video
Optimal prefix codes introduction video

• Lecture 17 (Sep 21) Huffman Codes video

• Lecture 18 (Sep 23) Huffman codes correctness video

#### Bipartite Matching

Slides for Lecture 19-23

Homework (not for grading, updated on Oct 10)

Quizzes on Moodle: Quiz 6 Quiz 7

• Lecture 19 (Sep 27) Bipartite matching introduction video

• Lecture 20 (Sep 28) Augmenting path algorithm video

• Lecture 21 (Sep 30) Finding augmenting path, Hall's theorem video

• Lecture 22 (Oct 4) Taxi scheduling video

• Lecture 23 (Oct 5) Taxi scheduling via bipartite matching video

#### Randomized Algorithms

Slides for lectures 24-27

Homework (not for grading, updated on Oct 16)

Quiz8

• Lecture 24 (Oct 7) Randomized algorithms, Approximate median video

• Lecture 25 (Oct 11) Approximate median analysis video

Analysis for sampling without replacement

• Lecture 26 (Oct 12) Minimum cut: randomized algorithm video

• Lecture 27 (Oct 14) Minimum cut analysis video

#### Approximation Algorithms

Slides for Lectures 28-29

Homework (not for grading, updated on Oct 24)

Quiz 9

• Lecture 28 (Oct 18) Load Balancing video Greedy gives 2-approximation video

• Lecture 29 (Oct 21) Load balancing greedy analysis, 3/2 approximation video

#### NP, NP-completeness

Homework (not for grading, updated on Oct 30)

• Lecture 30 (Oct 25) NP introduction video

• Lecture 31 (Oct 26) NP-completeness video

• Lecture 32 (Oct 28) Summarizing NP-complete, NP-hard video
SAT is NP-complete video
Independent Set is NP-complete video

Endsem solutions