Advanced algorithms (2008/2009)

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.

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