MTL342: Analysis and Design of Algorithms

Monsoon semester, 2021-22

Lectures by:
Ashutosh Rai.

Time of the class:
Tuesdays, Thursdays and Fridays 11:00am to 11:50pm.

Office hours:
by email appointment.

Teaching assistants:
Sharut Gupta: mt6170250@maths.iitd.ac.in
Gauri Gupta: mt6170207@maths.iitd.ac.in


Syllabus:
We will roughly cover the following topics: Asymptotic notation; DFS, BFS and some applications; Greedy algorithms: MST, shortest path etc; Divide and Conquer: sorting, matrix multiplication etc; Dynamic Programming: scheduling, subset sum etc; Flow algorithms; NP-completeness and reductions.



Course Material:
We will follow the book "Algorithm Design" by Jon Kleinberg and Eva Tardos [KT] published by Pearson. A low price edition is available in India.
Lecture slides for the chapters of the book can be found here.
I might sometimes refer to some other material, in which case I will mention that. Students can also refer to these additional texts if they are interested.
  1. Introduction to Algorithms (PHI)
    by Cormen, Leiserson, Rivest, and Stein [CLRS]
  2. The Algorithm Design Manual (Springer)
    by Steven Skiena


Credits:
The course will be evaluated on a 100 point scale.
There will be 3-4 assignments which will be worth 40 points together.
The minor and major will be worth 25 and 35 points respectively.
To pass or audit pass the course (i.e., to get a D grade), you need to have at least 30 points.


Course outline:
  1. Weeks 1-2: Topics: Asymptotic notations, Graph represntation, BFS, DFS and applications. References: [KT] Chapters 2 and 3, [CLRS] Chapters 2 and 3.
  2. Weeks 3-4: Topics: Greedy algorithms, Exchange argument, Interval Scheduling, Caching, Single-Sourse Shortest Paths (Dijkstra's algorithm), Minimum Spanning Tree (Prim's and Kruskal's algorithms), Union-Find data structure. Reference: [KT] Chapter 4.
  3. Weeks 5-6: Topics: Divide and Conquer, Recurrences and solving them, Counting Inversions, Closest Pair of Points, Interger Multiplication, Strassen's Algorithm for Matrix Multiplication, Convolutions and Fast Fourier Transforms. References: [KT] Chapter 5 and [CLRS] Chapter 28.2.
  4. Weeks 7-8: Topics: Dynamic Programming, Weighted Interval Scheduling, Principles of Dynamic Programming: Memoization and subproblems, Segmented Least Squares, Subset-Sum and Knapsack, RNA Secondary Structure, Sequence Alignment, Shortest Paths in a graph: the Bellman-Ford algorithm. References: [KT] Chapter 6.
  5. Weeks 9-10: Topics: Network Flow: The Max-flow problem, Ford-Fulkerson algorithm, Max-flow Min-cut theorem, Choosing good augmenting paths, Preflow-Push algorithm, Applications of Max-flow Min-cut: Bipartite Matching, Disjoint paths, Circulation with demands, Survey design. References: [KT] Chapter 7.
  6. Weeks 11-12: Topics: NP-completeness and intractibility: Polymonial time reductions, Satisfiability, Reduction from Satisfiability to Vertex Cover, Defining P, NP and efficient certification, NP-completeness, Circuit-SAT, 3SAT, Traveling Salesman, Hamiltonian Paths. Dealing with NP-completeness: Finding small vertex covers, (Weighted) Maximum Independent Set on trees, Approximation algorithms: Makespan and Vertex Cover using LP. References: [KT] Chapters 8, 10 and 11.