Optimisation

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

  1. Notation| Slides
  2. Matchings in bipartite graphs | Slides
  3. Tutte’s Theorem | Slides
  4. Whitney’s theorem | Slides
    1. Finding cut-vertices using DFS | Slides
  5. Menger’s theorem | Slides
  6. Dirac’s Theorenm | Slides
  7. Brooks’ theorem | Slides
  8. NP-Completness | Slides
  9. Classical NP-complete languages | Slides
  10. Linear Programming: early definitions | Slides
  11. LPs in equational form | Slides
  12. The Farkas Lemma | Slides
  13. Duality | Slides
  14. Complementary slackness | Slides
  15. Primal-dual method via shortest paths | Slides
  16. The k-centre problem | Slides
  17. Metric TSP | Slides
  18. Minimum set-cover | Slides
  19. Minimum set cover: LP analysis of the greedy algorithm | Slides
  20. Minimum set cover: Deterministic rounding of the primal LP | Slides
  21. Minimum set cover: Randomized rounding of the primal LP | Slides
  22. Maximum cuts in graphs | Slides
  23. Minimum cuts in graphs: Karger’s algorithm | Slides
  24. 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