To introduce advanced ideas in design of algorithms; To study the performance guarantees of algorithms; To introduce methods for coping with NP-hard problems.

Lectures-Tutorials-Practicals-Credits: 4-0-0-4

Week 1: Greedy algorithms; Interval scheduling and file storage problems; Stable matching.

Week 2: Matroids and greedy optimization; Matroid properties and examples; Scheduling with deadlines.

Week 3: Dynamic programming; Classic problems (LIS, edit distance, subset sum, optimal BSTs).

Week 4: Maximum flow theory; Flows, cuts, max-flow min-cut; Augmenting paths; Bipartite matching.

Week 5: Applications of flows; Scheduling, elimination problems, and project selection.

Week 6: Computational complexity; P , NP , NP-completeness; Reductions; SAT and classic NP-hard problems.

Week 7: Approximation algorithms; Vertex cover (matching and LP-based); TSP and set cover.

Week 8: Randomized algorithms; Monte Carlo vs Las Vegas; Min-cut; Probabilistic methods; 2SAT and primality testing.

Week 9: Exact algorithms; Branch and bound; Inclusion-exclusion; DP for TSP; Local search.

Week 10: Parameterized algorithms; Fixed-parameter tractability; Closest string; k-path; Subset DP techniques.

Week 11: Kernelization techniques; Vertex cover kernels; Structural reductions; Applications to classic problems.

Week 12: Practical approaches to hardness; SAT solvers; LP solvers; Problem reductions and real-world optimization.