PARTE I

function F ( T: AlberoBinario ) : integer; 
begin 
  if (T = NIL) 
     then F := 1
     else F := Chiave(T) * F( FiglioSinistro(T) ) 
               + F( FiglioDestro(T) ) * F( FiglioDestro(T) )
end;

1. Determinare l'ordine di complessità $C(n)$ della funzione F, dove $n$ è il numero totale di nodi dell'albero T.
2. Scrivere una diversa versione della funzione F che restituisca lo stesso valore, ma abbia un ordine di complessità provatamente inferiore. Fornire la relativa analisi di complessità.

Esercizio 2. (7 punti) Scrivere una funzione Pascal che, data una lista di interi, ne produca in uscita una copia. Si adotti la seguente definizione di lista:

type LISTA = ^Nodo;
     Nodo  = record
                 elem : Integer ;
                 next : LISTA
             end;

PARTE II

• FIND-MIN($Q$) : restituisce la chiave minima nella coda $Q$.
• EXTRACT-MIN($Q$): cancella la chiave minima dalla coda $Q$.
• INSERT($k,\; Q$) : inserisce la chiave $k$ nella coda $Q$.

Si vuole realizzare tale tipo di dato mediante le seguenti quattro strutture dati:

1. albero AVL;
2. heap;
3. lista bidirezionale;
4. vettore ordinato.

Riempire la seguente tabella con la complessità asintotica delle operazioni suddette realizzate con le quattro strutture dati:

Esercizio 4. (8 punti) Dato un grafo non orientato $G\; =\; (V,\; E)$ rappresentato con liste di adiacenza, si deve verificare se $G$ è un albero.

1. Descrivere brevemente a parole la struttura di un algoritmo efficiente per risolvere tale problema.
2. Realizzare tale algoritmo sotto forma di funzione booleana in Pascal o pseudocodice, con parametro di ingresso $G$.
3. Valutare e motivare la complessità asintotica della soluzione proposta.

SOLUZIONI

Soluzione dell'esercizio 1.

1. L'equazione di ricorrenza è data da:
   la cui soluzione secondo il teorema master (caso 1 con $a=3$, $b=2$ e $f(n)\; =\; O(1)$) è

   $C(n)\; =\; O(nlog$₂ 3) = O(n^{1.58 ...}).

2. Evitiamo una doppia chiamata ricorsiva sostituendo

        else F := Chiave(T) * F( FiglioSinistro(T) ) 
                  + F( FiglioDestro(T) ) * F( FiglioDestro(T) )

   con le seguenti istruzioni (e dopo aver dichiarato la variabile intera X)

        else begin
             X := F( FiglioDestro(T) );
             F := Chiave(T) * F( FiglioSinistro(T) ) +  X * X
             end

   Di conseguenza, l'equazione di ricorrenza diventa

   la cui soluzione è

   $C(n)\; =\; O(n).$

Soluzione dell'esercizio 2.

function COPIA ( L : LISTA ) : LISTA;
var P : LISTA;
begin
   if (L = NIL) then COPIA := NIL
   else begin
        new(P);
        P^.elem := L^.elem;
        P^.next := COPIA( L^.next );
        COPIA := P
        end
end;

Soluzione dell'esercizio 3.

Soluzione dell'esercizio 4.

1. Tra i vari approcci, usiamo quello basato sul Teorema 5.2 del libro di testo [Cormen-Leiserson-Rivest]: un grafo $G\; =\; (V,E)$ è un albero se e solo se $G$ è connesso e il numero di archi è pari al numero di vertici meno uno.
2. Usiamo una funzione ausiliare Dim(L) che restituisce la lunghezza di una lista L.

   IsAlbero( G )                           // G = grafo non vuoto
   1. foreach u in V do colore[u] := bianco     
   2. DFS-VISIT( u )                            // u = vertice arbitrario
   3. connesso := true; NumArchi := NumVertici := 0
   4. foreach u in V do 
   5.         connesso   := connesso and (colore[u] = nero) 
   6.         NumVertici := NumVertici + 1
   7.         NumArchi   := NumArchi + Dim( ListaAdiacenza(u) )
   8. NumArchi := NumArchi / 2
   9. return ( connesso and (NumArchi = NumVertici-1) )

3. L'algoritmo richiede tempo lineare $O(|V|\; +\; |E|)$ in quanto i vertici e gli archi sono esaminati un numero costante di volte. In particolare, la scansione delle liste di adiacenza richiede $O(|E|)$ tempo.