CS G526 Advanced Algorithms and Complexity
Aug–Dec 2026
Table of Contents
- When and Where
- People
- Zulip Chat
- Course Webpage
- References
- A Tentative List of Topics
- Evaluation and Grading Policy
- Continuous Evaluation Components
- Office Hours
- Handout
- Lecture Schedule
-
- Lecture 0 (03/08)
- Lecture 1 (05/08)
- Lecture 2 (07/08)
- Lecture 3 (10/08)
- Lecture 4 (12/08)
- Lecture 5 (14/08)
- Lecture 6 (17/08)
- Lecture 7 (19/08)
- Lecture 8 (21/08)
- Lecture 9 (24/08)
- Lecture 10 (31/08)
- Lecture 11 (02/09)
- Lecture 12 (07/09)
- Lecture 13 (09/09)
- Lecture 14 (11/09)
- Lecture 15 (16/09)
- Lecture 16 (18/09)
-
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)
- K Tharian Thomas (Teaching assistant)
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
Office Hours
- When: Fridays, 11:00 AM – 12:00 noon
- Where: D256
Handout
- pdf (As submitted to the Instruction Office. Last updated on 14/08)
Lecture Schedule
Lecture 0 (03/08)
- Administrivia, slides
Lecture 2 (07/08)
- Asymptotic Notations, Review of Graph Theory Basics
- Scribe: Amoghavarsha, Sakshi pdf
Lecture 3 (10/08)
- Job Scheduling, KT 4.1
Lecture 4 (12/08)
- Minimum Spanning Trees, Prim-JarnÃk algorithm, Cut Property, KT 4.5
- [Non-eval HW] Prove the time complexity of the implementation using min-heaps.
Lecture 5 (14/08)
- Single Source Shortest Path problem, Dijkstra's algorithm, KT 4.4
- [Non-eval HW] Prove the time complexity of the implementation using min-heaps.
Lecture 6 (17/08)
- Huffman Codes, Time Complexity, KT 4.8
Lecture 7 (19/08)
- Huffman Codes, Proof of Correctness, KT 4.8
Lecture 8 (21/08)
- Finding the Closest Pair of Points in the Plane, KT 5.4
Lecture 9 (24/08)
- Maximum Independent Set of Rectangles - A Divide-and-Conquer Algorithm
- Reference: Agarwal, P. K., Van Kreveld, M., & Suri, S. (1998). Label placement by maximum independent set in rectangles. Computational Geometry, 11(3-4), 209-218. Section 3 of the paper. https://doi.org/10.1016/S0925-7721(98)00028-5
Lecture 10 (31/08)
- Weighted Job (Interval) Scheduling, KT 6.1
Lecture 11 (02/09)
- Subset Sums and Knapsacks, KT 6.4
- [non-eval HW] Read about Pseudo-polynomial time.
Lecture 12 (07/09)
- Sequence Alignment, KT 6.6
- [non-eval] Read how this problem is related to the Shortest Path problem in the graph defined at the end of KT 6.6.
Lecture 13 (09/09)
- Sequence Alignment, KT 6.6, 6.7
Lecture 14 (11/09)
- Sequence Alignment, KT 6.7
Lecture 15 (16/09)
- Single Source Shortest Paths in Graphs, KT 6.8, 6.10
Lecture 16 (18/09)
- Network Flows, KT 7.1