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.
Conoscenza e capacità di comprensione
- Conoscenza dei concetti fondamentali relativi ai problemi computazionali
- Conoscenza delle tecniche base per dimostrare la correttezza di un algoritmo
- Conoscenza del funzionamento dei paradigmi di programmazione ricorsiva e divide-et-impera
- Conoscenza del funzionamento di algoritmi di ordinamento
- Conoscenza delle tecniche per valutare l'efficienza di algoritmi e strutture dati
- Conoscenza del funzionamento e delle caratteristiche di diverse strutture dati fondamentali
Conoscenza e capacità di comprensione applicate
- Capacità di analizzare la correttezza formale di un algoritmi iterativo e ricorsivo
- Capacità di applicazione dei paradigmi di programmazione ricorsiva e divide-et-impera per risolvere nuovi problemi computazionali
- Capacità di applicazione delle tecniche di valutazione dell'efficienza degli algoritmi iterativi, ricorsivi e divide-et-impera
- Capacità di simulare il funzionamento di algoritmi complessi e strutture dati fondamentali su istanze specifiche
- Capacità di utilizzare correttamente le strutture dati fondamentali per risolvere nuovi problemi computazionali
Autonomia di giudizio
- Capacità di scegliere l'algoritmo più efficiente e/o più indicato per risolvere nuovi problemi computazionali specifici
- Capacità di scegliere la struttura dati più efficiente e/o più indicato per risolvere nuovi problemi computazionali specifici
Abilità comunicative
- Saper utilizzare correttamente lo pseudocodice per presentare formalmente e in modo non ambiguo un algoritmo
- Saper comprendere e utilizzare il lessico corretto per comprendere o descrivere le caratteristiche di un algoritmo e di una struttura dati
Capacità di apprendere
- Essere in grado di ricercare e selezionare criticamente un nuovo algoritmo più indicato per risolvere un nuovo problema computazionale
- Essere in grado di ricercare e selezionare criticamente una nuova struttura dati più indicata per risolvere un nuovo problema computazionale
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, 44 ore (20 di esercitazione e 24 di laboratorio) in modalità 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.
Knowledge and Understanding
- Knowledge of basic concepts related to computational problems
- Knowledge of basic techniques to prove the correctness of an algorithm
- Knowledge of how recursive and divide-and-conquer programming paradigms work
- Knowledge of how sorting algorithms work
- Knowledge of techniques to evaluate the efficiency of algorithms and data structures
- Knowledge of how different fundamental data structures work and their characteristics
Applying Knowledge and Understanding
- Ability to analyze the formal correctness of iterative and recursive algorithms
- Ability to apply recursive and divide-and-conquer paradigms to solve new computational problems
- Ability to apply techniques to evaluate the efficiency of iterative, recursive, and divide-and-conquer algorithms
- Ability to simulate how complex algorithms and fundamental data structures work on specific examples
- Ability to correctly use fundamental data structures to solve new computational problems
Making Judgments
- Ability to choose the most efficient and/or most suitable algorithm to solve specific new computational problems
- Ability to choose the most efficient and/or most suitable data structure to solve specific new computational problems
Communication Skills
- Ability to correctly use pseudocode to formally and clearly present an algorithm
- Ability to understand and use the correct terminology to describe or understand the characteristics of an algorithm or a data structure
Learning Skills
- Ability to search for and critically select a new algorithm that is more suitable for solving a new computational problem
- Ability to search for and critically select a new data structure that is more suitable for solving a new computational problem
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, 44 hours (20 for exercises and 24 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