Neural Sync Active
BSCS4021 - Advanced Algorithms
Registry Synced
BSCS4021 - Advanced Algorithms
443 words
2 min read
| Field | Value |
|---|---|
| Course Code | BSCS4021 |
| Level | Degree Level Course |
| Credits | 4 |
| Type | Elective |
| Pre-requisites | None |
📖 Description
To introduce advanced ideas in design of algorithms; To study the performance guarantees of algorithms; To introduce methods for coping with NP-hard problems.
🗓️ Weekly Syllabus
| Week | Topic |
|---|---|
| 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 |
📚 Books & Resources
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.
less