SCRITTO 25/9/2000
Un "ricoprimento di vertici" in un grafo G è un insieme di vertici C tale che ciascuno spigolo di G abbia almeno un estremo in C. Dato un grafo G, fornire un algoritmo che generi un ricoprimento di vertici.
Dell'algoritmo presentato:
- si dia la spiegazione a parole;
- si fornisca l'implementazione in linguaggio C;
- si valuti la complessità computazionale.
SCRITTO 1/6/2000
Dato un albero n-ario calcolare l'altezza della sua rappresentazione in forma binaria.
Dell'algoritmo presentato:
- si dia la spiegazione a parole;
- si fornisca l'implementazione in linguaggio C;
- si valuti la complessità computazionale.
SCRITTO 10/4/2000
Si definisce matrice di incidenza INC(nxm) una matrice ad n righe ed m colonne tale che INC(i,j) = 1 se lo spigolo j-esimo è incidente al vertice i-esimo.
Dato in input un grafo rappresentato tramite matrice di incidenza, progettare un algoritmo che dia in output l'albero T ottenuto tramite visita in ampiezza. L'albero T sia rappresentato tramite liste a tre campi.
Dell'algoritmo presentato:
- si dia la spiegazione a parole;
- si fornisca l'implementazione in linguaggio C;
- si valuti la complessità computazionale.
SCRITTO 16/2/2000
Dato un grafo non orientato G (V,E), progettare un algoritmo che dia in output 1 se G è aciclico e 0 in caso contrario.
Dell'algoritmo presentato:
- si dia la spiegazione a parole;
- si fornisca l'implementazione in linguaggio C;
- si valuti la complessità computazionale.
SCRITTO 31/1/2000
Calcolare l'altezza di un albero n-ario nota la sua rappresentazione in forma binaria.
Dell'algoritmo presentato:
- si dia la spiegazione a parole;
- si fornisca l'implementazione in linguaggio C;
- si valuti la complessità computazionale.
SCRITTO 14/1/2000
Dato un grafo non orientato G= (V,E) con n vertici ed m spigoli rappresentato come matrice di incidenza INC(nxm), scrivere l'algoritmo di visita in profondità utilizzando direttamente tale struttura.
Si definisce matrice di incidenza INC(nxm) una matrice ad n righe ed m colonne tale che INC(i,j) = 1 se lo spigolo j-esimo è incidente al vertice i-esimo.
Dell'algoritmo presentato:
- si dia la spiegazione a parole;
- si fornisca l'implementazione in linguaggio C;
- si valuti la complessità computazionale.
SCRITTO 26/11/1999
Progettare un'algoritmo che dati in input due heap di 2n - 1 nodi ciascuno, descriva il procedimento che permette di fonderli in un unico heap di 2n+1 - 2 nodi.
Dell'algoritmo presentato:
- si dia la spiegazione a parole;
- si fornisca l'implementazione in linguaggio C;
- si valuti la complessità computazionale.
SCRITTO 27/9/1999
Dati n elementi memorizzati in uno dei seguenti modi:
- su un heap massimo,
- su un albero binario di ricerca,
- su un albero binario qualunque,
cancellare il valore massimo dalla struttura considerata, mantenendo inalterate le proprietà della stessa.
Per ogni algoritmo fornire:
- una spiegazione a parole,
- l’implementazione in C
- la complessità computazionale richiesta.
SCRITTO 8/10/1999
Dati due vettori di interi di lunghezza n, ordinati in modo crescente, presentare un algoritmo che nel minor tempo possibile determini il mediano dei 2n elementi. Calcolare la complessità dell'algoritmo presentato.
Dell’algoritmo presentato :
- si dia una spiegazione a parole;
- si dettagli il tipo di strutture dati adoperate;
- si fornisca l’implementazione in linguaggio C;
- si valuti la complessità computazionale.
SCRITTO 19/7/1999
Un algoritmo di ordinamento si dice stabile se elementi con lo stesso valore compaiono nel vettore di output nello stesso ordine in cui compaiono in quello di input.
Mostrare, con un esempio, che l’algoritmo heapsort, così com'è presentato nel testo, non è stabile.
Modificare l’algoritmo heapsort in modo da garantire la stabilità.
Dell’algoritmo presentato:
- si dia una spiegazione a parole;
- si dettagli il tipo di strutture dati adoperate;
- si fornisca l’ implementazione in linguaggio C;
- si valuti la complessita’ computazionale.
SCRITTO 28/6/1999
Il codice di Prufer di un albero di n nodi, etichettato da 1 a n, e’ una sequenza di lunghezza (n - 2) costruita con il seguente processo sequenziale:
per 1 ² i ² n - 2 inserire nella i-esima posizione della sequenza l’etichetta dell’adiacente del più piccolo fra i nodi di grado 1 rimanenti e poi cancellare tale nodo.
Descrivere un algoritmo che, dato in input un codice di Prufer di lunghezza (n - 2) generi l’albero etichettato con n nodi ad esso associato.
Dell’algoritmo presentato :
- si dia una spiegazione a parole;
- si dettagli il tipo di strutture dati adoperate;
- si fornisca l’ implementazione in linguaggio C;
- si valuti la complessità computazionale.
SCRITTO 22/2/1999
Un grafo G = (V,E) si dice bipartito se è possibile partizionare V in due sottoinsiemi V1, V2 tali che:
V1 unito a V2 = V;
V1 intersecato a V2 = ø;
ciascuno spigolo in E unisce due vertici in sottoinsiemi diversi.
Descrivere un algoritmo che verifichi se un dato grafo G è bipartito o no e, in caso di risposta affermativa, determini una bipartizione dello stesso. Si assuma che il grafo G sia rappresentato tramite matrice di adiacenza.
Dimostrazione che se il grafo G è un albero, allora è sempre bipartito.
Descrivere un algoritmo che, dato in input un albero binario determini una bipartizione dello stesso. Si supponga l’albero rappresentato con una struttura dati di tipo liste di records dove ogni record è costituito da tre campi, uno contenente il nome del nodo corrente e gli altri due contenenti il puntatore al figlio sinistro e il puntatore al figlio destro, rispettivamente.
Per ciascuno degli algoritmi presentati, si deve:
- darne una spiegazione a parole;
- fornirne una implementazione in linguaggio C;
- valutare la complessità computazionale.
SCRITTO 1/2/1999
Siano dati k vettori di interi V1, V2, ..., Vk, di dimensioni n1, n2, ..., nk, rispettivamente. Ciascuno vettore Vi, 1² i ² k, sia ordinato in modo crescente.
Descrivere a parole un algoritmo che, sfruttando tutte le proprietà dell’input, fonda i vettori V1, V2, ..., Vk in un unico vettore V di dimensione n = n1+n2+...+nk, ordinato in modo crescente.
Calcolare la complessità computazionale dell’algoritmo presentato.
Implementare l’algoritmo presentato in linguaggio C, fissando k=10 e n1+n2+...+nk = 100.000.000.000 ed adoperando solo strutture dati ad accesso diretto.
Fornire una implementazione dello stesso algoritmo con una grande quantità di strutture dati ad accesso sequenziale. Sottolineare, se ce ne sono, i vantaggi forniti da questa seconda realizzazione
SCRITTO 18/1/1999
Si può ordinare un insieme di n numeri distinti inserendoli uno alla volta in un albero binario di ricerca, ed elencando successivamente i numeri con una visita in ordine simmetrico dell'albero.
Quali sono i tempi di esecuzione di questo algoritmo nel caso migliore e nel caso peggiore?
Implementare in linguaggio C una versione ricorsiva ed una iterativa di questo algoritmo.
SCRITTO 12/1/2001
Proporre un algoritmo che trovi l'elemento minimo fra gli n memorizzati in una coda di priorità massima rappresentata tramite un vettore di n elementi.
Implementare in linguaggio C l'algoritmo proposto.
Trasformare il programma proposto dopo aver cambiato la rappresentazione dell'heap da vettore a lista a tre campi.
Calcolare la complessità computazionale dell'algoritmo proposto.
SCRITTO 2/2/2001
Dato un albero T(V,E) con n vertici, si definisce centroide un vertice v di V, di grado d(v), la cui rimozione genera una foresta di d(v) alberi ciascuno dei quali contiene al più n/2 vertici. In ogni albero esiste almeno un centroide.
Dato in input un albero binario T rappresentato tramite liste a tre campi, proporre un algoritmo per trovare un centroide.
Implementare in linguaggio C l'algoritmo proposto.
Trasformare il programma proposto dopo aver cambiato la rappresentazione dell'albero da liste a vettore di archi.
Calcolare la complessità computazionale dell'algoritmo proposto.
SCRITTO 1/6/1999
Un grafo G = (V,E) si dice bipartito se è possibile partizionare V in due sottoinsiemi V1, V2 tali che:
V1 unito a V2 = V;
V1 intersecato con V2 = ø;
ciascuno spigolo in E unisce due vertici in sottoinsiemi diversi.
Se il grafo G è un albero, allora è sempre bipartito.
Descrivere un algoritmo che, dato in input un albero binario rappresentato in forma vettoriale, determi una bipartizione dello stesso.
Descrivere un algoritmo che, dato in input un albero qualunque determini una bipartizione dello stesso. L’albero sia rappresentato come lista di records, dove ogni record è costituito da tre campi, uno contenente il nome del nodo corrente e gli altri due contenenti, rispettivamente, il puntatore al figlio più a sinistra (se esiste) e il puntatore al fratello immediatamente alla sua destra (se esiste).
Per ciascuno degli algoritmi presentati, si deve:
- darne una spiegazione a parole;
- fornirne una implementazione in linguaggio C;
- valutare la complessità computazionale.
SCRITTO 19/4/1999
Il codice di Prufer di un albero etichettato con n nodi è una sequenza di lunghezza (n - 2) costruita con il seguente processo sequenziale:
per 1 ² i ² n - 2 inserire nella i-esima posizione della sequenza l’etichetta del padre della più piccola fra le foglie rimanenti e poi cancellare la foglia.
Descrivere un algoritmo che, dato in input un albero etichettato con n nodi, generi il codice di Prufer ad esso associato.
Dell’algoritmo presentato :
- si dia una spiegazione a parole;
- si dettagli il tipo di strutture dati adoperate;
- si fornisca l’ implementazione in linguaggio C;
- si valuti la complessita’ computazionale.
SCRITTO 7/7/2000
Date in input due stinghe rispettivamente rappresentazioni in modo inordine e preordine dello stesso albero T, progettare uno algoritmo che dia in output l'albero T rappresentato tramite liste a tre campi.
Dell'algoritmo presentato:
- si dia la spiegazione a parole;
- si fornisca l'implementazione in linguaggio C;
- si valuti la complessità computazionale.