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. Introduction to Algorithms (PHI) by Cormen, Leiserson, Rivest, and Stein [CLRS] 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: Weeks 1-2: Topics: Asymptotic notations, Graph represntation, BFS, DFS and applications. References: [KT] Chapters 2 and 3, [CLRS] Chapters 2 and 3. 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. 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. 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. 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. 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.