Lectures and Schedule with Materials

Below you find the schedule for 2017-2018.

Links to the slides and relevant materials will be added or updated during the course.
Week nr Lecture on tuesday by Johan van Rooij Lecture on thurday by Hans Bodlaender
46
November 14th
Introduction.
Slides: PPTX, PDF.
Stable Mariage Problem.
Slides: PPTX, PDF (first part).
Further reading:
  • Kleinberg and Tardos: Chapter 1.
November 16th
Flows and Matchings I: Maximum Flow
Slides: PPTX, PDF.
Further reading:
  • Cormen et al.: Chapter 26
  • Ahuja et al.
  • Schrijver: Chapters 10 and 11.
47
November 21st
Stable Roommates Problem.
Slides: PPTX, PDF (second part).
Further reading:
  • Robert W. Irving, An efficient algorithm for the "Stable Roommates" problem, Journal of Algorithms 6, 577-595, 1985. (ScienceDirect)
Shortest Paths: Algorithms for Standard Variants.
Slides: PPTX, PDF (first part).
Further reading:
  • Cormen et al.: Chapters 24 en 25.
  • Schrijver: Chapters 7 and 8.
November 23th
No course today
48
November 28th
Advanced Shortest Paths Algorithms.
Slides: PPTX, PDF (second part).
Further reading:
  • Cormen et al.: Chapters 24 en 25.
  • Schrijver: Chapters 7 and 8.
Introduction to Exact Exponential-Time Algorithms.
Slides: PPTX, PDF (first part).
Further reading:
  • Fomin and Kratsch: Chapters 1 and 3.
  • Sections 1-3 from: Gerard Woeginger, Exact Algorithms for NP-hard problems. "Combinatorial Optimization - Eureka! You shrink!". LNCS 2570, 185-207, 2003. (Download from TU/e).
November 30th
Teacher: Tom van der Zanden.
Flows and Matchings II: Minimum Cost Flow.
Slides:PPTX, PDF.
Further reading:
  • Ahuja et al.
  • Schrijver: Chapter 12.
Flows and Matchings III: Matching
Slides: PPTX, PDF.
Graph Isomorphism.
Slides: PPTX, PDF.
49
December 5th
Some Techniques for Exact Exponential-Time Algorithms.
Slides: PPTX, PDF (second part)
Further reading:
  • Fomin and Kratsch: Chapters 2, 8, 9
  • Sections 4-6 from: Gerard Woeginger, Exact Algorithms for NP-hard problems. "Combinatorial Optimization - Eureka! You shrink!". LNCS 2570, 185-207, 2003. (Download from TU/e).
Inclusion/Exclusion.
Slides: PPTX, PDF (third part).
Further reading:
  • Fomin and Kratsch: Chapter 4.
  • Cygan et al.: Section 10.1.
December 7th
Fixed Parameter Tractability I.
Slides: T.B.A.
Further reading:
  • Cygan et al.: Sections 2.1, 2.2, 2.5, 3.1, 3.5, 5.2.
50
December 12th
Measure-and-Conquer Analysis for Exact Exponential-Time Algorithms.
Slides: PPTX, PDF (fourth part).
Further reading:
  • Fomin and Kratsch: Chapter 6.
T.B.A.
Slides: T.B.A.
December 14th
Fixed Parameter Tractability II.
Slides: T.B.A.
Further reading:
  • Cygan et al.: Sections 2.1, 2.2, 2.5, 3.1, 3.5, 5.2.
51
December 19th
First Exam.
Topics for the exam are the topics of weeks 46-49 and the Tuesday lecture of week 50.
December 21st
Fixed Parameter Tractability III.
Slides: T.B.A.
Further reading:
  • Cygan et al.: Sections 2.1, 2.2, 2.5, 3.1, 3.5, 5.2.
2
January 9rd
Introduction to Approximation Algorithms
Slides: PPTX, PDF (first part).
Further reading:
  • Cormen et al.: Chapter 35.
  • Kleinberg and Tardos: Chapter 12.
The Landscape of Approximation Algorithms.
Slides: PPTX, PDF (second part).
Further reading:
  • Cormen et al.: Chapter 35.
  • Kleinberg and Tardos: Chapter 12.
  • Ausiello et al.: Chapter 3.(download)
January 11th
Treewidth I.
Slides: T.B.A.
Further reading:
  • Cygan et al.: Sections 7.1, 7.2, 7.3.
3
January 16th
The Landscape of Approximation Algorithms Part 2.
Slides: PPTX, PDF (third part)
Further reading:
  • Cormen et al.: Chapter 35.
  • Kleinberg and Tardos: Chapter 12.
  • Ausiello et al.: Chapter 3.(download)
Approximation Complexity.
Slides: PPTX, PDF (fourth and fifth parts).
Further reading:
January 18nd
Treewidth II.
Slides: T.B.A.
Further reading:
  • Cygan et al.: Sections 7.1, 7.2, 7.3.
Shortest Paths and Treewidth
Slides: T.B.A.
4
January 23rd
Parameterised Complexity.
Slides: T.B.A.
Further reading:
  • Cygan et al., Parameterized Algorithms: Chapter 13.
January 25th
Algorithmic Game Theory.
Slides: T.B.A.
5
Februari 1st
Second Exam.
Topics for the exam are the topics of weeks 51 - 4.