Esercizio 1. (9 punti) Data una lista $L$ di $n$ interi, determinare l'ordine di complessità $T(n)$ della seguente funzione Pascal con parametri d'ingresso $L$, $n$:

function f( L : LIST; n : integer ) : integer; 
var i, c : integer; 
    P : LIST;
begin 
if (n = 0) then f := 1
else begin
     c := 0;
     P := L;
     for i := 1 to n do
         begin
         c := c + P^.elem;
         P := P^.next;
         end;
     f := c + f( L, (3*n) div 5 ) * f( L, (2*n) div 5 )
     end 
end.

Esercizio 2. (9 punti) Mostrare l'esecuzione dell'algoritmo Bucket Sort con le seguenti chiavi in ingresso: .34, .15, .56, .27, .77, .312, .123, .546, .1111, .10235, .7329, .5009.

Esercizio 3. (12 punti) Dato un grafo non orientato $G\; =\; (V,\; E)$, si vuole individuare una catena di lunghezza almeno $k\; >\; 0$. Una catena è una sequenza di vertici connessi, dove ciascun vertice ha grado esattamente due. La lunghezza di una catena è il numero di vertici in essa contenuti. Assumendo che il grafo sia rappresentato con liste di adiacenza:

1. Scrivere una funzione booleana in Pascal o pseudocodice, con parametri di ingresso $k$ e $G$, che restituisca true se e solo se $G$ contiene una catena di lunghezza almeno $k$.
2. Valutare e motivare la complessità asintotica della soluzione proposta.