Scheda programma d'esame
ALGORITHMS AND DATA STRUCTURES
ROBERTO GROSSI
Academic year2022/23
CourseMATHEMATICS
Code039AA
Credits6
PeriodSemester 2
LanguageItalian

ModulesAreaTypeHoursTeacher(s)
ALGORITMI E STRUTTURE DATIINF/01LEZIONI60
ROBERTO GROSSI unimap
Obiettivi di apprendimento
Learning outcomes
Conoscenze

Introdurre algoritmi (base) e strutture dati per risolvere problemi su seqeuneze, liste, alberi, grafi, efficienti in tempo e/o spazio. Saranno trattate anche tecniche per valutare la complessita' degli algoritmi e dei problemi. Infine, queste tecniche saranno sperimentate mediante implementazione nel linguaggio C++.

Knowledge

The goal is to introduce (basic) algorithms and data structures to solve problems on sequences, lists, trees and graphs, in efficient time and/or space. We will also deal with techniques for evaluating the complexity of algorithms and problems. Finally, we will experiment these algorithmic techniques by implementing some of them using the C++ language.

Modalità di verifica delle conoscenze

Le capacita' acquisite dallo studente sui temi trattati durante il corso e sulla loro implementazione verranno valutate mediante:

  • Esame orale finale
  • Esame scritto finale
  • Prova pratica di laboratorio
Assessment criteria of knowledge

The student will be assessed on her/his demonstrated ability to discuss and put into practice the main topics presented during the course.

Methods:

  • Final oral exam
  • Final written exam
  • Final laboratory practical demonstration
Capacità

Capacita' di base sull'utilizzo di strutture dati, e sulla comprensione e lo sviluppo di algoritmi efficienti in tempo e/o spazio.

Skills

Basic skills on algorithm and data structure design and time/space complexity evaluation.

Modalità di verifica delle capacità

Esame scritto e orale.

Assessment criteria of skills

Via written and oral exams.

Comportamenti

Gli studenti saranno in grado di valutare l'efficienze degli algoritmi prima della loro implementazione, direttamente dalla loro progettazione. Conoscenza di alcuni problemi difficili, la cui progettazione puo' impattare sulla implamentazione.

Behaviors

Students will be able to evaluate performance of basic algorithms before their implementation, directly from their design. Know some difficult problems and which algorithmic design choices can impact positively or negatively the algorithm implementation.

Modalità di verifica dei comportamenti

Esame scritto e orale.

Assessment criteria of behaviors

Via written and oral exams

Prerequisiti (conoscenze iniziali)

Basi di matematica e di programmazione C.

Prerequisites

Basics of Maths and C programming.

Indicazioni metodologiche

Lezioni frontali.

 

Attivita' di apprendimento:

  • partecipare alle lezioni
  • partecipare alle discussioni
  • studio individuale
  • lavoro in laboratorio

Frequenza consigliata.

Metodi di insegnamento:

  • Lezioni
  • Laboratorio

Per ulteriori dettagli, consultare la home page del corso.

Teaching methods

Delivery: face to face

Learning activities:

  • attending lectures
  • participation in discussions
  • individual study
  • laboratory work

Attendance: Advised

Teaching methods:

  • Lectures
  • Laboratory

For details look at the home page of the course.

Programma (contenuti dell'insegnamento)

Breve introduzione a problemi computazionali: dicidabilita' e trattabilita'(P, NP, NPC, EXP-TIME). Complessita': modelli, dimensione inpute e output, albero decisionale, lower e upper bounds, caso pessimo e medio. Divide-et-impera; relazioni di ricorrenza, teorema fondamentale. Algoritmi su sequenze statice/dinamiche: ricerca e ordinamento. Problema dei matrimoni stabili e sottosequenza di somma massima. Programmazione dinamica: LCS, Partizione e Zaino. Combinazioni e permutazioni. Greedy: Zaino e sue varianti. Rappresentazione e visita di alberi. Dizionari: 2-3 alberi, tabelle hash tables, trie. Algoritmi randomizzati: Quicksort, QuickSelect. Grafi: rappresentazione e visita (DFS e BFS), DAG e ordinamento topologico.

Syllabus

Short introduction to computational issues: decidability and tractability (P, NP, NPC, EXP-TIME). Computational complexity: computation model, input and output size, decision tree, lower and upper bounds, worst and avarage case. Divide-et-impera; recurrence relations, fundamental theorem. Algorithms on static/dinamic sequences: search and sorting. Stable marrigies problem and maximum sum subsequence. Dynamic Programming: LCS, Partition and Backpack. Combination and permutation generation. Greedy: Knapsack and its variants. Trees representation and visit. Dictionaries: 2-3 trees, hash tables, trie. Randomized Algorithms: Quicksort, QuickSelect. Graphs: representation and visit (DFS e BFS), DAG and topological sorting.

Bibliografia e materiale didattico

T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. MIT Press, third edition, 2009.

Ulteriori riferimenti alla home page del corso.

Bibliography

T. Cormen, C. Leiserson, R. Rivest, C. Stein. Introduction to Algorithms. MIT Press, third edition, 2009.

Further bibliography will be indicated and linked in the home page of the course.

Modalità d'esame

Esame orale e scritto, e prova di laboratorio per il linguaggio C++.

Assessment methods

Via written and oral exams, and a C++ programming test.

Updated: 20/02/2023 10:35