Algorithmic Combinatorics

Winter 2020-21

FU Berlin, Mathematics and Informatics

Many thanks to Toptal for this animation.

Course Details

Listed below are the administrative details regarding the course.

Registration

If you are interested in taking this course, please make sure you register in the Whiteboard system. (Instructions for registration, and for non-FU students.) It is important to do this as soon as possible, so that we can contact you if needed.

Schedule

In keeping with the university's coronavirus guidelines and maintaining a responsible level of social distancing, all course activities will take place online through the Cisco Webex Meetings platform. Please be sure to have installed and familiarised yourself with any necessary software in advance. Information for setting up an account for FU students can be found in the ZEDAT portal. Once installed, you can test your configuration here.

Starting from the 2nd of November, lectures will take place on Tuesdays from 12:15 to 13:45 and on Wendesdays from 14:15 to 15:45. The exercise classes will take place on Thursdays from 08:30 to 10:00. The links to the Webex meetings will be available in the Whiteboard system.

Instructors

Michael Anastos Tibor Szabó Patrick Morris
Arnimallee 3, Room 202 Arnimallee 3, Room 211a Arnimallee 3, Room 207
manastos at mi dot fu-berlin dot de szabo at math dot fu-berlin dot de pm0041 at math dot fu-berlin dot de

Exams and Requirements

The final grade for this course will be from a written exam.

The full set of requirements and formalities for the course can be found here.

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). A previous version of this course can be found here.

We will also make use of undergraduate linear algebra, calculus and probability.

Return to top
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
2 Spanning trees: Depth-first and breadth-first search, Kruskal's algorithm for minimum-weight spanning trees LPV 9.1
West 2.3
3 Shortest paths: Dijkstra's algorithm;
TSP, 2-approximation to TSP		 West 2.3
4 Complexity classes:P, NP, co-NP, NP-Hard, NP-completeness LPV 15.1
LPV 9.2
5 Perfect matchings: Hall's theorem, Tutte's theorem and their Min-Max versions West 3.1, 3.3
LPV 10.3
6 Berge's theorem, certificates for NP and co-NP, polynomial time algorithms West 3.1-2
LPV 10.4
7 Weighted matchings and the Hungarian algorithm West 3.2
8 Vertex connectivity: definitions, examples, Chvatal--Erdős theorem, Edge connecivity, Whitney's theorem West 4.1
9 Whitney's theorem, Menger's theorem (local/global, vertex/edge)
Network flows: formulation of problem		 West 4.2
West 4.3
10 Network flows: weak duality, Ford-Fulkerson Algorithm and the Integrality Theorem, Max-Flow Min-Cut Theorem West 4.3
11 Flow applications: local, vertex Menger's Theorem,
Baranyai's Theorem on perfect matching decompositions		 West 4.3
12 Vertex coloring of graphs: complexity, lower and upper bounds, Brook's Theoremupper Hajos and Hadwinger conjecture, Dirac's theorems West 5.1
13 Vertex coloring: Hajos and Hadwinger conjuctures, Dirac's Theorems , List colouring: introduction West 5.2
14 List colouring of graphs, 5-choosability of planar graphs West 8.4