CS218: Design and Analysis of Algorithms (2023-24 Sem II)

• Schedule: Mon 8:30, Tue 9:30, Thu 10:35. LA001.

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

References:

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

• Useful notes from Prof. Sundar's course.

Lectures

Course introduction slides

Basics

Exercises (Lectures 1-7)

Slides pdf pptx keynote (Lectures 1-7)

• Lecture 1, 2 (Jan 4, 8) Binary search and variants

• Lecture 3 (Jan 9) Applications of binary search, O(·) notation. Analyzing and describing algorithms.

• Lecture 4 (Jan 11) Reduction to a subproblem. Maximum subarray sum problem.

• 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 18) Use of balanced binary search tree. Counting significant inversions. Repeated squaring.

Arithmetic

Exercises (Lectures 8-11)

Slides pdf pptx keynote (Lectures 8-11)

• Lecture 8 (Jan 23) Fibonacci. Integer squaring: Karatsuba's algorithm

• Lecture 9 (Jan 25) Integer multiplication: Karatsuba, Toom-Cook, History.

• Lecture 10, 11 (Jan 29, 30) Polynomial multiplication, convolution, Fast Fourier transform

Quiz 1 solutions

Programming assignment 1

Greedy algorithms, Dynamic programming

No slides. One can see notes from last year.

Boardwork from class

Exercises (Lectures 12-20)

• Lecture 12, 13 (Feb 1, 5) Subsequences, Interval scheduling, Proof of correctness of a greedy algorithm.

• Lecture 14, 15 (Feb 6, 8) Longest duration Interval scheduling (DP). Scheduling assignments with minimum lateness (Greedy).

• Lecture 16 (Feb 12) DP II: Iterated matrix multiplication.

• Lecture 17 (Feb 13) DP III: Subset sum.

• Lecture 18 (Feb 15) DP IV: Balanced margins.

• Lecture 19 (Feb 19) DP V: Edit distance, Sequence alignment

• Lecture 20 (Feb 20) DP VI: Shortest path with negative weights: Bellman Ford

midsem solutions

Network Flow

See notes from last year.

Exercises (Lectures 21-24)

• Lecture 21-24 (Mar 4, 5) Network Flow, Max flow min cut theorem, Augmenting path algorithm, Applications: taxi scheduling

P, NP, NP-completeness

slides

Exercises (Lectures 25-28)

• Lecture 25-28 (Mar 7, 18, 19) P, NP, history, reductions, NP-completeness.

Programming assignment 2

Quiz 2 solutions

Advanced algorithms

Exercises (Lectures 29-)

• Lecture 29 (Mar 21) slides Minimum Makespan 2-approximation algorithm

• Lecture 30 (Mar 26) Linear Programming and application to curve fitting Tim Roughgarden's notes

• Lecture 31 (Mar 28) slides Min vertex cover: approximation via LPs

• Lecture 32-33 (Apr 1-2) Boardwork Randomized algorithms, 2-dimensional linear programming

• Lecture 34 (Apr 4) Boardwork Simplex algorithm for linear programming (Ref: CLRS chapter 29)

• Lecture 35 (Apr 8) Slides Error correction algorithm in QR codes

• Lecture 36 (Apr 12) Long paths via color coding by Prof. Akash Kumar

Endsem solutions