CS G526 Advanced Algorithms and Complexity
Aug–Dec 2026
Table of Contents
When and Where
Lectures
- Time: Mon Wed Fri 9:00 AM – 9:50 AM
- Place: D103
Exams
- Midsem Exam: 07 October Wednesday, 9:30 AM – 11:00 AM
- Comprehensive Exam: 04 December Friday, 10:00 AM – 1:00 PM
Google Calendar
Click here to add the course calendar or scan the QR code below.
People
- Students
- M.E. (CSE) 1st year, 1st semester
- Ph.D. students
- Staff
- Aniket Basu Roy (Instructor-in-Charge)
- Teaching assistants (TBA)
Zulip Chat
Click here to join the course Zulip chat or scan the QR code below.
Course Webpage
Click here to visit the course webpage or scan the QR code below.
References
- [KT] Kleinberg, J., & Tardos, E. (2006). Algorithm Design. Pearson/Addison-Wesley.
- [DPV] Dasgupta, S., Papadimitriou, C. H., & Vazirani, U. V. (2006). Algorithms. McGraw-Hill.
- [Vaz] Vazirani, V. V. (2001). Approximation Algorithms. Springer.
- [MR] Motwani, R., & Raghavan, P. (1995). Randomized Algorithms. Cambridge University Press.
A Tentative List of Topics
Preliminaries
- Motivation and Warmup
- Growth of Functions. Asymptotic Notations
- Review of Graph Theory Basics
Algorithmic Paradigms
- Greedy Algorithms
- Divide and Conquer
- Dynamic Programming
- Linear Programming
Computational Complexity
- Complexity Classes P, NP, PSPACE
- Reductions
Advanced Topics
- Approximation Algorithms
- Randomized Algorithms
- Local Search
- Hardness of Approximation
Evaluation and Grading Policy
| Comprehensive Exam | 40% |
| Midsem Exam | 25% |
| Others | 35% |
Continuous Evaluation Components
- Problem Sets (4x)
- Paper Reading, Report Writing, Presenting
- Scribing