Esercizio 1

Esercizio

2 i=i*2)j=j*2)

SoluzioneIl frammento è composto da due parti quasi identiche. L’unica differenza è il modo in cui crescono i contatori. Nella prima parte la crescita è lineare mentre nella seconda èesponenziale. Questo significa che, ai fini della complessità asintotica, il primo blocco di cicli dominerà il secondo che può, quindi, essere ignorato. Il primo blocco presenta due cicli annidati e il numero di iterazioni del ciclo più interno è determinato dal crescere del contatore del ciclo più esterno. In particolare quando viene (1) per la prima volta, (2) esegue 2n cicli. Alla seconda esecuzione di (1), (2) esegue 2n-1 cicli. Perciò quando(1) avrà eseguito n cicli, (1) e (2) in totale avranno eseguito

Esercizio 2

Soluzione

Esercizio 3

Soluzione

Esercizio 4

• Dato un albero binario, definiamo altezza minimale di un nodo v la minima distanza di v da una delle foglie del suo sottoalbero, definiamo invece altezza massimale di un nodo v la massima distanza di v da una delle foglie del suo sottoalbero. 

• Supponiamo di avere un albero T che contiene in ogni nodo anche un numero intero m.

• Diciamo che l’albero è k‐equilibrato se tutti i nodi (eccetto al più k) contengono un valore m che è compreso tra l’altezza minimale e l’altezza massimale del nodo stesso.

• Definire un algoritmo che riceve in input l’albero T e un intero k e restituisce vero se l’albero T è k‐equilibrato, falso altrimenti.

• Calcolare la complessità dell’algoritmo proposto.

int maxheight ( tree t ) {int D, S;if (t == NULL)return 0;S = maxheigth( t‐>left );D = maxheigth( t‐>right );if ( S > D )return S + 1;

elsereturn D + 1;

}

int minheight ( tree t ) {int D, S;if (t == NULL)return 0;S = minheigth( t‐>left );D = minheigth( t‐>right );if(S==0)

return D+1;if(D==0)

return S+1;if ( S < D )

return S + 1;elsereturn D + 1;

}

int contaEcc ( tree t ) {int n=0;if(t‐>valore > maxheigth( t ) || t‐>valore < minheigth( t ))

n++;n+=contEcc(t‐>left);n+=contEcc(t‐>right);return n;}

int kequilibrato(tree t,int k) {if(contaEcc(t)<=k)

return 1;return 0;

}

int contaEcc ( tree t,int M,int m ) {int n=0;if(t‐>valore > M || t‐>valore < m )

n++;n+=contEcc(t‐>left,M‐1,m‐1);n+=contEcc(t‐>right,M‐1,m‐1);return n;}

int kequilibrato(tree t,int k) {int M,m;M= maxheigth( t ); m=minheigth( t ))if(contaEcc(t,M,m)<=k)

return 1;return 0;

}

Esercizio 5

• Costruire l'albero di Huffman necessario per codificare la seguente frase: “a nice way of encoding”

Esercizio 6

• Determinare la complessità computazionale del seguente frammento di codice C in funzione della lunghezza della stringa A

int foo(char A[], int k, int m) {

int i, a=0;

if (k>=m) 

return 0; 

for(i=k; i<m; i++) 

a+=A[i]; 

return a + foo(A, k*2, m/2);

}

int bar(char A[]) {  

return foo(A,1,strlen(A)); 

}

Esercizio 

• Determinare i bound di complessità asintotica più stretti per la seguente ricorrenza: T(n) = 4T(n/3) + n5

• T(n) = 4T(n/3) + n5 = 4 (4T(n/9) + (n/3)5) + n5

• (4 (4T(n/27) + 4*(n/9)5) + (n/3)5) + n5

Esercizio 8

• Si consideri un array bidimensionale A di m righe e n colonne, in cui ogni riga è ordinata in ordine crescente. Descrivere un algoritmo in grado di riunire le m righe di A in un unico array ordinato B di nmelementi in tempo O(n m log m)

• Suggerimento:mantenere il primo elemento non ancora copiato in B di ciascuna riga in uno heap H di m elementi

Esercizio 9

• Sia dato un array A di n elementi interi. Sia dato un algoritmo che esegue in sequenza le due operazioni:

Inserisci(i,x): assegna il valore x all’elemento A[i];

Somma(l,m): calcola la somma degli elementi di A con indice compreso tra l e m.

• La prima operazione ha costo costante, mentre la seconda, nel caso peggiore, ha un costo O(n). 

• Si discuta come l’uso di una struttura dati aggiuntiva permette di ridurre la complessità dell’algoritmo a O(log n). Data l’organizzazione dei dati individuata, si definisca in pseudocodice la specifica delle due operazioni di inserimento e di somma e se ne discuta la complessità.

33

16 17

11                  5                    7   10

4  7        2         3        2          5 6        4

Esercizio 10

• Si risolva l'equazione ricorsiva T(n) = 2T(n/3) + n4

• Si specifichi in pseudocodice un’ipotetica funzione foo che abbia una complessità pari all’equazione ricorsiva (non è necessario che la funzione faccia qualcosa di significativo).

