Course Overview
This course is an advanced course with an emphasis on fundamental algorithms and advanced methods of algorithm design and analysis. Different instances of the course may focus on different sets of topics. A sample instance is given below.
Course Content
Algorithms on numbers: algorithms for arithmetic and modular arithmetic, algorithms on matrices and polynomials, factoring and primality testing. [10 lectures]
Algebraic graph algorithms: algorithms for clique, independent set and vertex cover using matrix product, matching algorithms using matrix inversion, perfect matching using polynomial identity testing, applications of inclusion-exclusion principle. [10 lectures]
Matroids and Network flows: Matroids and greedy strategy. Reduction of graph problems to matroid intersection and matroid parity. Algorithms for maximum flow and minimum cost maximum flow. Applications of flows. [14 lectures]
Intractability: Recap of NP-hardness and approaches to NP-hardness, ETH-based hardness, SETH-based hardness [8 lectures]
Text Books
- Algorithms by Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. McGraw-Hill Education, 2006. ISBN: 9780073523408.
- Combinatorial Optimization: Polyhedra and Efficiency (Volumes A, B and C) by Alexander Schrijver. Springer-Verlag Berlin Heidelberg, 2003. ISBN: 9783540443896.
References
- Parameterized Algorithms by M. Cygan, F. V. Fomin, L. Kowalik, D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk, and S. Saurabh. Springer International Publishing, 2015. ISBN: 9783319212753.
- Approximation Algorithms by Vijay V. Vazirani. Springer-Verlag Berlin Heidelberg, 2003. ISBN: 978-3-642-08469-0.
- Exact Exponential Algorithms by Fedor V. Fomin and Dieter Kratsch. Springer, 2010. ISBN: 978-3-642-26566-2.
Past Offerings
Course Metadata
| Item | Details |
|---|---|
| Course Title | Topics in Advanced Algorithms |
| Course Code | CS6007 |
| Course Credits | 3-0-0-3 |
| Course Category | PME |
| Proposing Faculty | Venkatesh Raman (Faculty, IMSc Chennai) and Krithika Ramaswamy |
| Approved on | Senate 30 of IIT Palakkad |
| Course status | New |