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

## 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 enrollment year.**

1° Year

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

2° Year activated in the A.Y. 2011/2012

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

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

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

## Bibliography

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

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

## Examination Methods

Module: ALGORITMI

-------

Written test/ open questions

Module: COMPLESSITÀ

-------

Written test with open questions.

**Students with disabilities or specific learning disorders (SLD), who intend to request the adaptation of the exam, must follow the instructions given HERE**

## 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: only in this way will you be able to receive notification of all the notices from your teachers and your secretariat via email and also via the Univr app.

## Graduation

#### Deadlines and administrative fulfilments

For deadlines, administrative fulfilments and **notices on graduation sessions**, please refer to the Graduation Sessions - Science and Engineering service.

#### Need to activate a thesis internship

For** thesis-related internships**, it is not always necessary to activate an internship through the Internship Office. For further information, please consult the dedicated document, which can be found in the 'Documents' section of the Internships and work orientation - Science e Engineering service.

#### Final examination regulations

## List of thesis proposals

## Attendance modes and venues

As stated in the Teaching Regulations, attendance at the course of study is not mandatory.

Part-time enrolment is permitted. Find out more on the Part-time enrolment possibilities page.

The course's teaching activities take place in the Science and Engineering area, which consists of the buildings of Ca‘ Vignal 1, Ca’ Vignal 2, Ca' Vignal 3 and Piramide, located in the Borgo Roma campus.

Lectures are held in the classrooms of Ca‘ Vignal 1, Ca’ Vignal 2 and Ca' Vignal 3, while practical exercises take place in the teaching laboratories dedicated to the various activities.