CFU: 6 - SSD. ING-INF/05 Descrizione
The purpose of this course is to introduce students to the topics of data structures and algorithm design along with their respective applications. The topics that will be covered are:
• Algorithms Analysis
• Sorting Algorithms
• Algorithmic Paradigms
• Graphs
• Intractable problems
The use of data structures in programming languages and relevant aspects of data and file management will be illustrated by using a high level language.
Didattica Erogativa
La didattica è organizzata in modo tale che ogni corso di studio venga erogato tre volte l’anno e ciascuna erogazione dura due mesi e mezzo. Il sistema consente sempre agli studenti di avere accesso ai contenuti, ma durante il periodo di erogazione, lo studente viene inserito in una classe in cui sono presenti al massimo 20 studenti, in cui svolgere le attività organizzate nel tempo con la guida di un tutor esperto della materia che segue i processi di apprendimento.
Questo modello di erogazione è stato adottato per consentire agli studenti di iscriversi durante tutto l’anno all’Università e di avere la possibilità di entrare nelle classi a seconda del periodo in cui si iscrivono.
Il presente corso, che fornisce 6 crediti formativi, è strutturato in 3 macroargomenti ed è composto da 25 ore di videolezioni, da vedere due volte, per un totale minimo di 50 ore di attività dello studente.
Le videolezioni trattano i seguenti argomenti:
• Lesson n. 1: Introductions and Definitions • Lesson n. 2: Complexity Analysis
• Lesson n. 3: Analysis of recursive programs: recurrences I • Lesson n. 4: Analysis of recursive programs: recurrences II • Lesson n. 5: Sorting
• Lesson n. 6: Heapsort and Quicksort • Lesson n. 7: Sorting - linear time algorithms • Lesson n. 8: Dynamic sets and dictionaries • Lesson n. 9: Binary Search Trees
• Lesson n. 10: Hash Tables I • Lesson n. 11: Hash Tables II
• Lesson n. 12: Algorithmic paradigms: Dynamic programming I • Lesson n. 13: Dynamic programming II
• Lesson n. 14: The greedy paradigm
• Lesson n. 15: Search-based paradigms: backtracking • Lesson n. 16: Graphs I
• Lesson n. 17: Graphs II • Lesson n. 18: Graphs visits
• Lesson n. 19: Application of Depth-First-Search • Lesson n. 20: Minimum Spanning Trees I • Lesson n. 21: Minimum Spanning Trees II
• Lesson n. 22: Shortest paths I • Lesson n. 23: Shortest paths II • Lesson n. 24: All-pairs shortest paths
• Lesson n. 25: Intractable problems and NP completeness
Per ognuno dei 3 macroargomenti del corso saranno disponibili esercizi di autovalutazione che prevedono lo sviluppo tecniche di calcolo e di risoluzione di problemi che consentiranno agli studenti di esercitarsi e di mettere in pratica le conoscenze erogate attraverso le videolezioni e le aule virtuali. Si stima che gli esercizi, corredati di soluzione o provvisti di sistema di correzione automatica del risultato, richiederanno circa 10 ore di impegno dello studente.
Didattica Interattiva
La didattica interattiva avviene sia in modo sincronico che diacronico.
Il Docente/Tutor proporrà ogni settimana argomenti di discussione su forum e wiki, riguardanti approfondimenti sui contenuti del corso trattati in quella settimana, collegati ai macroargomenti delle videolezioni. Si stima che tali attività richiederanno circa 3 ore di impegno dello studente.
Inoltre suddivise per gruppi di 20 studenti ciascuno, saranno svolte aule virtuali interattive (appuntamenti sincroni, in audiovideo streaming su piattaforma Web, con gli studenti collegati che possono interagire via chat testuale). Per la valutazione degli esercizi e la relativa correzione, saranno svolte aule virtuali specifiche con gruppi di studenti collegate ai 3 macroargomenti di cui è composto il corso. Si stima che l’impegno dello studente sarà di circa 3 ore.
Per quanto concerne la didattica in situazione, durante l’erogazione il tutor pone nuovi problemi, non discussi nelle videolezioni e non risolvibili direttamente con i metodi esposti nelle esercitazioni, affidando agli studenti il compito di risolverli (singolarmente o in modo collaborativo) in autonomia, pur sotto la guida del tutor. I problemi possono essere posti a singoli studenti o condivisi con l'intera classe attraverso diversi strumenti e/o ambienti di apprendimento della piattaforma: laboratori virtuali, discussione negli incontri di chat con l'intera classe, invio per email al singolo studente o ad un gruppo, analisi e attività collaborative nel forum con la comunità di studenti. Queste attività stimolano sia il Learning-by-doing sia il Problem Based Learning nel quale lo studente sviluppa e sperimenta in autonomia l'apprendimento su casi pratici di studio e/o in situazioni esperienziali. Ogni settimana, infine, il Docente/Tutor pianifica un'ora di chat in cui fornirà spiegazione aggiuntive sugli argomenti del corso, raccoglierà e risponderà in tempo reale alle domande degli studenti, commenterà gli esercizi proposti e la struttura delle prove di verifica. Le chat saranno pianificate ad inizio erogazione e la loro calendarizzazione sarà disponibile nell'Agenda del Corso. Nel complesso queste attività richiedono circa 13 ore di impegno dello studente.
Autoapprendimento
Sono inoltre presenti materiali didattici collegati agli argomenti delle video lezioni, che si compongono di testi di approfondimento teorico, datasheets e dispense; tali materiali didattici compongono lo studio individuale dello studente di circa 61 ore.
In dettaglio, i materiali didattici collegati:
- Slide del corso, le slide utilizzate dai docenti autori delle videolezioni, che gli studenti potranno scaricare e stampare per crearsi il proprio "quaderno del corso"
- Libri&Articoli: testi, saggi, schede descrittive, approfondimenti,
- Bibliografia: riferimenti ragionati a fonti bibliografiche associati ai singoli argomenti di ogni videolezione
- Sitografia: selezioni ragionate di Siti web collegate agli argomenti della videolezione
Testi d'esame:
I testi d'esame per il corso di Algorithms and Data Structures sono:
T.H.Cohen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3° ed, McGraw-Hill, 2010.
Materiali di supporto e pianificazione dell’apprendimento
In dettaglio, i materiali di supporto e di pianificazione dell’apprendimento collegati sono:
- il Programma del Corso, che contiene informazioni sulla descrizione, gli obiettivi ed i contenuti dell’insegnamento, l’individuazione dei prerequisiti necessari, il riferimento agli esercizi relativi alle videolezioni, l’indicazione dei libri di testo, le indicazioni metodologiche ed i suggerimenti per lo studio della materia
- una Mappa Concettuale dell'insegnamento, che, in formato grafico e navigabile su Web, per ognuno dei macro argomenti riporterà:
o lezioni che affrontano il macroargomento o argomenti trattati in ognuna delle lezioni
o materiali di approfondimento associati agli argomenti o cadenza e temi degli appuntamenti di tutoring online
- la Pianificazione didattica, che illustra tempi e modalità di erogazione dell'insegnamento, corrispondenza tra argomenti delle videolezioni e capitoli dei testi d'esame, argomenti principali del corso
- la Guida all'esame, che illustrerà criteri di ammissione e modalità di svolgimento dell'esame - l’Agenda, che contiene le date e gli orari di svolgimento delle attività di didattica erogativa ed
interattiva (chat, aule virtuali, ricevimenti), nonché degli esami.
Modalità di valutazione in itinere e finale
Le modalità di valutazione del corso sono strutturate da 2 prove di verifica intermedie, che verranno consegnate attraverso la piattaforma UNINETTUNO e valutate dal Docente/Tutor. Tali prove di verifica, di respiro più ampio rispetto agli esercizi di autovalutazione, verteranno sugli argomenti del corso e saranno composte da più problemi ed esercizi. La data limite di consegna delle prove sarà inserita nell'agenda del corso ad inizio di ogni erogazione. Lo studente è chiamato ad assegnarsi un voto al momento della consegna, voto che è "cieco" al Docente/Tutor, finché questi non completi la correzione e a sua volta assegni un voto alla prova dello studente. Questi due dati andranno quindi a popolare il grafico di valutazione dello studente presente nella schermata "Valutazioni e statistiche" del Corso. Si stima che queste prove richiederanno circa 10 ore di lavoro dello studente.
La prova di valutazione finale consiste nello sviluppo di uno dei macroargomenti in cui è suddiviso il corso o parte di essi, dove lo studente, senza l’ausilio di libri o appunti, dovrà dimostrare la piena conoscenza di tutte le tematiche che caratterizzano il tema proposto e mostrare con esempi attinenti la padronanza dell’argomento.