Schedule: Tue, Fri 2-3:30 pm. LH302.
Office hours: Fri 3:30-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: Undecidability, 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.
References:
Primary reference J. Kleinberg and E. Tardos, Algorithm Design, Addison Wesley, 2005.
Useful notes from Prof. Sundar's course.
Notes from CS601 2021
Rajeev Motwani, Prabhakar Raghavan, Randomized algorithms, Cambridge University Press, 1995.
Exercises (Lectures 1-6)
Slides (Lectures 1-5)
Lecture 1 (Jan 3) Binary search and variants
Lecture 2 (Jan 6) Reduction to a subproblem (max subarray sum), divide and conquer (non-dominated points)
Lecture 3 (Jan 10) Integer multiplication: Karatsuba's algorithm
Lecture 4 (Jan 13) Polynomial multiplication or convolution
Lecture 5 (Jan 17) Fast Fourier transform
Lecture 6 (Jan 20) Problems discussion
Exercises (Lectures 7-11)
Lecture 7 (Jan 31) Introduction to greedy algorithms
Lecture 8 (Feb 3) Greedy I: Interval scheduling
Lecture 9 (Feb 7) DP I: Interval scheduling with largest total length
Lecture 10 (Feb 8) DP II: Subset sum
Lecture 11 (Feb 10) DP III: Iterated matrix multiplication
Lecture 12 (Feb 14) DP IV: Balanced margins, Sequence alignment or edit distance
Lecture 13 (Feb 15) Problem discussion
Lecture 14 (Feb 17) DP V: Shortest path in a directed graph with negative edge weights
Slides (Network flow)
Exercises (Lecture 16-19)
Lecture 15 (Feb 28) Introduction to Huffman codes
Lecture 16 (Mar 1) Network flow: Residual graph
Lecture 17 (Mar 3) Network flow: Ford Fulkerson algorithm
Lecture 18 (Mar 17) Linear programming by Prof. Akash Kumar Reference notes
Lecture 19 (Mar 21) Applications of network flow: taxi scheduling
Slides (NP, NP-complete, reductions)
Slides (LP and weighted vertex cover)
Exercises (lecture 20-24)
Lecture 20 (Mar 24) P, NP, various problems in or not in P
Lecture 21 (Mar 25) Counting distinct elements using limited memory (Guest lecture by Prof. Kuldeep Meel) Reference
Lecture 22 (Mar 28) NP-complete, P vs NP, Satisfiability is NP-complete
Lecture 23 (Mar 31) SAT to IND-SET reduction. IND-SET to Vertex Cover. 2-approximation algorithm for VC.
Lecture 24 (Apr 11) Linear programming algorithms and application to weighted vertex cover.