Course Details
Listed below are the administrative details regarding the course.
Schedule
There will be two lectures every week, as detailed below.
Lectures: Tuesdays from 14:30 to 16:00 in Takustrasse 9, SR 46 and Wednesdays from 12:30 to 14:00 in Arnimallee 6, SR 7/8.
You are also encouraged to attend one of the following exercise classes.
(We won't stop you from attending both if you really want to.)
Exercises: Tuesdays from 16:15 to 17:45 in Takustrasse 9, SR 6 and Thursdays from 10:30 to 12:00 in Arnimallee 6, SR 32.
Instructors
Tibor Szabó
Arnimallee 3, Room 211a
Anurag Bishnoi
Arnimallee 3, Room 206
Office hours are by appointment, so please e-mail as needed.
Exams and Requirements
The final grade for this course will be from a written exam. The first exam will be held on Wednesday, February 20th, from 1 pm to 4 pm, at T9/Gr. Hörsaal (Takustr. 9) (results)
The second exam will be held on April 2nd, from 1 pm to 4 pm, at T9/Gr. Hörsaal (Takustr. 9) (results)
The full set of requirements and formalities for the course can be found here.
Credits
Master's students at the Freie Universität Berlin may take this course either as
"Diskrete Mathematik II" or as an Ergänzungsmodul.
Phase I students from the Berlin Mathematical School may take this course as the basic course "Discrete Optimization" in teaching area 4.
Topics
We shall explore the use of algorithms in combinatorics. The main topics will be:
- Efficient discrete algorithms
- Sorting algorithms
- Shortest routes in graphs
- Maximum and stable matchings
- Brief introduction to complexity classes
- Algorithmic proofs of combinatorial theorems
- Network flows, connectivity and applications
- Linear programming and duality
- Integer programming and approximation
- Randomised algorithms
- Matchings in general graphs
- Algorithmic Local Lemma
- Derandomisation
References
The following texts are recommended for this course.
- D. Hefetz, M. Krivelevich, M. Stojaković and T. Szabó, Positional Games
- L. Lovász, J. Pelikán and K. Vesztergombi, Discrete Mathematics
- J. Matoušek and Bernd Gärtner, Understanding and Using Linear Programming
- D. West, Introduction to Graph Theory
The interested reader might also enjoy the following.
- V. Chvátal, Linear Programming
- A. Schrijver, Theory of Linear and Integer Programming
- A. Schrijver, Combinatorial Optimization
Prerequisites
This course is a second course in the Discrete Mathematics module, and we assume our students are familiar with the basic concepts of graph theory and combinatorics covered in the Discrete Mathematics I course (see here for the relevant material).
We will also make use of undergraduate linear algebra, calculus and probability.
Exercises
There will be a homework assignment you should solve in pairs.
Submit your solutions by the end of the Tuesday lecture, either in class itself, or to the tutor box of Anurag Bishnoi (solutions via email are also accepted).
| Quiz | Homework | Due date | Comments |
|---|---|---|---|
| Week 0 | Sheet 0 | Never | To be discussed on 16/10 |
| Week 1 | Sheet 1 | 23/10/2018 | [23/10: Exercise 5 corrected] |
| Week 2 | Sheet 2 | 30/10/2018 | |
| Week 3 | Sheet 3 | 6/11/2016 | |
| Sheet 4 | 13/11/2016 | ||
| Sheet 5 | 20/11/2016 | ||
| Sheet 6 | 27/11/2016 | ||
| Sheet 7 | 5/12/2018 | ||
| Sheet 8 | 11/12/2018 | ||
| Sheet 9 | 18/12/2018 | ||
| Practice Exam | 22/01/2019 | Solutions | |
| Sheet 10 | 15/01/2019 | ||
| Sheet 11 | 29/01/2019 | ||
| Sheet 12 | 05/02/2019 | ||
| Sheet 13 | 12/02/2019 | ||
| Sheet 14 | 26/03/2019 |
Course Progress
Topics
As we make our way through the semester, we will provide below a brief review of the topics covered each week.
| Lecture | Topics | References |
|---|---|---|
| 1 | Sorting algorithms: (Binary) insertion sort, Mergesort; Analysis: running time, matching lower bound | lecture notes |
| 2 | Spanning trees: Depth-first and breadth-first search, Kruskal's algorithm for minimum-weight spanning trees | LPV 9.1 West 2.3 lecture notes |
| 3 | Shortest paths: Dijkstra's algorithm, TSP; Complexity and P |
West 2.3 lecture notes |
| 4 | Complexity classes: NP, co-NP, NP-completeness; 2-approximation to TSP |
LPV 15.1 LPV 9.2 |
| 5 | Perfect matchings: Hall's theorem, Tutte's theorem | West 3.1, 3.3 LPV 10.3 |
| 6 | Perfect matchings: proof of Tutte's theorem, Maximum matchings: Berge's theorem, certificates for NP and co-NP, polynomial time algorithms | West 3.1-2 LPV 10.4 lecture notes |
| 7 | Weighted matchings and the Hungarian algorithm | West 3.2 lecture notes |
| 8 | Hungarian algorithm proof, Vertex connectivity: definitions, examples | West 4.1 |
| 9 | Chvatal--Erdős theorem, Edge connectivity | West 4.1 |
| 10 | Whitney's theorem, Menger's theorem (local/global, vertex/edge) Network flows: formulation of problem |
West 4.2 West 4.3 |
| 11 | Network flows: weak duality, Ford-Fulkerson Theorem, Ford-Fulkerson Algorithm and the Integrality Theorem |
West 4.3 |
| 12 | Flow applications: local, vertex Menger's Theorem, Baranyai's Theorem on perfect matching decompositions |
West 4.3 lecture notes |
| 13 | Vertex coloring of graphs: complexity, lower bounds, Hajos and Hadwinger conjecture, Dirac's theorem | West 5.1, 5.2 |
| 14 | Vertex coloring: upper bounds, Brook's theorem, List colouring: introduction | West 5.1 |
| 15 | List colouring of graphs, 5-choosability of planar graphs | West 8.4 |
| 16 | Edge colorings and Vizing's theorem | West 7.1 |
| 17 | Edge-choosability: conjectures (list-colouring, Dinitz), Galvin's theorem for bipartite graphs | West 8.4 lecture notes |
| 18 | Stable matchings, Gale-Shapley proposal algorithm | West 3.2 West 5.1 |
| 19 | Linear programming: network flows, history, 2D examples, standard form, dietary application |
MG 1.1-4 MG 2.1-2 |
| 20 | Linear programming applications: absolute values, strict inequalities, hidden variabels |
MG 2.3-7 |
| 21 | Integer programming, Solving LPs | MG 3.1,3.2,3.4 MG 4.1 |
| 22 | Solving LP's, Simplex Algorithm: tableaux, pivoting | MG 5.1-5 |
| 23 | Simplex algorithm: outline of steps, pivot rules,proof that Bland's rule avoids cycling | MG 5.6-8 |
| 24 | Duality: formulation of dual, weak duality, Duality Theorem | MG 6.1, 6.3 |
| 25 | Applications of Duality, Totally Unimodular Matrices and integer solutions to LP's | MG 8.2 |
| 26 | Zero-sum two-player games: examples, mixed strategies, Nash equilibria, worst-case optimal strategies, the Minmax theorem | MG 8.1 |
| 27 | Transversals of d-intervals: Helly's Theorem, definitions, proof of 2d2 bound | MG 8.6 |
| 28 | Randomised algorithms: Las Vegas vs Monte Carlo, one-sided errors; matrix multiplication verification | |
| 29 | Polynomial identity testing: oracle access, Schwartz-Zippel lemma, perfect matchings in bipartite graphs | |
| 30 | Two-colourability: hypergraph formulation, randomised algorithm; Positional Games: Bridge-It | Notes |
| 31 | derandomised two-colouring, extremal function for games, Erdős-Selfridge criterion | HKSS Ch 1 and 2 |