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
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.
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.
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
Lecture 1 (July 29) Binary search and applications 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 7 (Aug 12) Finding visible lines: iterative approach 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.
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 13 (Sep 2) Interval scheduling: maximizing total length, Subset Sum video
Lecture 14 (Sep 6) Balanced Margins video
Midsem Week Sep 10-18 Midsem solutions
Lecture 17 (Sep 21) Huffman Codes video
Lecture 18 (Sep 23) Huffman codes correctness video
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
Slides for lectures 24-27
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
Assignment 2 Solution
Slides for Lectures 28-29
Homework (not for grading, updated on Oct 24)
Lecture 29 (Oct 21) Load balancing greedy analysis, 3/2 approximation video
Slides 1 Slides 2
Homework (not for grading, updated on Oct 30)
Lecture 30 (Oct 25) NP introduction video
Lecture 31 (Oct 26) NP-completeness video