Applications Open now for September 2024 Batch | Applications Close: Sep 15, 2024 | Exam: Oct 27, 2024

Applications Open now for September 2024 Batch | Applications Close: Sep 15, 2024 | Exam: Oct 27, 2024

Degree Level Course

Advanced Algorithms

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

by Neeldhara Misra

Course ID: BSCS4021

Course Credits: 4

Course Type: Elective

Pre-requisites: None

Course structure & Assessments

12 weeks of coursework, weekly online assignments, 2 in-person invigilated quizzes, 1 in-person invigilated end term exam. For details of standard course structure and assessments, visit Academics page.

WEEK 1 Greedy Algorithms: Storing Files on Tape; Scheduling Classes; Stable Matchings
WEEK 2 Matroids: A Generic Optimization Problem, Motivating the Definition, Examples of Matroids, Scheduling with Deadlines
WEEK 3 Dynamic Programming: Longest Increasing Subsequence, Edit Distance, Subset Sum, Optimal BSTs
WEEK 4 Maximum Flows: Flows, Cuts, Maxflow-Mincut, Augmenting Paths, Bipartite Matchings, Other Settings
WEEK 5 Applications of Flows: Exam Scheduling, Baseball Elimination, Project Selection
WEEK 6 NP-hardness: P, NP, NP-hardness, NP-completeness, Reductions and SAT, 3SAT, Maximum Independent Set, Graph Coloring, Subset Sum
WEEK 7 Approximation Algorithms: Introduction to Approximation Frameworks, Vertex Cover via Maximal Matchings, Vertex Cover via LP rounding, TSP, Set Cover
WEEK 8 Randomized Algorithms – Monte Carlo v. Las Vegas, Min-Cut Algorithm, MAX SAT via the Probabilistic Methods, 2SAT via Markov Chains, Primality Testing
WEEK 9 Exact Algorithms – Branch and Bound, An Inclusion-Exclusion approach to Hamiltonian Path, Dynamic Programming for TSP, Local Search
WEEK 10 Parameterized Algorithms – Closest String, Iterative Compression for FVS, Randomized Algorithm for k-Path, DP over subsets - Set Cover
WEEK 11 Kernelization – Vertex Cover, Matrix Rigidity, Feedback Arc Set on Tournaments, Max Sat, Edge Clique Cover
WEEK 12 Practical Approaches to Coping with Hardness – SAT Solvers, SAT reductions, LP solvers, LP reductions
+ Show all weeks

Prescribed Books

The following are the suggested books for the course:

Cormen, Leiserson, Rivest, and Stein. Introduction to Algorithms. 2nd ed. Cambridge, MA: MIT Press, 2001.

David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms

About the Instructors

Neeldhara Misra
Faculty, CSE, IIT Gandhinagar

Neeldhara Misra is an Assistant Professor of Computer Science and Engineering at the Indian Institute of Technology, Gandhinagar. Her primary research interest involves the design and analysis of efficient algorithms for “hard” problems in general, and parameterized algorithms in particular. The problems considered are typically concerned with combinatorial optimization, frequently in the context of graph theory, social choice, games, geometry, and constraint satisfaction.