Combinatorics & Graphs

This two-semester course offers a rigorous study of combinatorics and graph theory for computer science students. It blends theoretical foundations with algorithmic applications, covering topics from advanced counting and extremal problems to spectral methods and random graphs. Emphasis is placed on proof techniques, problem-solving, and connections to modern applications in algorithms, networks, and optimization.

At the end of this course, you will get a grade from 0 to 10 (you need at least 3 to pass) according to the following parameters:

• A:= Max of 1 point for class attendance (1 if you missed no more than 1 class. And o,5 if you missed no more than 2)
• P:= Max of 2 points for participation in class by solving homework on the board.
• T:= Max of 6 points for Test 1 + Test 2
• E:= Max of 4 points for final exam (зачет) on theory

Final grade = A+P+T+E-2

IMPORTANT: You must get at least 1.5 points in the final exam on theory in order to pass the course.

The theoretical exam and tests 1 and 2 are closed-book, that is, you are not allowed to use any material.

The number of points you get for each activity, is either an integer x or x+0.5.

If your final grade (after the final exam) is not an integer (z+0,5), you can solve an extra problem to raise your grade to z+1. Otherwise you get just z.

If you have <= 2 points for A+T, then you have a solve problems in the exam. You need a minimum number of points of the solution of these problems to get your theoretical questions and continue with the exam.

On the other hand, in the retake you have to solve problems independently from the number of points you have for T.

• Béla Bollobás — Modern Graph Theory
• László Lovász — Combinatorial Problems and Exercises
• Douglas West — Introduction to Graph Theory
• Miklós Bóna — A Walk Through Combinatorics
• Noga Alon, Joel Spencer — The Probabilistic Method
• Reinhard Diestel — Graph Theory (free electronic edition)