Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/safehtml.php on line 308
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 159
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 161
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 162
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 163
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 165
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 166
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 167
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 243
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 250
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 259
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 266
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 273
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 280
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 467
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 469
Deprecated: Assigning the return value of new by reference is deprecated in /home/demetres/public_html/didattica/ae2008/3rdparty/core/safehtml/classes/HTMLSax.php on line 471
Homework
Questa pagina raccoglie gli homework che vengono assegnati come esercitazione durante il corso. La soluzione di tutti gli homework o di un loro sottoinsieme può confluire nella tesina software prevista per il superamento dell'esame.
HW0
Confrontare sperimentalmente il tempo di esecuzione di un programma che scandisce una matrice n x n per righe e il tempo di esecuzione di un programma che la scandisce per colonne. Ci aspettiamo che i tempi di esecuzione siano uguali o diversi? Produrre un grafico che mostra il rapporto tra il tempo di scansione per colonne diviso il tempo di scansione per righe in funzione del lato n della matrice. Considerare n che varia da qualche centinaio a qualche migliaio.
HW1
Implementare il seguente algoritmo per la verifica di duplicati in una lista:
algoritmo verificaDupHashList(sequenza L) -> boolean
sia H una tabella hash inizialmente vuota
per ogni elemento x di L
se x appartiene ad H allora restituisci true
altrimenti aggiungi x ad H
restituisce false
realizzando un metodo Java con il seguente prototipo:
public static boolean verificaDupHashList
(List L
)
Estendere inoltre l'analisi sperimentale del capitolo 1 di [
T1] in modo da confrontare le prestazioni dell'algoritmo scritto con quelle dell'algoritmo
verificaDupOrdList basato su ordinamento. Scrivere una breve relazione sui risultati sperimentali ottenuti, includendo grafici prestazionali. In particolare, graficare il rapporto di prestazioni di
verificaDupHashList e
verificaDupOrdList rispetto a quello di
verificaDupArray (si veda [
T1, capitolo 1]).
Come dati di test si suggerisce di utilizzare:
- sequenze di valori casuali (ad esempio, interi)
- sequenze di valori derivati da testi reali (ad esempio, sequenze di stringhe ottenute da romanzi classici come quelli citati alla pagina materiale didattico).
Per effettuare gli esperimenti utilizzare la metodologia illustrata in [
A1].
HW2
Progettare una struttura dati di dimensione O(n) che realizza il tipo di dato
ArrayDinamico in modo che ciascuna operazione set/get/expand/shrink abbia costo costante nel caso peggiore (e non soltanto ammortizzato come visto a lezione).
HW3
Scrivere una classe Java DynamicArray che implementa l'interfaccia
List∞ ed estende la classe
AbstractList∞ basata sulla tecnica del raddoppiamento/dimezzamento. Supportare almeno le seguenti operazioni:
- boolean add∞(E e)
- E get∞(int index)
- E set∞(int index, E element)
- int size∞()
Effettuare poi un confronto sperimentale delle prestazioni delle classi DynamicArray,
ArrayList∞ e
LinkedList∞ su una sequenza di 3n operazioni della forma <add, set, get, add, set, get, ...> dove ciascuna add aggiunge alla collezione un intero a caso, ciascuna get preleva una cella a caso tra 0 e size()-1, e ciascuna set modifica il contenuto di una cella a caso tra 0 e size()-1 con un intero casuale.
Scrivere un programma java per ciascuna classe in modo da poter effettuare test separati per ognuna di esse.
Misurare il tempo complessivo richiesto dai metodi di ciascuna classe su sequenze con n che varia ad esempio da 50000 a 100000 con passo 5000. Graficare poi il tempo di esecuzione medio per operazione (ottenuto dividendo il tempo totale per 3n) in funzione di n.
HW4
Scrivere una classe Java DynamicArrayWC che implementa l'interfaccia
List∞ ed estende la classe
AbstractList∞ basata sulla struttura dati dell'homework 2. Supportare almeno le stesse operazioni previste dall'homework 3 per la classe DynamicArray. Estendere inoltre la sperimentazione dell'homework 3 includendo anche la classe DynamicArrayWC nei grafici.
Produrre infine un grafico che mostra il tempo massimo per operazione (invece del tempo medio) in funzione di n per ciascuna delle classi ArrayList, LinkedList, DynamicArray, e DynamicArrayWC utilizzata. Per questo esperimento utilizzare una sequenza di sole add.
HW5
Implementare un allocatore di memoria in C (malloc, free, realloc) e studiarne le prestazioni su vari tipi di sequenze di operazioni reali e sintetiche. La descrizione completa dell'homework è disponibile
qui.
HW6
Realizzare una classe grafo in Java come implementazione dell'interfaccia
Grafo∞ della libreria asdlab [
Software] e graficare il rapporto prestazionale della classe realizzata rispetto alla classe
GrafoLA∞ nel caso in cui le operazioni siano generate dalla
visita in ampiezza∞ di un grafo a partire dal suo nodo di indice zero. Utilizzare come dati di test i grafi stradali del
9th DIMACS Implementation Challenge∞.
- Può essere utile la classe FIleParser.java∞ per caricare in memoria grafi da file in formato DIMACS realizzata da Valerio Bellizia.
HW7
Scrivere due programmi A e B in un linguaggio a scelta: A apre un file e lo legge 4 byte alla volta sequenzialmente. B apre lo stesso file e lo legge 4 byte alla volta saltando in posizioni casuali nel file. Questa seconda modalità di lettura potrebbe richiedere anche settimane se il file è molto grande: si consiglia pertanto di non leggere tutto il file, ma effettuare solo qualche decina di migliaia di letture e calcolare il tempo medio per ogni lettura. Graficare il rapporto di prestazioni di B rispetto ad A (tempo medio per leggere 4 byte).
HW8
Realizzare l'operazione di cancellazione di un item da un B-Tree completando il codice C disponibile
qui∞.
Graficare poi il tempo totale richiesto per effettuare una sequenza di N inserimenti di chiavi seguita da una sequenza alternata di N inserimenti ed N cancellazioni di chiavi in funzione di N. Scegliere ad esempio le chiavi casualmente e assumere che il dizionario possa contenere duplicati. Provare con N che varia da qualche milione a qualche miliardo con chiavi a 32 bit fissando la block size a 8KB. Fare un ulteriore esperimento in cui si fissa N e si varia B ad esempio da 64 byte a 256 KB graficando il tempo totale in funzione di B.
HW9
Scrivere una classe Java che realizza gli heap binomiali rilassati come estensione degli
heap binomiali∞ della libreria
asdlab∞ e una classe che realizza gli heap di Fibonacci come estensione degli heap binomiali rilassati. Confrontare poi sperimentalmente l'efficienza dell'algoritmo di
Dijkstra∞ utilizzando come code con priorità i
d-Heap∞, gli
heap binomiali∞, gli heap binomiali rilassati, e gli heap di Fibonacci. Utilizzare i grafi dell'homework 6 come dati di test.