Course Syllabus
Obiettivi
Scopo del corso è insegnare allo studente come progettare, valutare e implementare algoritmi efficienti, utilizzando in modo opportuno le tecniche di programmazione e le strutture dati adeguate.
Si presenteranno, a tal fine, le tecniche di programmazione ricorsiva e Divide-et-impera e le principali strutture di dati. Verranno fornite le competenze necessarie a valutare quali tecniche e quali strutture dati scegliere per affrontare al meglio i diversi tipi di problemi computazionali.
Contenuti sintetici
Metodologie di base per progettare algoritmi e analizzarne l’efficienza. Strutture dati fondamentali: definizioni e utilizzo
Programma esteso
- Introduzione: Algoritmo, problema, istanza.
- Analisi di algoritmi: Valutazione dei tempi di esecuzione, caso pessimo, ottimo e medio.
- Programmazione ricorsiva e approccio Divide-et-Impera: Mergesort e Quicksort.
- Valutazione del tempo di esecuzione di algoritmi ricorsivi: equazioni di ricorrenza.
- Altri algoritmi di ordinamento: ordinamento in tempo lineare.
- Strutture dati fondamentali: Array, liste, pile e code.
- Alberi Binari e Alberi Binari di Ricerca
- Heap e code con priorità. Heapsort.
- Grafi e loro rappresentazione in memoria.
- Algoritmi di visita dei grafi: BFS e DFS.
Prerequisiti
Nozioni base di programmazione
Modalità didattica
Lezioni, esercitazioni e approfondimenti sperimentali. Attività di studio individuali supportate da materiali didattici in E-learning.
Le lezioni sono tenute in italiano. Tutte le attività verranno svolte in presenza: 32 ore di lezioni frontali in modalità erogativa, 40 ore (20 di esercitazione e 20 di laboratorio) in modalita' interattiva.
Materiale didattico
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduzione agli Algoritmi e Strutture dati, Ed. Mc. Graw Hill
Materiale integrativo disponibile sul sito e-learning.
Periodo di erogazione dell'insegnamento
Secondo Semestre
Modalità di verifica del profitto e valutazione
Prova scritta: la valutazione massima della prova scritta è 30/30. Tale prova consiste in:
- Esercizi che richiedono sviluppo di un algoritmo ricorsivo o iterativo per la soluzione di un problema assegnato
- Esercizi di simulazione relativi ad algoritmi presentati a lezione
- Domande aperte relative alle nozioni teoriche presentate a lezione
Le domande di teoria valgono, complessivamente, 8 punti
Possono essere assegnati fino a 2 punti aggiuntivi in caso di esercizi svolti particolarmente bene.
Prove parziali:
La prova scritta può essere sostituita da due prove parziali, che si tengono a metà corso e nel primo appello di giugno, a fine corso. Le prove parziali sono riservate alle matricole. Ogni prova è costituita da:
- Un esercizio che richiede sviluppo di un algoritmo per la soluzione di un problema assegnato
- Un esercizio di simulazione su input specifici degli algoritmi presentati a lezione
- Domande aperte relative alle nozioni teoriche presentate a lezione
Ogni prova parziale ha valutazione massima 15/15: il voto finale si ottiene sommando i voti delle due prove parziali. È prevista la possibilità di recuperare una sola delle due prove parziali (in caso di insufficienza, assenza o anche per migliorare il voto) nell'appello di luglio. Possono essere assegnati fino a 2 punti aggiuntivi (totali per le due prove) in caso di esercizi svolti particolarmente bene.
Orario di ricevimento
Su appuntamento
Aims
The aim of the course is to teach to design, evaluate and implement efficient algorithms, making use of the most appropriate progamming techniques and data structures.
We will introduce recursive programming and Divide-and-conquer technique, and main data structures. Students will learn to evaluate which programming technique and which data structures are more adequate to solve various types of computational problems
Contents
Basic techniques to develop algorithms and to analyse their efficiency. Introduction to the use of fundamental data structures.
Detailed program
- Introduction and basic definitions: algorithm, problem, instance.
- Computational complexity analysis of algorithms.
- Recursive programming and Divide-and-Conquer programming technique: Mergesort and Quicksort.
- Time complexity for recursive algorithms: recursive equations.
- Linear time sorting algorithms.
- Basic data structures: arrays, linked lists, stacks, queues.
- Binary trees and Search Binary Trees.
- Heap and priority queues. Heapsort.
- Graphs and graph representation.
- Traversing algorithms for graphs: BFS and DFS
Prerequisites
Basics of Computer Programming
Teaching form
Theoretical lectures, exercises, and practical implementation of proposed algorithms. Further exercises are available online, through an E-learning website.
The course is taught in Italian. All activities are in-person: 32 hours in unidirectional mode, 40 hours (20 for exercises and 20 for laboratory) in interactive mode.
Textbook and teaching resource
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, Mit press ed.
Further material available through the e-learning website.
Semester
Second semester
Assessment method
Written examination, maximum mark 30/30. The exam consists of
- Exercises to be solved by developing an algorithm to solve a given computing problem
- Simulations on specific inputs for algorithms illustrated during the lectures
- Open questions concerning theoretical aspects discussed during the lectures
Score for theoretical questions: 8 points (in total)
Up to 2 more points can be given in case of extremely good exercises.
The exam can be substituted by two intermediate exams, each evaluating some of the subjects covered during the course.
Split examination:
Written examination can be replaced by two split short exams, held during mid course break and at the end of the course. Such possibility is only allowed to first-year students. Each short exam consist of:
- An exercise to be solved by developing an algorithm to solve a given computing problem
- A simulation on specific inputs of algorithms illustrated during the lectures
- Open questions concerning theoretical aspects discussed during the lectures
The maximum score for each short exam is 15/15. Final mark is obtained by summing the marks of the two short exams. Students can repeat one of the two short exams (in case of non sufficient result, or to improve the result) during the exam in july.
Up to 2 more points can be given (considering both short exams) in case of extremely good exercises.
Office hours
By appointment