• Si proponga una macchina RAM che abbia una complessità pari all’equazione ricorsiva (non è necessario che la macchina faccia qualcosa di significativo).

Esercizio 11

• Si consideri il seguente problema:

• Data una n‐pla di numeri interi a1, a2, . . . , an, n ≥ 1 si calcoli la somma a1 + a2 + ∙ ∙ ∙ + an.

a) Descrivere ad alto livello una procedura per risolvere il problema.

b) Assumendo il criterio di costo uniforme, determinare l’ordine di grandezza del tempo di calcolo e dello spazio di memoria richiesti dalla procedura in funzione di n. 

c) Supponendo che ogni ai sia un intero di k bit, e assumendo il criterio di costo logaritmico, determinare l’ordine di grandezza del tempo e dello spazio richiesti dalla procedura in funzione dei parametri n e k. 

Esercizio 12

• Dato un grafo diretto rappresentato mediante liste di adiacenza, per ogni nodo v si vuole calcolare il numero dei nodi raggiungibili da v (ovvero il numero dei nodi w per i quali esiste un cammino orientato da v a w).

a) Definire un algoritmo che risolva il precedente problema;

b) Discutere la complessità dell’algoritmo definito.

foo(vett,v,visitati)

visitati.add(v);

cont=0;

for(n in vett)

if(n.nodo==v)

lis=n.lista;

for(m in lis)

if(notin(visitati,m))

cont++;

cont=cont+foo(vett,m);

return cont;

notin(visitati,m)…………………………….

Esercizio 13

• Una società deve progettare un sistema informativo per gestire i propri progetti. Ogni progetto ha una scadenza ed è composto da diversi task. Ogni task ha una durata e un numero di persone associato. Alcuni task hanno delle dipendenze: ad esempio nel progetto P1 non posso completare il task T3 se non ho completato prima il task T1.

1) Si progetti una struttura dati per rappresentare le informazioni e si progetti un algoritmo che assegna ad ogni progetto una data d'inizio limite oltre cui non sarà possibile iniziare il progetto.

2) Si implementi anche un algoritmo che calcoli quante persone sono necessarie per eseguire tutti i task nel momento in cui c'è il maggior numero di risorse richieste.

Esercizio 14

• Si consideri la seguente definizione di un albero binario in un linguaggio C‐like:struct ET { int dato;

struct ET * left, right; } treeNode;typedef treeNode * tree;

• Definiamo grado di un livello di un albero la somma degli elementi appartenenti al livello stesso.

• Una coppia di alberi t1 e t2 si dice k‐similare se esistono almeno klivelli in t1 e in t2 di pari grado.

• Nota: non è necessario che i livelli di pari grado siano lo stesso livello nei due alberi.

• Si codifichi, in pseudocodice o in un linguaggio di programmazione a scelta, la funzione int ksimilare(tree t1, tree t2, int k)che restituisce 1 se t1 e t2 sono k‐similari, 0 altrimenti.

struct ET { int dato;struct ET * left, right; } treeNode;

int f(tree t1, tree t2) { int profondita1=depth(t1);int v1[]=malloc(sizeof(int)*profondita1);int profondita2=depth(t2);int v2[]=malloc(sizeof(int)*profondita2);

…………………………….f2(t1,v1,0);     f2(t2,v2,0);

……………………………………}void f2(tree t,int v[],int liv)

v[liv]+=t‐>dato;f2(t1‐>left,v1,liv+1);f2(t1‐>right,v1,liv+1); 

Esercizio 15

• Dati due insiemi di interi A={a1, a2, …, an} e B={b1, b2, …, bm}, sia C la loro intersezione, ovvero l’insieme degli elementi contenuti sia in Ache in B.

• Quale è la complessità minima di un algoritmo che calcola C? Spiegare come funzionerebbe.

Esercizio 16

• L’algoritmo Insertion‐Sort può essere espresso come una procedura ricorsiva nel modo seguente: per ordinare A[1], …, A[n] si ordinano  in modo ricorsivo i primi n‐1 elementi A[1], …A[ n − 1] e poi si inserisce A[n] nell’array ordinato A[1], …, A[n − 1]

• Scrivere una ricorrenza che esprima il tempo di esecuzione di questa versione ricorsiva di Insertion‐Sort

• T(n)=T(n‐1)+n‐1

Esercizio 17

Soluzione

Esercizio 18

Soluzione

Esercizio 19

Soluzione

Esercizio 20

Soluzione

Esercizio 21

Soluzione

Esercizio 22

Soluzione

Esercizio 23

Soluzione

Esercizio 24

Soluzione

Esercizio 25

Soluzione

Esercizio 26

Soluzione

Esercizio 27

• Si consideri il problema di restituire, dato in ingresso un albero binario T contenente numeri interi, la radice del sottoalbero  S di  T la cui somma degli elementi è massima (tale cioè per cui non esiste nessun altro sottoalbero di T la cui somma dei valori è maggiore di quella degli elementi di S)

• Scrivere in pesudocodice un algoritmo che risolve il problema desiderato, e darne la complessità

Soluzione