## 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.

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

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