Schedule: Mon 9:30, Tue 10:35, Thu 11:35. LH102.
Office hours: Fri 4-5 pm. CC315.
Course Contents:
Algorithms: Basic principles like induction/recursion. Basic paradigms like Divide and Conquer, Dynamic Programming, Greedy Algorithms. Beyond the basics: Network Flow and its applications. Reductions.
Complexity: Polynomial time and the Complexity classes NP, co-NP. NP-hardness and NP-completeness.
Advanced topics: Randomized algorithms, Approximation algorithms. E.g., approximate max-cut, load balancing, min-cut, linear programming, QR codes.
References:
Primary reference J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005.
Useful notes from Prof. Sundar's course.
Exercises (Lectures 1-7)
Slides (Lectures 1-7)
Lecture 1, 2 (Jan 6, 7) Binary search and variants
Lecture 3 (Jan 9) Applications of binary search, O(ยท) notation. Analyzing and describing algorithms.
Lecture 4 (Jan 13) Reduction to a subproblem. Maximum subarray sum.
Lecture 5 (Jan 15) Solving more than required. Interval containment problem.
Lecture 6 (Jan 16) Divide and conquer. Area covered by rectangles.
Lecture 7 (Jan 20) Use of balanced binary search tree. Counting significant inversions. Repeated squaring.
Exercises (Lectures 8-11)
Slides (Lectures 8-11)
Lecture 8 (Jan 21) Fibonacci. Integer squaring: Karatsuba's algorithm
Lecture 9 (Jan 27) Integer multiplication History, Polynomial multiplication, convolution.
Lecture 10, 11 (Jan 28, 30) Polynomial multiplication, convolution, Fast Fourier transform
No slides. Handwritten slides from previous offering.
Exercises (Lectures 12-21)
Lecture 12, 13 (Jan 31, Feb 3) Subsequences, Interval scheduling, Proof of correctness of a greedy algorithm. (Kleinberg Tardos Section 4.1)
Lecture 14, 15 (Feb 4, 6) Longest duration Interval scheduling (DP). Partitioning a set of intervals into minimum number of mutually overlapping sets. (Kleinberg Tardos Section 6.1)
Lecture 16 (Feb 7) DP variants: Subset Sum, Iterated matrix multiplication. (Kleinberg Tardos Section 6.4)
Lecture 17 (Feb 11) DP variants: Iterated matrix multiplication continued. Some ideas around minimum spanning tree.
Lecture 18 (Feb 13) DP variants: Balanced margins.
Lecture 19, 20 (Feb 16, 17) Shortest path with negative weights: Bellman Ford. All pairs shortest paths: Floyd Warshall. (Kleinberg Tardos Section 6.8)
Exercises (Lectures 22-28)
Lecture 22, 23 (Mar 4, 6) Stable matching. Gale-Shapley algorithm. (Kleinberg Tardos Section 1.1)
Lecture 24-28 (Mar 10, 11, 13, 17, 18) Network Flow, Max flow min cut theorem, Augmenting path algorithm, Applications (Kleinberg Tardos Chapter 7)
See notes from last year.
Exercises (Lectures 29-32)
Lecture 29-31 (Mar 20, 24, 25) P, NP, history, reductions, NP-completeness.
Lecture 32 (Mar 27) Subset sum, TSP problems are NP-complete. (Kleinberg Tardos Sections 8.7, 8.8)
Exercises (Lectures 33-)
Lecture 33 (Apr 1) Linear Programming and application to curve fitting Tim Roughgarden's notes
Lecture 34 (Apr 3) Simplex algorithm for linear programming (Ref: CLRS chapter 29)
Lecture 35-36 (Apr 7, 8) notes Minimum Makespan 2-approximation algorithm
Lecture 37-38 (Apr 15, 17) Slides Error correction algorithm in QR codes