Advanced algorithms (2007/2008)

Course partially running

Course code
Name of lecturer
Roberto Posenato
Number of ECTS credits allocated
Other available courses
Academic sector
Language of instruction
3° Q dal Apr 7, 2008 al Jun 13, 2008.
Web page

Lesson timetable

Learning outcomes

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


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.

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
Alan Bertossi Algoritmi e strutture dati (Edizione 1) UTET 2000 88-7750-611-3
G. Brassard, P. Bratley Fundamentals of Algorithms Prentice-Hall 1996 0133350681
R. C. T. Lee, S. S. Tseng, R. C. Chang, Y. T. Tsai Introduction to the Design and Analysis of Algorithms (Edizione 1) McGraw-Hill Education 2005 007-124346-1
T. Cormen, C. Leiserson, R. Rivest, C. Stein Introduzione agli Algoritmi e Strutture Dati (Edizione 2) McGraw-Hill 2005 88-386-6251-7

Assessment methods and criteria

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

Teaching aids