Advanced algorithms (2007/2008)

  1. Home
  2. Teaching
  3. Master’s degrees (no longer running)
  4. Masters in Computer Science
  5. Insegnamenti

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
3° Q dal Apr 7, 2008 al Jun 13, 2008.
Web page
http://profs.sci.univr.it/~posenato/courses/algavanzati/
Course news Seminars related to the course

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.

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.

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

Documents

Share