[2025-03-22] The (still unofficial) dates of the summer session are out, see the exam section for details.
[2025-02-23] The text of the written exam from the second call of the first session is available in the materials section together with a proposed solution trace.
[2025-01-17] The text of the written exam from the first call of the first session is available in the materials section together with a proposed solution trace.
Four hours per week. The 2024-25 edition is over.
The course aims at providing the theoretical bases for understanding two fundamental properties of computational problems.
Students should have a basic understanding of the following topics:
For the actual program, see below.
At the end of the course, students will be able to:
The course will mainly consist of lectures and discussions with students.
As soon as specific milestones are reached, exercises and papers will be proposed for self-assessment and further discussion.
Since the beginning of the course, the previous year's material will be made available on this website (in the materials section below):
The following books may be useful, but none is mandatory. References to online material will be provided in the course program section.
Computational Complexity: A Modern Approach. Cambridge University Press, 2009. ISBN 9780521424264 [Draft of the book]
and .Computational complexity. Addison Wesley (Pearson College Div.), 1994. ISBN 9780020153085
.Introduction to Automata Theory, Languages and Computation. Pearson new International Edition, 2013. ISBN: 9781292039053
, , and .The exam is written, pen and paper, in English, and is composed by three open-question exercises requiring to expose theoretical topics and analyze problems and algorithms. One of the exercises is about computability, the other two are mainly about the computational complexity topic. The three exercises have an equal weight in determining the final mark.
Answers are evaluated on the basis of the following criteria:
In the winter and summer exam sessions of 2024, 61 registrants out of 66 have passed the exam (38 out of 42 in the first exam in January).
This section contains course material and exercises.
(See the lecture notes for details)
Exercises from previous exams that are compatible with this year's program appear in the lecture notes. Here are links to the exam sheets as they were proposed during the academic years 2018-2019, 2019-2020 and 2023-2024 (the three missing years were taught by another instructor):
Date/time | Room | |
---|---|---|
First call | Wednesday, June 11th, 2025 09:00—12:00 | A102 |
Second call | Monday, July 21st, 2025 09:00—12:00 | A102 |
Third call | Wednesday, September 3rd, 2025 14:00—17:00 | A102 |