Algorithmic Combinatorics

Winter 2018-19

FU Berlin, Mathematics and Informatics



Many thanks to Toptal for this animation.

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)

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.

Return to top

Topics

We shall explore the use of algorithms in combinatorics. The main topics will be:

References

The following texts are recommended for this course.

The interested reader might also enjoy the following.

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.

Return to top

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
Return to top

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