Course Details for A.Y. 2013/2014
Name:
Algoritmi e Strutture Dati II / Algorithms and Data Structures II
Basic information
Credits:
: Laurea Magistrale in Informatica 6 CFU (b)
Degree(s):
Laurea Magistrale in Informatica 1° anno curriculum SDRC Obbligatorio
Laurea Magistrale in Informatica 1° anno curriculum ASSC Obbligatorio
Laurea Magistrale in Informatica 1° anno curriculum Generale Obbligatorio
Language:
Italian
![[info]](img/info16.png)
Course Objectives
Knowledge of advanced algorithmic techniques; ability to individuate, formalize and solve optimization problems; concept of approximation; ability to classify problems according to their degree of approximability; ability to collaborate for the realization of applicative projects in group.
Course Content
- Review of computational complexity and intractability. Optimization problems. Approximation algorithms.
- Algorithmic techniques: greedy.
- Algorithmic techniques: local search and dynamic programming.
- Linear programming techniques: rounding and primal-dual methods
- Polynomial Time Approximation Schemes (PTAS) and Fully Polynomial Time Approximation Schemes (FPTAS).
- Negative approximation results and gap technique. Complexity classes for optimization problems and their inclusions
Learning Outcomes (Dublin Descriptors)
On successful completion of this course, the student should
-
Acquire knowledge of advanced algorithmic techniques for NP-Hard optimization problems. In particular, the student will
have mastery command of main algorithmic (approximation) techniques like greedy, local search, dynamic programming, linear programming: rounding and primal-dual methods, Polynomial Time Approximation Schemes (PTAS) and Fully Polynomial Time Approximation Schemes (FPTAS). Moreover the student will acquire knowledge on negative approximation results and gap technique, and therefore on the complexity classes for optimization problems.
-
Acquire the ability of abstracting models and formal algorithmic problems from real computational problems, understanding the degree of approximability and designing efficient algorithmic solutions.
-
Acquire autonomy in individuating, formalizing and understanding the degree of approximability of real computational problems and identify independently their most efficient solutions.
-
Being able to understand complex algorithms solutions and to formal proving performances of their algorithmic solutions for complex computational problems.
-
The course aims to develop in graduate students competencies and abilities necessary in their future studies and/or works, especially with respect to doctoral studies and in general to any research activity on algorithmic topics.
Prerequisites and Learning Activities
KNOWLEDGE: fundamentals of programming, discrete mathematics, algorithms and data structures, computer architectures, reading and understanding of the English language
SKILLS: ability to integrate classroom and homework study, ability to interact with the teacher during the class for originating discussion.
Assessment Methods and Criteria
Final written examination.
Textbooks
- Vijay V. Vazirani, Approximation Algorithms , Springer. 2001. ISBN: 3-540-65367-8
- G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, M. Protasi, Complexity and Approximation , Springer. 1999. ISBN: 3-540-65431-3
Course page updates
This course page is available (with possible updates) also for the following academic years:
To read the current information on this course, if it is still available, go to the university course catalogue .
Course information last updated on: 19 marzo 2014, 16:51
Italian version
sad
strutture.univaq