Studying at the University of Verona

Here you can find information on the organisational aspects of the Programme, lecture timetables, learning activities and useful contact details for your time at the University, from enrolment to graduation.

A.A. 2012/2013

Academic calendar

The academic calendar shows the deadlines and scheduled events that are relevant to students, teaching and technical-administrative staff of the University. Public holidays and University closures are also indicated. The academic year normally begins on 1 October each year and ends on 30 September of the following year.

Academic calendar

Course calendar

The Academic Calendar sets out the degree programme lecture and exam timetables, as well as the relevant university closure dates..

Definition of lesson periods
Period From To
I semestre Oct 1, 2012 Jan 31, 2013
II semestre Mar 4, 2013 Jun 14, 2013
Exam sessions
Session From To
Sessione straordinaria Feb 4, 2013 Feb 28, 2013
Sessione estiva Jun 17, 2013 Jul 31, 2013
Sessione autunnale Sep 2, 2013 Sep 30, 2013
Degree sessions
Session From To
Sessione autunnale Oct 18, 2012 Oct 18, 2012
Sessione straordinaria Dec 12, 2012 Dec 12, 2012
Sessione invernale Mar 21, 2013 Mar 21, 2013
Sessione estiva Jul 16, 2013 Jul 16, 2013
Period From To
Festa di Ognissanti Nov 1, 2012 Nov 1, 2012
Festa dell'Immacolata Concezione Dec 8, 2012 Dec 8, 2012
Vacanze di Natale Dec 21, 2012 Jan 6, 2013
Vacanze di Pasqua Mar 29, 2013 Apr 2, 2013
Festa della Liberazione Apr 25, 2013 Apr 25, 2013
Festa del Lavoro May 1, 2013 May 1, 2013
Festa del Santo Patrono di Verona - San Zeno May 21, 2013 May 21, 2013
Festa della Repubblica Jun 2, 2013 Jun 2, 2013
Vacanze estive Aug 9, 2013 Aug 16, 2013

Exam calendar

Exam dates and rounds are managed by the relevant Science and Engineering Teaching and Student Services Unit.
To view all the exam sessions available, please use the Exam dashboard on ESSE3.
If you forgot your login details or have problems logging in, please contact the relevant IT HelpDesk, or check the login details recovery web page.

Exam calendar

Should you have any doubts or questions, please check the Enrolment FAQs

Academic staff


Belussi Alberto +39 045 802 7980

Bombieri Nicola +39 045 802 7094

Bonacina Maria Paola +39 045 802 7046

Carra Damiano +39 045 802 7059

Castellani Umberto +39 045 802 7988

Combi Carlo 045 802 7985

Cristani Matteo 045 802 7983

Cristani Marco +39 045 802 7841

Cubico Serena 045 802 8132

Di Pierro Alessandra +39 045 802 7971

Farinelli Alessandro +39 045 802 7842

Favretto Giuseppe +39 045 802 8749 - 8748

Fiorini Paolo 045 802 7963

Fracastoro Gerolamo + 39 0458122786

Fummi Franco 045 802 7994

Giachetti Andrea +39 045 8027998

Giacobazzi Roberto +39 045 802 7995

Manca Vincenzo 045 802 7981

Masini Andrea 045 802 7922

Mastroeni Isabella +39 045 802 7089

Menegaz Gloria +39 045 802 7024

Merro Massimo 045 802 7992

Monti Francesca 045 802 7910

Muradore Riccardo +39 045 802 7835

Oliboni Barbara +39 045 802 7077

Posenato Roberto +39 045 802 7967

Pravadelli Graziano +39 045 802 7081

Quaglia Davide +39 045 802 7811

Rizzi Romeo +39 045 8027088

Segala Roberto 045 802 7997

Vigano' Luca

Villa Tiziano +39 045 802 7034

Study Plan

The Study Plan includes all modules, teaching and learning activities that each student will need to undertake during their time at the University. Please select your Study Plan based on your enrolment year.

Altre attivita' formative

1° Year


2° Year

Altre attivita' formative
Modules Credits TAF SSD
Between the years: 1°- 2°

Legend | Type of training activity (TTA)

TAF (Type of Educational Activity) All courses and activities are classified into different types of educational activities, indicated by a letter.

SPlacements in companies, public or private institutions and professional associations

Teaching code




Scientific Disciplinary Sector (SSD)





I semestre dal Oct 1, 2012 al Jan 31, 2013.

To show the organization of the course that includes this module, follow this link:  Course organization

Learning outcomes

The goal of this module is to introduce students to computational complexity theory in general, to the NP-completeness theory in detail and to computational analysis of problems with respect to their approximability.

Recommended Prerequisite
To attend the course lessons in a productive way, a student should be confident with the following concepts:
1. Basic data structures as list, stack, queue, tree, heap.
2. Graph representation and fundamental graph algorithms:
2.1 Graph visit: BFS, DFS.
2.2 Topological ordering. Connected component.
2.3 Minimal spanning tree. Kruskal and Prim algorithm.
2.4 Single-source shortest path: Dijkstra algorithm and Bellman-Ford one.
2.5 All-pairs shortest path: Floyd-Warshall algorithm and Johnson one.
2.6 Max flow: Ford-Fulkerson algorithm.
A recommended book to revise the above concepts is ``Introduction to Algorithms" di T. H. Cormen, C. E. Leiserson, R. L. Rivest e C. Stein (3 ed.).


