MTL342: Analysis and Design of Algorithms

Monsoon semester, 2025-26

Lectures by:
Ashutosh Rai.

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

Office hours:
by email appointment.

Teaching assistants:
Soumen Mandal: maz208750@maths.iitd.ac.in
Sahiba: maz238701@maths.iitd.ac.in
Atishay Aggarwal: mt6210941@iitd.ac.in

Tutorials:
On Mondays, Tuesdays, Thursdays and Fridays, 1pm-2pm in LH521 (depending on your group).


Syllabus:
We will roughly cover the following topics: Asymptotic notation; Recursion; 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 mostly 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. Algorithms
    by Jeff Erickson [JE]: The book is freely available here and can turn out to be a joyful read even for those who want to learn the subject on their own.
  2. Introduction to Algorithms, 3rd Edition (PHI)
    by Cormen, Leiserson, Rivest, and Stein [CLRS]


Credits:
The course will be evaluated on a 100 point scale.
The minor and major will be worth 30 and 40 points respectively.
The quizzes will be worth 30 points.
To audit pass the course, you need to have at least 40 points, at least 30 of which should come from minor and major.
There will be only one make-up exam to make up for missed quizzes or minor. One can appear in at most one make-up exam, either the re-quiz or the re-minor, both of which will be conducted before the major, and would contain the full syllabus.
Attendance of 75% is required to get credits for the course.


Lectures and References:
  • Lecture 1: Introduction to Algorithms, Running Time and Correctness through Finding Maximum and Stable Matching. Reference: [KT] 1.1.
  • Lecture 2: Stable Matching (cont.), Lower Bounds: Max and Sorting. Reference: [KT] 1.1, [CLRS] 8.1, Lecture notes by Jeff Erickson.
  • Lecture 3: Asymptotic notations and some common running times. Reference: [KT] 2.1, 2.2, 2.4.
  • Lecture 4: Recursion: Merge Sort and Solving Recurrences, Master Theorem. Reference: [KT] 5.1, 5.2, [CLRS] 4.3, 4.4, 4.5 (Optional: 4.6: Proof of Master Theorem), [JE] 1.7.
  • Lecture 5: Recursion: Tower of Hanoi and Counting Inversions. Reference: [JE] 1.3, [KT] 5.3.
  • Lecture 6: Recursion: Closest Pair of Points and Integer Multiplication. Reference: [KT] 5.4, 5.5.
  • Lecture 7: Recursion: Matrix Multiplication, Introduction to Convolutions. Reference: [CLRS] 4.2, [KT] 5.6. Also, there is an excellent video about convolutions on 3Blue1Brown.
  • Lecture 8: Recursion: Computing Convolutions through Fast Fourier Transforms. Reference: [KT] 5.6. For a somewhat deeper dive, lecture notes by Jeff Erickson can be looked at.
  • Lecture 9: Graph Algorithms: BFS and DFS. Reference: [JE] 5.1 to 5.6.
  • Lecture 10: BFS and DFS: Finding all connected components and testing bipartiteness. Reference: [KT] 3.2 to 3.4.
  • Lecture 11: Directed Graphs: Checking Strong Connectivity and Finding all Strongly Connected Components in linear time. Reference: [JE] 6.5, 6.6.
  • Lecture 12: Directed Graphs: Recognizing DAGs and finding topological ordering. Reference: [KT] 3.6.
  • Lecture 13: Greedy Algorithms: Introduction and Interval Scheduling. Reference: [KT] 4.1.
  • Lecture 14: Greedy Algorithms: Interval Partitioning and Scheduling to Minimize Lateness. Reference: [KT] 4.1, 4.2.
  • Lecture 15: Greedy Algorithms: Optimal Caching. Reference: [KT] 4.3.
  • Lecture 16: Greedy Algorithms: Dijkstra's Algorithm for shortest path. Reference: [KT] 4.4.
  • Lecture 17: Greedy Algorithms: MST: Prim's, Kruskal's and Reverse Delete. Reference: [KT] 4.5.
  • Lecture 18: Greedy Algorithms: Implementing Prim's and Kruskal's, Union-Find Data Structure. Reference: [KT] 4.6.
  • Lecture 19: Greedy Algorithms: Huffman Codes. Reference: [KT] 4.8.
  • Lecture 20: Dynamic Programming: Iteration Vs Memoization, Weighted Interval Scheduling, Fibonacci. Reference: [KT] 6.1, 6.2, [JE] 3.1.
  • Lecture 21: Dynamic Programming: Segmented Least Squares. Reference: [KT] 6.3.
  • Lecture 22: Dynamic Programming: Subset Sum and Knapsack. Reference: [KT] 6.4.
  • Lecture 23: Dynamic Programming: RNA Secondary Structure. Reference: [KT] 6.5.
  • Lecture 24: Dynamic Programming: Sequence Alignment, Space Reduction for Sequence Alignment. Reference: [KT] 6.6, 6.7.
  • Lecture 25: Dynamic Programming: Bellman-Ford for Shortest Paths. Reference: [KT] 6.8.
  • Lecture 26: Network Flows: Introduction, Ford-Fulkerson Algorithm. Reference: [KT] 7.1.
  • Lecture 27: Network Flows: Max-Flow Min-Cut, Analysis of Ford-Fulkerson. Reference: [KT] 7.2.
  • Lecture 28: Network Flows: Choosing good aumneting paths. Reference: [KT] 7.3.
  • Lecture 29: Network Flows: Preflow-Push-I. Reference:: [KT] 7.4.
  • Lecture 30: Network Flows: Preflow-Push-II. Reference:: [KT] 7.4.
  • Lecture 31: Applications of Network Flow: Bipartite Matching, Disjoint Paths, Circulation With Demands, Lower Bounds on Edges etc. Reference: [KT] 7.5-7.11.
  • Lecture 32: NP-Completeness: Introduction to reductions. Reference: [KT] 8.1.
  • Lecture 33: NP-Completeness: Satisfiability. Reference: [KT] 8.2.
  • Lecture 34: NP-Completeness: Defining P and NP. Reference: [KT] 8.3.
  • Lecture 35: NP-Completeness: P Vs NP, Circuit-SAT and 3SAT. Reference: [KT] 8.4.
  • Lecture 36: NP-Completeness: Traveling Salesman Problem and Hamiltonian Cycle. Reference: [KT] 8.5.
  • Lecture 37: NP-Completeness: Graph Coloring. Reference: [KT] 8.7.