Laboratorio di Algoritmi e Strutture Dati

Anno Accademico 2020-2021

Secondo semestre (marzo 2021 - giugno 2021)

Il laboratorio di Algoritmi e Strutture Dati inizia giovedì 18 marzo 2020 dalle 11.30 alle 13.30. Le lezioni si terranno da remoto.

Esercitatori

Per il secondo semestre, gli esercitatori sono Antonio Bucchiarone (bucchiarone${at}fbk${dot}eu) e Cristian Consonni (cristian.consonni${at}unitn${dot}it).

Tutor

Per il secondo semestre, i tutor sono Giovanni Zotta (giovanni.zotta${at}studenti${dot}unitn${dot}it) e Francesco Lotito (quintino.lotito${at}studenti${dot}unitn${dot}it).

Domande progetto

Per inviare domande relative al progetto usate l’indirizzo asd.disi${at}unitn${dot}it, che viene letto dai tutor e dagli esercitatori.

Registrarsi al laboratorio e ai progetti

Il sito di riferimento si chiama judge. Per partecipare vi è richiesto di:

Nella sezione “Link utili” trovate una guida che spiega come funziona il sistema di valutazione di judge.

Organizzazione delle esercitazioni di laboratorio e dei progetti

Le esercitazioni di laboratorio comprendono 12 lezioni – di cui 6 nel primo semestre e 6 nel secondo – alcune delle quali saranno dedicate alla presentazione e implementazione dei progetti. Per il primo semestre, le lezioni si svolgeranno da remoto.

Durante una lezione tipica del laboratorio:

Durante il corso verranno assegnati dei progetti, con tempo di risoluzione attorno alla settimana e da svolgere singolarmente o in gruppo (max 3 persone), che daranno origine a piccoli incrementi (bonus) da aggiungere al voto dello scritto. Questi punteggi aggiuntivi possono essere utilizzati per superare la soglia per accedere all’orale: se avete preso 15 allo scritto e avete 3 punti bonus, siete ammessi in quanto la somma raggiunge il 18. È obbligatorio consegnare almeno un progetto sufficiente per accedere all’orale. Il punteggio aggiuntivo rimane valido negli anni successivi e continua a dare la possibilità di accedere all’orale.

Cosa serve per partecipare al laboratorio

Le lezioni di laboratorio comprendo lo svolgimento di alcuni esercizi di programmazione in C++. In generale, il consiglio è di compilare edeseguire il vostro codice in un terminale pertanto, se già non lo avete a disposizione, dovete installare il compilatore g++. Per scrivere il codice sorgente potente scegliere tra decine di editor.

[Tutti gli OS]

Installare un compilatore: installing a compiler

[(GNU/)Linux]

Tutte le distribuzioni linux hanno dei pacchetti che forniscono il compilatore GNU (gcc per il C, g++ per il C++), ecco due riferimenti:

[Windows]

Guida generale all’installazione di un compilatore e di un editor: guida

[Mac]

Installare g++: guida

Materiale

Primo semestre

Lab Data Slides Prob1 Prob2 Prob3 Prob4 Prob5 Materiale
1 06/10/2020 lab01.pdf Somma di due numeri (somma) Sottosequenza di somma massima (sottoseq) Sottomatrice di somma massima (sottomat) - - soluzioni_lab01.zip
2 13/10/2020 lab02.pdf Ordinamento (sort) Intervalli (intervalli) Ordinamento pesato (sortpesato) Natale a Flatlandia (flatland) - soluzioni_lab02.zip
3 10/11/2020 lab03.pdf Visita di un grafo orientato (visita) Diametro di un grafo non orientato (diametro) Numero di cammini minimi (numcammini) Primo progetto a. a. 2017/2018: 007: Pioggia di laser (laser) - slides, testo, dataset Primo progetto a. a. 2016/2017: Pokémon Park (pokemon) - slides, testo, dataset graphs.zip, soluzioni_lab03.zip
4 17/11/2020 lab04.pdf Dimensione massima componente fortemente connessa (componente) Ordinamento topologico (toporder) Cammino più lungo (camminolungo) Primo progetto a. a. 2019/2020: Cicli ciclabili (cicli) - slides, testo, dataset Primo progetto a. a. 2014/2015: Batman si annoia (batman) - slides, testo, dataset soluzioni_lab04.zip
5 10/12/2020 lab05.pdf Primo progetto a. a. 2020/2021: Lettere da Powarts (powarts) - slides, testo, dataset sottoposizioni su arena - - - soluzione progetto, classifica punti bonus
6 15/12/2020 lab05.pdf Primo progetto a. a. 2020/2021: Lettere da Powarts (powarts) - slides, testo, dataset sottoposizioni su arena - - - soluzione progetto, classifica punti bonus

Secondo semestre

Lab Data Slides Prob1 Prob2 Prob3 Prob4 Prob5 Materiale
7 18/03/2021 lab07.pdf Massimizzazione della somma in un insieme (zaino) Sottoinsieme crescente di somma massina (sottocres) Sequenze Possibili (pillole) - - soluzioni_lab07.zip
8 15/04/2021 lab08.pdf Sottosequenza comune massimale (lcs) Min-cover su albero (mincover) Min-cover su albero pesato (mincoverpesato) Progetto programmazione dinamica a. a. 2016/2017: La vendetta del Re Lich (lich) - slides, testo, dataset Progetto programmazione dinamica a. a. 2017/2018: Assedio a Nassau (nassau) - slides, testo, dataset soluzioni_lab08.zip + slide soluzioni esercizi
9 29/04/2021 lab09.pdf Esercitazione libera programmazione dinamica - - - - codice Java vertex cover (zip)
10 13/05/2021 lab10.pdf Commesso viaggiatore (tsp) Progetto algoritmi approssimati a.a. 2017/2018: Alpinocalypse Now (alpini) - slides, testo, dataset Progetto algoritmi approssimati a.a. 2018/2019: Game of (Approximated) Thrones (got) - slides, testo, dataset Progetto algoritmi approssimati a.a. 2019/2020: Star Wars: Il Risveglio dell’Algoritmo - La gara degli sgusci (swrace) - slides, testo, dataset - materiali progetti approssimati
11 27/05/2021 - Secondo progetto a.a. 2020/2021: ASD: Endgame slides, testo, dataset, materiali Sottoposizioni su arena - - - classifica punti bonus, soluzione progetto
12 01/06/2021 - Secondo progetto a.a. 2020/2021: ASD: Endgame slides, testo, dataset, materiali Sottoposizioni su arena - - - classifica punti bonus, soluzione progetto

Progetti degli anni passati

Anno Accademico 2020-2021

Anno Accademico 2019-2020

Anno Accademico 2018-2019

Anno Accademico 2017-2018

Anno Accademico 2016-2017

Anno Accademico 2015-2016

Anno Accademico 2014-2015