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; NPcompleteness 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 34 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 12: Topics: Asymptotic notations, Graph represntation, BFS, DFS and applications. References: [KT] Chapters 2 and 3, [CLRS] Chapters 2 and 3.

Weeks 34: Topics: Greedy algorithms, Exchange argument, Interval Scheduling, Caching, SingleSourse Shortest Paths (Dijkstra's algorithm), Minimum Spanning Tree (Prim's and Kruskal's algorithms), UnionFind data structure. Reference: [KT] Chapter 4.

Weeks 56: 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 78: Topics: Dynamic Programming, Weighted Interval Scheduling, Principles of Dynamic Programming: Memoization and subproblems, Segmented Least Squares, SubsetSum and Knapsack, RNA Secondary Structure, Sequence Alignment, Shortest Paths in a graph: the BellmanFord algorithm. References: [KT] Chapter 6.

Weeks 910: Topics: Network Flow: The Maxflow problem, FordFulkerson algorithm, Maxflow Mincut theorem, Choosing good augmenting paths, PreflowPush algorithm, Applications of Maxflow Mincut: Bipartite Matching, Disjoint paths, Circulation with demands, Survey design. References: [KT] Chapter 7.

Weeks 1112: Topics: NPcompleteness and intractibility: Polymonial time reductions, Satisfiability, Reduction from Satisfiability to Vertex Cover, Defining P, NP and efficient certification, NPcompleteness, CircuitSAT, 3SAT, Traveling Salesman, Hamiltonian Paths. Dealing with NPcompleteness: 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.
