Course Details for A.Y. 2014/2015

The information on this page refer to the academic year 2014/2015. 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:

2014/2015

Name:

Algoritmi e Strutture Dati / Algorithms and Data Structures

Type:

Module

Main course:

Algoritmi e Strutture Dati con Laboratorio / Algorithms and Data Structures with Lab

Basic information

Code:

F1I012

Sector:

INF/01

Credits:

: Bachelor Degree in Computer Science 6 CFU (a)

Term:

1^st semester

Degree(s):

Bachelor Degree in Computer Science 2^nd anno curriculum General Compulsory

Language:

Italian

Course Objectives

To provide the students with competences about main data structures and algorithms, and to make them learn how to analyze the computational complexity of algorithms and problems. Finally, to develop an intuition about how to solve efficiently a computational problem.

Course Content

Algorithms and problems. Complexity analysis of an algorithm. Lower and upper bound.
Sorting algorithms: insertion-sort, selection-sort, merge-sort, quick-sort
Priority queues: binary heaps, binomial heaps, heap-sort.
The dictionary problem: searching, inserting, deleting. Hast tables and AVL trees.
Graphs: definitions, memory representations, DFS and BFS.
Elementary graph algorithms: shortest paths and minimum spanning trees.

Learning Outcomes (Dublin Descriptors)

On successful completion of this course, the student should

By the end of this module students will be able to: 1) understand the importance of designing efficient algorithms; 2) analyze the resources (space and time) needed by an algorithm; 3) known efficient algorithms for basic computational problems (sorting, searching, graph problems, etc.).
The aim is to make the student capable of abstracting models and formal algorithmic problems from real computational problems, and designing efficient algorithmic solutions.
Through the presentation and the comparison of different solutions to a given probelm, students will be guided to learn and to identify independently their most efficient solution.
The course will encourage the development of the following skills of the student: capability of formally presenting and modelling concrete problems, focusing on their main features and discarding the inessential ones.
The course aims to develop in undergraduate students competencies and abilities necessary in their future studies, especially with respect to advanced algorithmic courses.

Prerequisites and Learning Activities

Students have to know: - elementary data structures (array, list, …) - recursion - summation, proof by induction, calculus

Assessment Methods and Criteria

The exam should be completed jointly with the lab module. It consists of: - a written and oral examination on the theory module: - a written (mandatory) and oral (optional) examination on the lab module. Both parts provides also an (optional) intermediate written examination.

Textbooks

C. Demetrescu, I. Finocchi, G.F. Italiano, Algoritmi e Strutture Dati , Ed. McGraw-Hill.

Internet Resources

Homepage:

http://www.di.univaq.it/~proietti/didattica.html

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 novembre 2014, 09:30