Teaching Group:
Instructor: Dr. Pallavi Jain
Assistant Professor
IIT Jodhpur
Teaching Assistant: Nayanita Saha
M.Tech. CSE
Course objective:
If you have ever
used google maps or any navigation system to find the shortet route, then you have used graph algorithms (Shortest Path)
played Sudoku, then you have used graph algorithms (Graph Coloring)
Many real-world situations can be formulated as graphs, e.g., road networks, computer networks, social networks, web graph, airline scheduling, etc. In this course, you will learn several efficient algorithms for graph-theoretic problems.
Prerequisites:
Maths for Computing/Discrete Mathematics
Algorithms
Class Schedule:
Friday : 6:00 - 7:30 PM
Saturday - 5:00-6:00 PM
Location: LHB 205
Attendance Requirements: as per institute policy.
Office Hours:
If you want to discuss with instructor, then schedule an appointment through email.
Grading Policy:
The following grading policy is tentative. It might change depending on the class size.
Major Exam : 40%
Minor Exams: 20%
Class Participation: 5%
Lecture Scribes: 20% (You need to scribe at least 5 lectures. Best lecture scribes will be uploaded on the website.)
Project: 15% (You will be expected to read a paper and present in the class. The mode of the presentation can be decided by the students, i.e., it can be either slides or board presentation. The project can either be done alone or in a group of 2.)
Lectures:
Lecture 1: Introduction to the course, Basic graph definitions, Algorithm to find a u-v walk of length at least/at most k in the graph.
Lecture 2: Algorithm to find a u-v of length k in the graph, Counting the number of u-v walks of length k in the graph, Counting triangles, Algorithm for integer multiplication.
Lecture 3: Algorithm for matrix multiplication, Algorithm for All Pair Shortest Distance. [Reference]
Lecture 4: Algorithm for All Pair Shortest Path. [Reference]
Lecture 5: Maximum Matching in Bipartitie Graphs: O(nm) algorithm
Lecture 6: Maximum Matching in Bipartitie Graphs: Hopcroft-Karp algorithm [Reference]
Lecture 7: Maximum Weight Matching in Bipartite Graphs
Lecture 8: Edmonds' Blossom Algorithm for Maximum Sized Matching in General Graphs
Lecture 9: Stable Matching [Chapeter 1 in KT]
Lecture 10: Algorithm for Vertex Cover in Bipartite Graphs, NP-hardness of Vertex Cover in General Graphs
Lecture 11: Approximation algorithm for Vertex Cover
Lecture 12: Approximation algorithm for Vertex Cover
Lecture 13: Linear Programming: Tool to design (1) polynomial time exact algorithm for Vertex Cover in Bipartite graph and (2) approximation algorithm for Vertex Cover in general graphs
Lecture 14: Exact Exponential Time Algorithm for Vertex Cover
Lecture 15: Parameterized Algorithm for Vertex Cover, Parameterized approximation algorithm for Vertex Cover
Lecture 16: Network Flows [Chapter 7 in KT, Chapter 10&11 in JE]
Lecture 17: Network Flows [Chapter 7 in KT, Chapter 10&11 in JE]
Lecture 18: Network Flows [Chapter 7 in KT, Chapter 10&11 in JE]
Lecture 19: Network Flows [Chapter 7 in KT, Chapter 10&11 in JE]
Lecture 20: Treewidth [Chapter 10 in KT, Chapter 7 in CFKLMPPS]
Lecture 21: Algorithm for Maximum Weight Independent Set in Trees [Chapter 10 in KT, Chapter 7 in CFKLMPPS]
Lecture 22: Algorithm for Maximum Weight Independent Set in Bounded Treewidth Graphs: 4^{tw}.(n+tw)^{O(1)}and 2^{tw}.(n+tw)^{O(1)}[Chapter 10 in KT, Chapter 7 in CFKLMPPS]
Lecture 23: Project Presentations
Presentation Title: Disjoint Stable Matchings in Linear Time
Presented Students: Ashish Jacob sam, Shubham Singh, Priyal jain, Poonam Kashyap, Himanshi
Lecture 24: Project Presentations
Presentation Title: 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science
Presented Students: Manveer Singh Rathore, Mayank Raj, Manepalli Hari, Vikash Singh
Lecture 25: Project Presentations
Presentation Title: Perfect Matchings in O(n log n) Time in Regular Bipartite Graphs
Presented Students: Kajal Paradkar
Presentation Title: Connecting the Dots (with Minimum Crossings)
Presented Students: Abhinav Kashyap, Aditya Devade, Abhishek Raghav, Abhijeet Verma, Aklovya Gupta
Lecture 26: Project Presentations
Presentation Title: Efficient Implementation of Edmonds' Algorithm for Maximum Matching on Graphs
Presented Students: Abhilekh Talukdar, Sahil Bhatia
Presentation Title: Graph realisation of distance sets Bar Noy et al MFCS 2022.
Presented Students: Harikrishnan,Mudit Singh
Lecture 27: Approximation Algorithm for Treewidth [Chapter 7 in CFKLMPPS]
Lecture 28: Approximation Algorithm for Treewidth-- continued [Chapter 7 in CFKLMPPS]
Lecture 29: Vertex Coloring
Lecture 30: Projects Presentations
Presentation Title: The Complexity of Contracting Bipartite Graphs into Small Cycles ∗
Presented Students: Kanika Aggarwal, Devansh Kaushik , Jayadeep , Sumit Prajapati, Anirudh Shrikant
Lecture 31: Projects Presentations
Presentation Title: Recognising k-Clique Extendible Orderings
Presented Students: Rutvik Jethava, Asmita Rani, Amit Shukla, Alok Shukla, Vishal Dasani
Presentation Title: A linear-time algorithm for a special case of disjoint set union
Presented Students: Ankit
Lecture 32: Projects Presentations
Presentation Title: Google page rank algorithm
Presented Students: Shubham Solanki