Schedule (July 29 onwards): Mon 11:35, Tue 8:30, Thu 9:30

New meeting link Webex link Meeting number:170 166 9909 Password: apPBmvH2M77

**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.

**References:**

Primary reference J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005.

Useful notes from Prof. Sundar's course.

Rajeev Motwani, Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, 1995.

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 videoLecture 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 videoLecture 6 (Aug 10) Maximum subarray: strengthening the subproblem video

Repeated squaring videoLecture 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 videoAug 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.

- Watch these introduction lecture recordings from 2020: Slides Greedy. Dynamic Programming. Needs IITB SSO login

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) videoLecture 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 videoLecture 17 (Sep 21) Huffman Codes video

Lecture 18 (Sep 23) Huffman codes correctness video

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

Homework (not for grading, updated on Oct 16)

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

Homework (not for grading, updated on Oct 24)

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

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

Homework (not for grading, updated on Oct 30)