Advanced algorithms (2008/2009)

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
2° Q dal Jan 26, 2009 al Mar 27, 2009.
Web page
http://profs.sci.univr.it/~posenato/home/courses/algavanzati

Lesson timetable

2° Q
Day Time Type Place Note
Wednesday 11:30 AM - 1:30 PM lesson Lecture Hall I  
Thursday 2:30 PM - 3:30 PM lesson Lecture Hall A  
Friday 2:30 PM - 4:30 PM lesson Lecture Hall D  

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.

Assessment methods and criteria

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