Course Details for A.Y. 2016/2017

The information on this page refer to the academic year 2016/2017. Therefore, several links are not available and data may be incomplete. To read the current information on the course, if it is still available, go to the university course catalogue . To read information relating other academic years, use the list at the bottom of this page.

A. Year:

2016/2017

Name:

Ingegneria degli Algoritmi / Algorithm Engineering

Type:

Course

Basic information

Code:

I0665

Sector:

ING-INF/05

Credits:

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

Term:

2^nd semester

Degree(s):

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

Language:

Italian

Teacher(s):

Daniele Frigioni

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. Metodologie dell'ingegneria degli algoritmi: realistic models, design, theoretical analisys, implementation, experimental analisys. A case study: shortest paths. Speed-up techniques for shortest paths computation: BiDirectional Dijkstra, ALT, Reach, ALT+Reach, Arc Flags.

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

Notes

Si veda anche la pagina sul vecchio sito di ingegneria: http://www.ing.univaq.it/cdl/scheda_corso.php?codice=I0665_I4I

Internet Resources

Homepage:

http://www.didattica.univaq.it/moodle/course/view.php?id=4540

Forum: