Search    Print

Algoritmi e Strutture Dati
Algorithms and Data Structures
Giuseppa Ribighini

Seat Ingegneria
A.A. 2016/2017
Credits 9
Hours 72
Period II
Language ENG

Prerequisites
knowledge of fundamentals of computer and an imperative programming language.

Learning outcomes
KNOWLEDGE AND UNDERSTANDING:
The course enables students to acquire appropriate knowledge of data structures and algorithms for the solution of remarkable fundamental problems (search, sort) taking into account the computational complexity of each algorithm, and to know how to implement it in an appropriate language, understanding modes and limits for the application of the examined algorithms.
CAPACITY TO APPLY KNOWLEDGE AND UNDERSTANDING:
After completing the course, students will be able to formalize nformation engineering problems using appropriate algorithms and data structures (correct, efficient)
TRANSVERSAL SKILLS:
The group work on the use and comparison of algorithms helps to improve student's ability of making judgements and communicate. Finally it will be stimulated the ability to learn autonomously and in-depth study.

Program
ntroduction to algorithms. Numerical algorithms for solving integrals and systems of linear equations. Design of recursive algorithms. Computational complexity, asymptotic notations, computational complexity of main structures, and computational complexity of recursive functions. Basic data structures. Sorting algorithms and their computational complexity. Dynamic lists: algorithms for search, insertion, and deletion and their computational complexity. Binary search trees: recursive algorithms for search, insertion, and deletion and their computational complexity. A short introduction to red-black trees, B-trees, AVL trees and trees 2-3. Hash tables for closed addressing and routing: algorithms for search, insertion and deletion and their computational complexity. Abstract datatypes: design and realization. The language used in the course is the C programming language.

Development of the examination
LEARNING EVALUATION METHODS
The evaluation learning consists of two tests: -a written test on topics covered in the course to be completed in two hours -an oral examination during which students discuss one or more course topics and any gaps arisen in the written test. The written test is preparatory to the oral test. Student must obtain at least the sufficiency in the written test in order to be admitted to the oral test. Students must also submit, prior to the written test or during the same, one project on one of the course topics at its choice. The project must be developed by a groups of four or five people and will be exposed by each group member during the oral examination.

LEARNING EVALUATION CRITERIA
The student must demonstrate an appropriate knowledge about data structures, the most appropriate algorithms for each problem, and how these algorithms should be implemented.

LEARNING MEASUREMENT CRITERIA
Both in the written test and the oral examination, the student must demonstrate to know course topics, expose them in a sufficiently correct way using an appropriate technical terminology. Each test the assign a score up to 30.

FINAL MARK ALLOCATION CRITERIA
In order to obtain a positive overall outcome, the student must achieve a score greater or equal than 18, both in the written test and the oral. The maximum rating is achieved by demonstrating a thorough understanding of content, exhibited with complete mastery of the technical language and presenting a good project. Full mark with distinction is reserved to students who, having played both tests correct and complete way, have shown a particular brilliance both on the written and in the oral test and a good autonomy in project work.

Recommended reading
P.Foggia, M. Vento - “Algoritmi e strutture dati - Astrazione, progetto e realizzazione“- McGraw Hill 2011. (Book chosen) C. Demetrescu, I. finocchi, G. F. Italiano - “Algoritmi e strutture dati“-McGraw Hill 2008 C. Demetrescu, I. finocchi, G. F. Italiano - “Progetto di algoritmi e strutture dati in Java“-McGraw Hill 2007. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein - “Introduzione agli algoritmi e strutture dati“-McGraw Hill 2010

Courses

• Ingegneria Informatica e dell'Automazione (Corso di Laurea Triennale (DM 270/04))