**Course description**

A mandatory course for CS undergraduates in the honours program.

The course takes aim at various aspects of the following topics with the specific selection varying from one course instance to the next.

- Classical and elementary graph theory
- NP-completness
- Linear programming
- Semi-definite programming
- Fractional graph theory
- Approximation algorithms
- Randomised algorithms
- Analysis of Boolean functions
- Discrepancy
- Property testing
- Computational learning algorithms

**Lecture notes**

The course follows these notes.

Please contact me whenever you find mistakes, oversights, typos etc.

**Logistics**

The course has 13 lecture meetings and 13 practical sessions; each conducted on a weekly basis throughout the semester.

**Final grade composition:**

- 50% Assignments
- 50% final exam.

In order to pass the course one needs to

- Score at ≥ 60 on the final exam
- After passing the final exam, have a final grade of at least 60.

Bonus points can be earned for

- Giving a lecture presentation in a departmental seminar on a topic related to the course.
- Make progress on a challenge/research problem.
- Significant programming projects related to the course.
- Submitting assignments in English.
- Submitting assignments using LaTex.

Those of you who are in pursuit of the programming bonus, the following notes might be of use to you.

We do not cover these notes in class.

**Lecture Slides**

- Notation| Slides
- Matchings in bipartite graphs | Slides
- Tutte’s Theorem | Slides
- Whitney’s theorem | Slides
- Finding cut-vertices using DFS | Slides

- Menger’s theorem | Slides
- Dirac’s Theorenm | Slides
- Brooks’ theorem | Slides
- NP-Completness | Slides
- Classical NP-complete languages | Slides
- Linear Programming: early definitions | Slides
- LPs in equational form | Slides
- The Farkas Lemma | Slides
- Duality | Slides
- Complementary slackness | Slides
- Primal-dual method via shortest paths | Slides
- The k-centre problem | Slides
- Metric TSP | Slides
- Minimum set-cover | Slides
- Minimum set cover: LP analysis of the greedy algorithm | Slides
- Minimum set cover: Deterministic rounding of the primal LP | Slides
- Minimum set cover: Randomized rounding of the primal LP | Slides
- Maximum cuts in graphs | Slides
- Minimum cuts in graphs: Karger’s algorithm | Slides
- Minimum cuts in graphs: The Karger-Stein algorithm | Slides

**Assignments **

Assignment 1 | Link | Deadline: March 30, 2020, by 18:00

Assignment 2 | Link | Deadline: 24.04.2020, by 18:00 (after extension)

Assignment 3 | Link | Deadline: 24.04.2020 by 18:00 (after extension)

Assignment 4 | Link | Deadline: 10.05.2020 by 18:00 (after extension)

Assignment 5 | Link | Deadline: 29.05.2020 by 18:00 (after extension)

Assignment 6 | Link | Deadline: 12.06.2020 by 18:00