# Course Details for A.Y. 2019/2020

#### Name:

**Ingegneria degli Algoritmi / Algorithm Engineering**

### Basic information

##### Credits:

*:* Laurea Magistrale in Ingegneria Informatica e Automatica 9 CFU (b)

##### Degree(s):

Laurea Magistrale in Ingegneria Informatica e Automatica 1^{st} anno curriculum Generale Compulsory

##### Language:

Italian

### Course Objectives

The student will be introduced to the most important aspects of Algorithm Engineering, whose aim is that of bridging the gap between classic algorithm theory and implementation of algorithms in practice. Driven by concrete applications, algorithm engineering complements theory by the benefits of experimentation and puts equal emphasis on all aspects arising during a cyclic solution process ranging from realistic modelling, design, analysis, robust and efficient implementations to careful experiments.

### Course Content

- Introduction to algorithms and data structures. The Algorithm engineering process.
- Algorithms and problems. Complexity analysis of an algorithm. O, Omega and Theta notations. Lower and upper bound.
- Sorting problem. Lower bound. Sorting algorithms: BubbleSort, HeapSort, MergeSort, QuickSort, IntegerSort, BucketSort, RadixSort.
- Dictionary problem. Binary search trees. Balanced bynary search trees. AVL trees. 2-3 trees. Hash Tables.
- Priority queues: elementary representations, binary heaps, binomial heaps.
- Graphs: definitions, memory representations. Graph visits: DFS and BFS. Connected components.
- Minimum spanning tree. Definitions and properties. Algorithms: greedy, Kruskal, Prim.
- Shortest paths. Definitions and properties. Algorithms: Bellmann-Ford, algorithm for DAGs, Djikstra, Floyd-Warshall.
- NP-completeness. Decision problems. Complexity classes P and NP. NP-complete problems. Approximation algorithms: vertex cover.
- Algorithm engineering. Definitions and methodologies: realistic models, design, theoretical analysis, implementation, experimental analysis, Design of Experiments (DOE), Tuning algorithms and code, code profiling, code optimization, data analysis, algorithms and data structures as experimental subjects.
A case study: distance queries in large-scale dynamic graphs.

### Learning Outcomes (Dublin Descriptors)

On successful completion of this course, the student should

- Have profound knowledge of basic concepts of algorithm engineering; has profound knowledge and understanding of how these concept impact on the performance of a computer; have profound knowledge of advanced algorithms and data structures, complexity analysis of algorithms; knowledge of the practical applications scenarios of algorithms and data structures; knowledge of the algorithm engineering process and how it contribute in bridging the gap between classic algorithm theory and implementation of algorithms in practice.
- Have ability to relate different topics; ability to solve algorithmic problems never faced in classroom, but solvable through logic deductions and reasoning; ability in analyzing the computational complexity of algorithms; ability to complement algorithmic theory by the benefits of experimentation driven by concrete applications; ability in realistic modelling, design, analysis, robust and efficient implementations, and careful experiments.
- Have ability to critically analyze and synthesize algorithm engineering concepts; ability to apply these concepts to real world algorithmic problems coming from real application scenarios; interest in design and pragmatic implementation aspects of algorithms and their experimentation.
- Demonstrate ability to understand and explain the knowledge acquired by the course.
- Have capacity to read and understand other texts/papers on related topics using notions learnt by the course and understand their applications.

### Prerequisites and Learning Activities

Basic programming skills (C/C++). Elementary data structures: arrays, lists, queues, stacks, and trees, and their representation in RAM. Basic notions of mathematic and probability.

### Assessment Methods and Criteria

Written and oral exams

### Textbooks

- Camil Demetrescu, Irene Finocchi, Giuseppe F. Italiano, Algoritmi e Strutture Dati (seconda edizione) , McGraw-Hill. 2008 . Testo di riferimento
* *
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, Introduzione agli Algoritmi e Strutture Dati (terza edizione) , McGraw-Hill. 2005. Testo di approfondimento
* *
- Camil Demetrescu, Umberto Ferraro Petrillo, Irene Finocchi, Giuseppe F. Italiano, Progetto di Algoritmi e Strutture Dati in Java , McGraw-Hill . 2007 . Testo di approfondimento
* *
- Catherine McGeoch, A guide to experimental algorithmics , Cambridge University Press.
* *

### Notes

- See also http://www.mattiademidio.com/graduate.php or http://www.ing.univaq.it/cdl/scheda_corso.php?codice=I0665_I4I

### 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: 15 luglio 2019, 12:33*