Instructors: Sanjukta Roy, Sourav Chakraborty
Lecture timing: Monday, 5th January 16:00 - 18:00
Tuesday and Wednesday 11:10 - 12:50 (starting from 7th January)
Location: room# 705
Evaluation: Your grade will be based on your performance in quizzes (20%), Midterm or class presentation (30%) , and final exam (50%).
Basic understanding of algorithms is required.
Practice problem sets for basics of Algorithms
Following are some basic books for algorithms and graph theory:
Graph Theory by Reinhard Diestel
Introduction to Graph Theory by Douglas B. West
Algorithm Design by John Kleinberg and Éva Tardos
Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein
Parameterized Algorithms
Useful lecture notes: Saket Saurabh's Advance Graph Algorithm Course (2014)
Jan 5: Welcome
Jan 7: Quiz 1 . Topic: Basics of Algorithms)
Feb 11: Quiz 2 . Topic: Tree decompositions: how to find them and algorithms on tree decompositions
Tree decompositions: how to find them and algorithms on tree decompositions
Algebraic techniques to solve graph problems
Counting problems on graphs
Date
Topics Covered
References
05.01.2025
Lecture 1: Introduction to the course, some basics of Algorithms, NP hardness
Chapter 8 of Pre-requisit Reference 3
07.01.2025
Quiz 1: on Basics of Algorithms
13.01.2025
Lecture 2: Algorithms for finding Maximum Independent Set on Trees and its properties
Chapter 7.1 of Reference 1
Lecture 1 of Reference 2
14.01.2025
Lecture 3: t-decomposable graphs and Balanced Separators
Chapter 7.6 of Reference 1
Lecture 2 of Reference 2
20.01.2025
Lecture 4: Weighted Balanced Separators and definition of tree decomposition
Chapter 7.6 of Reference 1
Lecture 3 of Reference 2
21.01.2025
Lecture 5: Existence of tree decomposition using W-balance separators via constructive arguments
Chapter 7.6 of Reference 1
Lecture 4 of Reference 2
27.01.2025
Lecture 6: Menger's Theorem
Pre-requisit Reference 1 & 2
28.01.2025
Lecture 7: Finding approximately balanced separators, Finding Tree Decomposition, Nice tree decompositions
Lecture 5 of Reference 2
Chapter 7.6 and 7.2 of Reference 1
03.02.2025
Lecture 8: Designing algorithms using tree decompositions
Chapter 7 of Reference 1