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.
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 |
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 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.