## 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.

## 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.

## Course calendar

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

Period | From | To |
---|---|---|

I semestre | Oct 4, 2010 | Jan 31, 2011 |

II semestre | Mar 1, 2011 | Jun 15, 2011 |

Session | From | To |
---|---|---|

Sessione straordinaria | Feb 1, 2011 | Feb 28, 2011 |

Sessione estiva | Jun 16, 2011 | Jul 29, 2011 |

Sessione autunnale | Sep 1, 2011 | Sep 30, 2011 |

Session | From | To |
---|---|---|

Sessione autunnale | Oct 21, 2010 | Oct 21, 2010 |

Sessione straordinaria | Dec 15, 2010 | Dec 15, 2010 |

Sessione invernale | Mar 24, 2011 | Mar 24, 2011 |

Sessione estiva | Jul 19, 2011 | Jul 19, 2011 |

Period | From | To |
---|---|---|

All Saints | Nov 1, 2010 | Nov 1, 2010 |

National holiday | Dec 8, 2010 | Dec 8, 2010 |

Christmas holidays | Dec 22, 2010 | Jan 6, 2011 |

Easter holidays | Apr 22, 2011 | Apr 26, 2011 |

National holiday | Apr 25, 2011 | Apr 25, 2011 |

Labour Day | May 1, 2011 | May 1, 2011 |

Local holiday | May 21, 2011 | May 21, 2011 |

National holiday | Jun 2, 2011 | Jun 2, 2011 |

Summer holidays | Aug 8, 2011 | Aug 15, 2011 |

## 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.

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

## Academic staff

## 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.

Modules | Credits | TAF | SSD |
---|

Modules | Credits | TAF | SSD |
---|

1° Year

Modules | Credits | TAF | SSD |
---|

2° Year

Modules | Credits | TAF | SSD |
---|

Modules | Credits | TAF | SSD |
---|

#### 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.

### Algorithms (2010/2011)

The teaching is organized as follows:

## Learning outcomes

Module: ALGORITMI

-------

The goal of this course is to introduce some advanced paradigms for algorithms development and analysis in order to determine good approximate solutions for hard optimization problems.

Module: COMPLESSITÀ

-------

In this courses, the relevant notions in complexity theory are introduced. Main themes are the relationship between complexity classes and Np-completeness theory. The scope of the courses is to give formal instruments useful in the analysis of the difficulty of computational problems.

## Program

Module: ALGORITMI

-------

Main concepts recall about computational problems: definition, instances, encoding, precise and approximate models. Optimization computational problem.

Main concepts recall about algorithms: computational resources, input encoding, input size/cost, computational time. Worst and average analysis. Computational time and growth order.

Computational time vs. hardware improvements: main relations. Efficient algorithms and tractable problems.

Divide et impera paradigm

-------------------------

Definition and application to some problems.

Greedy paradigm

---------------

Definition and application to some problems. Matroids and greedy algorithms.

Huffman Codes

Backtracking technique

----------------------

Definition and application to some problems (main examples: Graham Scan and Knuth-Morris-Pratt algorithm).

Branch & Bound technique

------------------------

Definition and application to some problems.

Dynamic programming paradigm

----------------------------

Definition and application to some problems.

Memoization and Dynamic programming.

Probabilistic algorithms

------------------------

Definition and few application examples.

Numerical probabilistic algorithms, Monte Carlo algorithms and Las Vegas algorithms. Examples: Buffon's needle, Pattern Matching and Universal hashing.

Local search tecnique

---------------------

Definition and application to some problems.

Approximations algorithms

-------------------------

Definition and some examples.

Simulated annealing.

Tabù search.

Module: COMPLESSITÀ

-------

This is a condensed version of the program. The detailed program (with useful notes for the students) is available in the pdf file "Diario delle Lezioni"

1)Introduction

Computational models, computational resources, tractable problems and feasible algorithms.

2) Computational models and time complexity classes

Deterministic Turing Machine with 1 and k strings

Class TIME(f(n)).

Relationship between k-MdT e 1-MdT (theorem).

Random Access Machine.

Simulation theorems TM-RAM.

Thesis of sequential calculus.

Linear speed-up theorem and consequences.

The class P.

Examples of problems in P.

Non deterministic Turing machine(NTM).

Class NTIME(f(n)).

Relationship between NTM and TM.

The class NP.

Examples of problems in NP.

Characterization of problem in NP with polynomial verifier.

The class EXP.

4)Space complexity
.

Input-output TM.

Classes SPACE(f(n)) and NSPACE(f(n)).

Compression Theorem

Classes L e NL.

Examples of problems in L and NL.

Relationship between space and time onf I/O TM

5)Relationship between complexity classes

Proper function.

The reachability method.

Theorems: inclusions between time and space classes. Universal TM.

Lemmata for Time Hierarchy Theorem.

Time Hierarchy Theorem. Corollary P ⊂ EXP.

Space Hierarchy Theorem. Corollary L ⊂ PSPACE.

Gap's Theorem.

Savitch's Theorem with Corollary. Corollary PSPACE=NPSPACE.

6)Reduction and completeness

Reduction and logarithmic reduction.

Examples of reduction: HAMILTON PATH ≤log SAT, PATH ≤log CIRCUIT VALUE, CIRCUIT SAT ≤log SAT.

Examples of reduction by generalization.

Property of reduction: reflexivity and transitivity.
C-Completeness for a language.

Closure of a class C with respect to reduction.

L, NL, P, NP, PSPACE and EXP are closed w.r.t ≤log.

Table method. Computational table

CIRCUIT VALUE is P-complete.

Cook's theorem.

Examples of NP-complete problems.

7)Some notions on the complement of non deterministic classes

coC

NP and coNP

## Examination Methods

Module: ALGORITMI

-------

Written test/ open questions

Module: COMPLESSITÀ

-------

Written test with open questions.

## Bibliografia

Author | Title | Publishing house | Year | ISBN | Notes |
---|---|---|---|---|---|

Christos H. Papadimitriou | Computational complexity | Addison Wesley | 1994 | 0201530821 |

## 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

## Graduation

## List of theses and work experience proposals

## Attendance

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.