# Course Details for A.Y. 2010/2011

#### Name:

**Algoritmi e Strutture Dati II / Algorithms and Data Structures II**

### Basic information

##### Degree(s):

Laurea Magistrale in Informatica 1° anno curriculum SDRC Obbligatorio

Laurea Magistrale in Informatica 1° anno curriculum ASSC Obbligatorio

##### Language:

Italian

### 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

### 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.

### 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: 23 febbraio 2011, 18:48*