18. Lezione/esercitazione del 12/11/04 [2 ore: 14-16, in AULA B] per tutti i turni

di: Algoritmi & Laboratorio ( Modulo 2 )

"Riassunto" della lezione:

• Realizzazione di una coda (mutabile) con un array "circolare" dinamico e costo ammortizzato delle operazioni di enqueue e dequeue (si vedano gli esercizi P17.9 e P17.10 in [Hor]).

• Non e' stato detto nulla che non sia contenuto nel Capitolo 13 di [Hor].

• Non e' stato detto nulla che non sia contenuto nel Capitolo 14 di [Hor].

• Non e' stato detto nulla che non sia contenuto nel Capitolo 18 di [Hor].

Riferimenti (LETTURE OBBLIGATORIE):

• Gestione delle eccezioni ([Hor] capitolo 13),
• Flussi ([Hor] capitolo 14),
• Strutture di dati avanzate ([Hor] capitolo 18).

Esercizi assegnati:

• Esercizio E11.
  Questi esercizi non devono essere consegnati. Essi sono esempi di domande che potrebbero esere fatte in sede di esame, sia nella prova scritta (per il modulo 1) che nel colloquio (per il modulo 2).
  • Esercizi di ripasso del capitolo 13 di [Hor]: R13.1,...,R13.10.
  • Esercizi di ripasso del capitolo 14 di [Hor]: R14.1,...,R14.17.
  • Esercizi di ripasso del capitolo 18 di [Hor]: R18.1,...,R18.15.
• Esercizio E12.
  Scrivere, in Java, un'interfaccia PriorityQueue, che specifichi le operazioni di una struttura dati coda con priorita' (mutabile) di "oggetti generici". Realizzare:
  1. una classe TreePriorityQueue che implementi l'interfaccia PriorityQueue usando la classe TreeSet della libreria Java (ispiratevi a: [Hor] Argomenti avanzati 18.1);
  2. una classe ArrayBinaryHeapPriorityQueue che implementi l'interfaccia PriorityQueue usando la classe ArrayBinaryHeap realizzata nell'Esercizio E9.
  Entrambe le classi devono ridefinire (in modo opportuno) i metodi toString e clone. Prevedere due tipi diversi di costruttore: uno che generi una coda atta a memorizzare oggetti che implementano l'interfaccia Comparable, l'altro che che generi una coda atta a memorizzare oggetti che sono confrontati attraverso un oggetto comparatore. Realizzare un modulo di test tale che:
  • nel modulo di test l'identicatore "TreePriorityQueue" e' usato solo come costruttore, e
  • rimpiazzando la parola "TreePriorityQueue" con "ArrayBinaryHeapPriorityQueue" il modulo di test deve "ancora funzionare".
• Esercizio E13.
  Scrivere, in Java, un'interfaccia UnionFind, che specifichi le operazioni di una struttura dati union find di numeri naturali. Realizzare una classe ArrayUnionFind che implementi l'interfaccia UnionFind. La classe deve ridefinire (in modo opportuno) i metodi toString e clone. Scrivere un modulo di test.
• Esercizio E14.
  Scrivere, in Java, una classe CodiceDiHuffman, con:
  • un costruttore che richiede come argomento un oggetto di tipo SortedMap che rappresenta un alfabeto di caratteri con le relative frequenze,
  • un metodo getCodice() che restituisca un oggetto di tipo SortedMap che associa ad ogni carattere dell'alfabeto il suo codice,
  • un metodo decodifica(String s) che, data una stringa contenente la codifica di un carattere, restituisca il carattere corrispondente, e
  • i metodi toString e clone.
  Scrivere un modulo di test.
• Esercizio E15.
  Scrivere, in Java, un'interfaccia GrafoNonOrientato, che specifichi le operazioni di una struttura dati grafo non orientato (ispiratevi alla Figura 11.2 a pag. 267 di [Dem] - attenzione: dovete decidere come rappresentare i tipi di dato "vertice" e "arco"). Realizzare:
  1. una classe GrafoNonOrientatoConMatriceDiAdiacenza che implementi l'interfaccia GrafoNonOrientato usando una marice di adiacenza;
  2. una classe GrafoNonOrientatoConListeDiAdiacenza che implementi l'interfaccia GrafoNonOrientato usando liste di adiacenza.
  Entrambe le classi devono ridefinire (in modo opportuno) i metodi toString e clone. Realizzare un modulo di test.