[2024-11-03] An updated version of the lecture notes, with the new exercises (42—45) discussed during the past week, is available in the materials section.
[2024-10-14] An updated version of the lecture notes, with changes to the solution of Exercise 36 as discussed in today's lesson, is available in the materials section.
[2024-10-11] The dates of the winter session are out, see the exam section for details.
Mauro Brunato < mauro.brunato@unitn.it>
Please email me if you want to set up a meeting.
In order to receive urgent updates (e.g., about moved or cancelled lectures), please subscribe to the course's Moodle page.
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 | Thursday, January 9th, 2025 09:00a,—12:00pm | B107 (conference room in Povo2) |
Second call | Monday, February 17th, 2025 09:00a,—12:00pm | B107 (conference room in Povo2) |