Advanced algorithms (2006/2007)

Course partially running

Course code
4S01076
Name of lecturer
Roberto Posenato
Number of ECTS credits allocated
5
Other available courses
Academic sector
INF/01 - INFORMATICS
Language of instruction
Italian
Period
3rd quadrimester dal Apr 2, 2007 al Jun 8, 2007.

Lesson timetable

3rd quadrimester
Day Time Type Place Note
Tuesday 11:30 AM - 1:30 PM lesson Lecture Hall L  
Wednesday 11:30 AM - 1:30 PM lesson Lecture Hall L  
Thursday 11:30 AM - 12:30 PM lesson Lecture Hall L  

Learning outcomes

The goal of this course is to introduce some advanced paradigms for algorithms development and analysis in order to solve optimization problems.

Syllabus

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.

Backtracking technique
----------------------
Definition and application to some problems.

Branch & Bound technique
------------------------
Definition and application to some problems.

Dynamic programming paradigm
----------------------------
Definition and application to some problems.
Memoization and Dynamic programming.

Local search tecnique
---------------------
Definition and application to some problems.

Approximations algorithms
-------------------------
Definition and some application examples.
Simulated annealing.
Tabù search.

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.

Quantum algorithms
------------------
Introduction to qubit, quantum state concepts. Information coding by qubits. Quantum algorithms. One example of quantum algorithm: Fourier Quantum Transform.

Reference books
Author Title Publisher Year ISBN Note
Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani Algorithms (Edizione 1) McGraw-Hill Higher Education 2007 978-0-07-352340-8 consultazione
Alan Bertossi Algoritmi e strutture dati (Edizione 1) UTET 2000 88-7750-611-3 consultazione
G. Brassard, P. Bratley Fundamentals of Algorithms Prentice-Hall 1996 0133350681 consultazione
T. Cormen, C. Leiserson, R. Rivest, C. Stein Introduzione agli Algoritmi e Strutture Dati (Edizione 2) McGraw-Hill 2005 88-386-6251-7 consultazione

Assessment methods and criteria

The final exam consists of a written part followed, if it is sufficient, by an oral part.

Teaching aids

Documents