## 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 18:00 in Takustrasse 9, SR 6 and Thursdays from 10:30 to 12:00 in Arnimallee 6, SR 31.

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

The second exam will be held on April 2nd, from 1 pm to 4 pm.

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.

Quiz | Homework | Due date | Comments |
---|---|---|---|

Week 0 | Sheet 0 | Never | To be discussed on 16/10 |

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