Computational model concept, computational resource, efficient algorithm and tractable problem.

Computational models
Turing Machine (MdT): definition, behavior, configuration, production and computation concepts. MdT examples. MdT and languages: the difference between accepting and deciding a language. MdT extension: multi-tape MdT (k-MdT)

Time Complexity
Time computational resource. Computational class TIME(). Theorem about polynomial relation between k-MdT computations and MdT ones (sketch of proof).
Introduction to Random Access Machine (RAM) computational model: configuration, program and computation concepts. RAM: computation time by uniform cost criterion and by logarithmic cost one. Example of a RAM program that determines the product of two integers.
Theorem about simulation cost of a MdT by a RAM.
Theorem about simulation cost of a RAM program by a MdT.
Sequential Computation Thesis and its consequences.
Linear Speed-up Theorem and its consequences.

P Computational Class.

Extension of MdT: non-deterministic MdT (NMdT).
Time resource for k-NMdT. NTIME() computational class.
Example of non-deterministic algorithm computable by a NMdT: algorithm for Satisfiability (SAT).

Relation between MdT and NMdT.

NP Computational Class.
Relation between P and NP. Example of a problem into NP: Travel-salesman Problem (TSP).
An alternative characterization of NP: polynomial verifiers.

EXP Computation Class.

Space Complexity.
Space complexity concept. MdT with I/O. Computational Classes: SPACE() and NSPACE().
Compression Theorem.
Computational Classes: L and NL.
Example of problems: PALINDROME ∈ L and PATH ∈ NL.

Theorems about relations between space and time for a MdT with I/O.
Relations betwee complexity classes.
Proper function concept and example of proper functions.
Borodin Gap Theorem.

Reachability method. Theorem about space-time classes: NTIME(f(n)) ⊆ SPACE(f(n)), NSPACE(f(n)) ⊆ TIME(k(log n+f(n))).

Universal MdT.
The Hf set.
Lemma 1 and 2 for time hierarchy theorem.
Time Hierarchy Theorem: strict and no-strict versions.
P ⊂ EXP Corollary.

Space Hierarchy Theorem. L ⊂ PSPACE Corollary.
Savitch Theorem. SPACE(f(n))=SPACE(f(n)^2) corollary. PSPACE=NPSPACE Corollary.

Reductions and completeness.
Reduction concept and logarithmic space reduction. HAMILTON PATH ≤log SAT, PATH ≤log CIRCUIT VALUE, CIRCUIT SAT ≤log SAT.
Language completeness concept.
Closure concept with respect to reduction.
Class reduction of L, NL, P, NP, PSPACE and EXP.
Computation Table concept.
Theorem about P-completeness of CIRCUIT VALUE problem.
Cook Theorem: an alternative proof.
Gadget concept and completeness proof of: INDEPENDENT SET, CLIQUE, VERTEX COVER and others.

Approximation algorithms and approximate complexity classes.


Reference texts
Author Title Publishing house Year ISBN Notes
Christos H. Papadimitriou Computational complexity Addison Wesley 1994 0201530821
S. Arora, B. Barak Computational Complexity. A modern approach (Edizione 1) Cambridge University Press 2009 9780521424264

Examination Methods

The examination consists of a written test. The grade in this module is worth 1/3 of the grade in the Algorithms examination.

Type D and Type F activities

Modules not yet included

Career prospects

Module/Programme news

News for students

There you will find information, resources and services useful during your time at the University (Student’s exam record, your study plan on ESSE3, Distance Learning courses, university email account, office forms, administrative procedures, etc.). You can log into MyUnivr with your GIA login details.

Gestione carriere


List of theses and work experience proposals

theses proposals Research area
Analisi ed identificazione automatica del tono/volume della voce AI, Robotics & Automatic Control - AI, Robotics & Automatic Control
Analisi e percezione dei segnali biometrici per l'interazione con robot AI, Robotics & Automatic Control - AI, Robotics & Automatic Control
Integrazione del simulatore del robot Nao con Oculus Rift AI, Robotics & Automatic Control - AI, Robotics & Automatic Control
BS or MS theses in automated reasoning Computing Methodologies - ARTIFICIAL INTELLIGENCE
Sviluppo sistemi di scansione 3D Computing Methodologies - COMPUTER GRAPHICS
Sviluppo sistemi di scansione 3D Computing Methodologies - IMAGE PROCESSING AND COMPUTER VISION
Dati geografici Information Systems - INFORMATION SYSTEMS APPLICATIONS
Analisi ed identificazione automatica del tono/volume della voce Robotics - Robotics
Analisi e percezione dei segnali biometrici per l'interazione con robot Robotics - Robotics
Integrazione del simulatore del robot Nao con Oculus Rift Robotics - Robotics
BS or MS theses in automated reasoning Theory of computation - Logic
BS or MS theses in automated reasoning Theory of computation - Semantics and reasoning
Proposte di tesi/collaborazione/stage in Intelligenza Artificiale Applicata Various topics
Proposte di Tesi/Stage/Progetto nell'ambito delle basi di dati/sistemi informativi Various topics


As stated in point 25 of the Teaching Regulations for the A.Y. 2021/2022, attendance at the course of study is not mandatory.
Please refer to the Crisis Unit's latest updates for the mode of teaching.

Further services

I servizi e le attività di orientamento sono pensati per fornire alle future matricole gli strumenti e le informazioni che consentano loro di compiere una scelta consapevole del corso di studi universitario.