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