Course Syllabus
Obiettivi
Scopo del corso e' 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
Introduzione: tipi astratti di dati e strutture dati.
Strutture dati statiche (Array) e dinamiche (Liste).
Pile e code
Alberi Binari e Alberi Binari di Ricerca
Heap e heapsort, code con priorita'.
Prerequisiti
Nozioni base di programmazione
Modalità didattica
Nel periodo di emergenza Covid-19 le lezioni ed esercitazioni saranno videoregistrate (alcune di esse potranno essere trasmesse in modalità sincrona); ci saranno inoltre dei momenti sincroni (in streaming, non registrati) di discussione e risposta alle domande degli studenti.
Lezioni, esercitazioni e approfondimenti sperimentali. Attivita' di studio individuali supportate da materiali didattici in E-learning.
Le lezioni sono tenute in italiano.
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 (lucidi ed esercizi) disponibili 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:
- 2 esercizi che richiedono sviluppo di un algoritmo ricorsivo o iterativo per la soluzione di un problema assegnato
- 2 esercizi di simulazione su input specifici degli algoritmi presentati a lezione
- domande aperte relative alle nozioni teoriche presentate a lezione
Ogni esercizio vale 6 punti, e le domande di teoria valgono, complessivamente, 6 punti
Possono essere assegnati fino a 2 punti aggiuntivi in caso di esercizi svolti particolarmente bene.
La prova scritta puo' essere sostituita da due prove parziali, che si tengono a meta' corso e nel primo appello di giugno, a fine corso. Le prove parziali sono riservate alle matricole. Ogni prova e' costituita da:
- 1 esercizio che richiede sviluppo di un algoritmoper la soluzione di un problema assegnato
- 1 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. E' prevista la possibilita' 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.
Introduction to Abstract Data Types and Data structures.
Arrays and Linked lists.
Stacks and Queues.
Binary trees and Search Binary Trees.
Heap and Heapsort, priority queues.
Prerequisites
Basics of Computer Programming
Teaching form
During the Covid-19 emergency, lectures and practice exercises will be recorded (some of them could be online). There will be some discussions and answers to questions, in streaming and not recorded.
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.
Textbook and teaching resource
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, Mit press ed.
Further slides and exercises are available through the e-learning website.
Semester
Second semester
Assessment method
Written examination, maximum
mark 30/30. The exam consists of
- 2 exercises to be solved by developing an algorithm to solve a given computing problem
- 2 simulations on specific inputs of algorithms illustrated during the lectures
- open questions concerning theoretical aspects discussed during the lectures
Score for each exercise: 6 points
Score for theoretical questions: 6 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:
- 1 exercise to be solved by developing an algorithm to solve a given computing problem
- 1 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