Prova di Algoritmi e Strutture Dati

Non si possono consultare uè appunti ne testi

20 Settembre 2022

Esercizio l Calcolare il limite supcriore alla complessità, in tempo dei seguenti algoritmi:

1 Test l (n : int):int; 1 Test 2(n: int):int;

2 if n > 1 then 2 a := 0;
3 n := n — 5; 3 while n > '2 do
4 return 5 * Testl(n); 4 L n:=[jj;a:=a+l;
5 else 5 while a > l do
6 [_ return 0 6 b := a;
7 while o > l do
8 L o :=&-i;
9 a := a— l;

Esercizio 2 Dati due array A e B della stessa dimensione n che memorizzano interi, trovare se
A c B soiio uno una, permutazione dcll'altro.

• Descrivere l'algoritmo a parole e dare lo pseudocodicc

• Studiare la complessità in tempo della soluzione proposta

Esercizio 3 Dato un grafo G = (V, E) non orientato, trovare le componenti connesse ed associare
ad ogni vertice V l'etichetta che identifica la componente connessa a cui il vertice appartiene.

• Dare lo pseudocodice dell'algoritino che risolve il probleina

• Studiare la complessità in tempo della soluzione proposta

Esercizio 4 (Facoltativo) Dato un min-heap H realizzato con albero binario che memorizza
interi, e dato un intero k, trovare e marcare tutte le chiavi in H minori od uguali a k.

• Dare lo pseudocodice dell'algoritmo che risolve il problema

• Studiare la complessità in tempo della soluzione proposta.
• C'è una relazione fra il rango di k m H e la complessità dell'algoritmo?
es <
T&y^- 4
~rC^-^) -^ 0^3 ^ ^ z
-t~Cn^» =
O(^) ^v^ è- ^

A€^ cAjJJL-s, \f~i (:>^-^ O l<j?

^) ? TCn)
TC/u; e 0^)
0^) O T^-s-3
<

oC±) O

3 cyo 3 /no >o : ¥ A^^ Do '^Tv^) ^ ^H

t-l^ rv^, ~T^ - S^^ ^ (O ^ ^ ^-
"KI- ^TC/U) ^ c^-<s-)-t oC^;-CLn" ^-^of<)
^ C^^-^> - 5-C^OC<.) ^
C fe oC-L;
Lo. ^t^ C<^o L.^ C ^^ ^7^-^-3 <-^T(^J
T^ (»-)
^v^-e S-^ (pl^^
^ Vi " ®:
) ^ofz.V
-£ O
^
K

^,A -^Z^ ^ •z.

.^^ ^-^
a^/(
£L^-< ^?
-&^10' ^^ ^
f^^so^r^) ^^
t^n^5~o/2-r (^ 8^± ^
w-^.A ^ ^^) ^L (ft^ ^ fc^]) y^
A ^r +
^^ ^ ^. m. H^ (('<<JON ^ U\JA jF^h^T^-?no^.^
X^< l(^/0^-^ ^^.^.^TAÀOf^-cv
~^)
of^< ^^^ }
N^^ <yi POON c)<.A^LE GOU/U-T?A/-^ ^o/ZT~ ^e^^ ^C--eJl^. <^<
A^-c^ ^JLo rVL I^LO 9--7M^ GÈ- (A- Co ( ^-A»2-'YV/^'0
^a^^G-E
s^ us ^ <2ou^T7^c soa^ ^o^^^^.'^
^^' VT^C^^ , 1 u
dL.U<^^ ^lo^
^S^c^'/K- '^> Assot-^-3 CW ^-- ^<o<o^
DF$ (G ^C^^^} OJK^O^Q^ ^ Cjerf^-^p-?
ec ^- i c^^c^^ t<^,c"^.
J^ i^-^ ^ \\1{ ^ l^n.^ ^ °^' ^h^^^
cc^ ^^c^V^
-^ c^ ^ -"- r^<:-^?
^ /,^ * ^ NI ov~
^i Oc^Z ^)Cc
- ^^bl
^r^
tì^
t>^-^-v<^fc (G^^;°<-;
t)P$> ^^^ ^ [G, ^) cc )
ù^^i^^^^^^ '
V M-é A^T^^
'^' _c^ = .0^ y^
(U-)
(\ ^ \ Cc^-<fc> (T^^ c<^
7r (v^.^.\ f&.r--, ^}
^>ps>- Art 9'< ^ LM:7^ "' ; " ~-y
L-

^ ) <- t^oO^ ;
^^-^•o 4 ^^o^^kv»;
-^ v<So-G)^ ( ^\joco\^o^ ,^_ ^^o^oY^^ c-^^c^
<^0^ ^3Cn^a-\v^ -^Vv-^.' /i- )<1 ^
i ^'9-^ cW^o^^v VT^

o^c^^- C^^C/\ ( ^:A^^^r ^^^u) c.^-^^ ^-^^

,/i'^ -h F^/v,o ( ^ CÀ^ o^ve-
^\ ^ ^ '^ v <? 4^ /u- \
Ce^c^ ^ 2' i^^-o^a^^^ , Vv.<L
.>

/1 :(- 2. ^ •)^rh^ ^ -i ^ ry^ fcC^-k

C^^CA (^^ ^. U^'Ys^ ^ (/ CU--^ -^^
^

u^-v^w~^)
fV<6[-|p -^te ^' .-^-^/^^k' /^A "^ r^t^^Q^
O U^u^O^' 0^ ^ ^- ^0~ -^LQ^J^^^-GU ^lu.
c»
c?L' '^AI //^jocLt° cL^ ./^o^^ > ki

A k ^
2 ^ , VvoJL.- ^A^-^' ^^^-^
-^ ÀO ^ VcA^-' /^- ^-b^-
o V3<2

/ (-o.^. J^' //y^c^ (VT:^-^)^'

^ ^^JCTG^' A^— ^^ A^c
^ ^^—- ^ -^ ^ ^^^ ^^^^ ^^^^ ^^ ^J^
; ^ T- <^^ ^ 0^ (^^^<^/ ^-' ^ •
^ .. l. -
o >^ °^ ^°/^° 0^. ^ ^ ^
fi, ^^^. ^
^ °^. ^ ^ ^ ^~° c^
o
^ vuo^U ^^U^ ^ S^^^ J^
^ (^) ^ fTQ^^O ^
 rrova ai Algoritmi e Strutture Uati
Non si possono consultare ne appunti ne testi
11 Gennaio 2023 - A

Esercizio l Ordinare le seguenti funzioni in ordine di grandezza:

n2;(^n)3;410sisn;n2/3
Esercizio 2 Calcolare il limite superiore alla coinplessità in tempo dei seguenti algoritmi.

1 Test l; int t :== log^n; 1 Test3(A : array of int, s, f: int)

2 while t > l do 2 int i := s;
3 L^=!; 3 int a := l;
4 while i </ do
5 if A[i] < 0 then
1 Test 2; int t := l; 6 a := a * A[i]; i := i +1;
2 while t < n do 7 else

3 ^t:=t+5 8 L i := 4z

Esercizio 3 Chiamata n la dimefìsione dell'array, stimare il limite superiore alla complessità in

tempo dell' algoritmo Pippo usando il Master Theorem.

1 Pippo(A : array of int, s, e: int):int

2 if (e-s+ 1) ^ 10 then
3 int a := s;
4 while a < e do
5 |_ a := a+1
6 return a
7 else
8 mtg:=5+LR^J;
9 return 2*Pippo(A, s, g — l)

Esercizio 4 Dato un array A di dimensione n che contiene caratteri maiuscoli seguiti da cifre
comprese fra O e 9, trovare quanti caratteri sono memorizzati in A.
• Descrivere l'algoritmo a parole e dare lo pseudocodice
• Studiare la complessità in tempo della soluzione proposta.
• Discutere l'ottimalità. della soluzione proposta
Esempio di istanza: Array A di dimensione n = 12,
B\U\0\N \A\N\N \0\2\0\2\3
Output = 8
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
11 Gennaio 2023 - B

Esercizio l Ordinare le seguenti funzioni in ordine di grandezza:

2I062l°g2";(^);4Iog2";n2/3

Esercizio 2 Calcolare il limite superiore alla complessità in tempo dei seguenti algoritmi.

1 Test l; i Test3(A : array of int, s, f: int)

2 int t := n; 2 int i := s;
3 while t > l do 3 int a := l;
4 L<-!; 4 while z < / do
5 if A [t] < 0 then
6 a := a* A[i]; i := 2i;
1 Test 2; 7 else
2 int t := i/n; 8 L-=/
3 while t > l do
4 L A:= i-5

Esercizio 3 Chiamata n la dimensione dell'array, stimare il limite superiore alla complessità in

tempo dell' algoritmo Pippo usando il Master Theorem.

<1
1 Pippo(A : array of int, s, e: int):int
2 if (e-s+1) > 3 then
• 3 int q:=s+ Le=j±iJ;
4 return
Pippo(A, s, g - l)*Pippo(A, s, 7-1)

Esercizio 4 Dato un array A ordinato di dimensione n che contiene n interi compresi tra O e
n — l con una sola ripetizione, trovare il carattere ripetuto in A.
• Descrivere l'algoritmo a. parole e dare lo pseudocodice
• Studiare la complessità in tempo della soluzione proposta
• Discutere l'ottimalità della soluzione proposta
Esempio di istanza: Array A di dimensione n = 12,
l l 2| 3|4|5 |5|6 [7|8 |9| 10[ 11
Output 5
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
7 Febbraio 2023

Esercizio l Calcolare il limite superiore alla complessità in tempo del seguente algoritmo.
1 Test 2(/n: int):int;
2 if n > 15 then
3 int c := 0;
4 t := n;
5 while i > O do
6 [_ c++;i--
7 Test2:- Test2([^J)+2n2;
s else
9 [_ Test2:= 6

Esercizio 2 Dato un array A, progettare un algoritmo in piace per capovolgere A.

• Darò lo pseudocodice della soluzione proposta

• Studiare la complessità in tempo della soluzione proposta

• Discutere l'ottimalità della soluzione proposta

Esempio: Input A=26 3 5 4

Output A=45 3 6 2

Esercizio 3 Dato un array A ordinato ed un intero x, trovare la somnia degli elementi in A

uguali ad x.

• Descrivere l'algoritmo a parole

• Darò lo pseudocodice della soluzione proposta

• Studiare la complessità in tempo della soluzione proposta
• Discutere l'ottimalità della soluzione proposta

Esercizio 4 Dato un grafo G = (V, E) orientato, visitare il grafo in profondità e restituire il tipo
di ogni arco in G.

• Descrivere l'algoritmo a parole

• Darò lo pseudocodice della soluzione proposta

• Studiare la complessità in tempo della soluzione proposta

 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi

21 Gennaio 2020

Esercizio l. Dato un testo T, sì vogliono sostituire i caratteri che appaiono in esso con una codifica tale
da minimizzare la lunghezza del testo T dopo la codifica. Descrivere uii algoritmo che restituisce la
codifica da sostiture a ciascun carattere in T. Descrivere la complessità dell'algoritmo di codifica.
Motivare perché l'algoritmo proposto minimizza la dimensioiie del testo T dopo la compressione.
Esercizio 2. Dato un grafo non orientate G =- (V, E) connesso e aciclico, si vogliono etichettare i vertici
in V in modo che gli estremi di ogni arco siano assegnati a due etichette diverse. Descrivere un algo-
ritmo che risolve il problema c darne lo pseudocodicc. Quante etichette sono utilizzate dall'algoritmo
proposto? Il grafo G c un albero? Studiare la complessità in tempo dell'algoritmo proposto.
Esercizio 3. Dato un grafo G = (V, E) diretto e pesato w : E —i- N+, data una sorgente s £ V, trovare il
vertice u tale che il canimino da s a u sia quello di peso d[s, u) miiiimo in C?. Descrivere un algoritmo
che risolve il problema e darne lo pseudocodice. Studiare la complessità dell'algoritmo proposto.

Esercizio 4 Calcolare la complessità in tempo dei seguenti algoritmi:

1 Test; int s := n; a:= l; t :=0 1 Pippo(n : int) : int

2 while s > l do 2 if n < 3 then
• 3 \_ S := L|J;a++ 3 return 1
4 else
4 for'c= l;ì++;2ado
5 \_t :=2+t • 5 3 := l;
6 while j < n do
7 i 3^= 3+2
8 return Pippo (^) . Pippo (^) + ^n
 Prova di Algoritmi e Strutture Dati
Non si possono consiiltare ne appunti ne testi

21 Gennaio 2020

Esercizio l. Dato uii testo T, si vogliono sostituire i caratteri che appaiono in esso coli mia codifica tale
da minimizzare la lunghezza del testo T dopo la codifica. Descrivere un algoritmo che restituisce la
codifica da sostiture a ciascun carattere in T. Descrivere la complessità dell'algoritmo di codifica.
Motivare perché l'algoritmo proposto miiiimizza la dimensioiie del testo T dopo la compressione.
Esercizio 2. Dato un grafo non orientato G == {V, E) connesso e aciclico, si vogliono etichettare i vertici
in V in modo che gli estremi di ogni arco siano assegnati a due etichette diverse. Descrivere iin algo-
ritmo che risolve il problema c danic lo pseudocodicc. Quante etichette sono utilizzate dall'algoritmo
proposto? Il grafo G c un albero? Studiare la complessità in tempo dell'algoritmo proposto.
Esercizio 3. Dato un grafo G = {V., E) diretto e pesato w : -B —> N+, data una sorgente s € V, trovare il
vertice u tale che il cammiiio da s a u sia quello di peso d(s, u) minimo in G. Descrivere un algoritmo
che risolve il problema e darne lo pseudocodice. Studiare la complessità dell'algoritmo proposto.
Esercizio 4 Calcolare la complessità in tempo dei seguenti algoritmi:

1 Test; int s := n; a :=• l; t := O 1 Pippo(n : int) : int

2 while è > l do 2 if n < 3 then
• 3 |_ A' := L|J;a++ 3 return 1
4 else
4 for i := l:i++;2a do
5 \^f.=2+t 5 J :-1;
6 while j < n do
7 ÌJ:=J+2
8 return Pippo (^) . Pippo (^) + ^fn
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi

21 Gennaio 2020

Esercizio l. Dato un testo T, si vogliono sostituire i caratteri che appaiono in esso con una codifica tale
da minimizzare la lunghezza del testo T dopo la codifica. Descrivere un algoritmo che restituisce la
codifica da sostiture a ciascun carattere in T. Descrivere la complessità dell'algoritmo di codifica.
Motivare perché l'algoritmo proposto minimizza la dimensione del testo T dopo la compressione.

Esercizio 2. Dato un grafo non orientato G =- (l/, -E) connesso e aciclico, si vogliono etichettare i vertici
in V in modo che gli estremi di ogni arco siano assegnati a due etichette diverse. Descrivere un algo-
ritmo che risolve il problema c darne lo pseudocodicc. Quante etichette sono utilizzate dall'algoritmo
proposto? Il grafo C? è un albero? Studiare la complessità in tempo dell'algoritmo proposto.

Esercizio 3. Dato un grafo G = (V, E} diretto e pesato w : E -^ N+, data mia sorgente s £ V, trovare il
vertice u tale che il cammino da s a u sia quello di peso d(s, u) minimo in G'. Descrivere un algoritmo
che risolve il problema e darne lo pseudocodice. Studiare la complessità dell'algoritmo proposto.
Esercizio 4 Calcolare la complessità in tempo dei seguenti algoritmi:

1 Test; int s := n; a:= l; t :•• o 1 Pippo(n : int) : int

2 while ,s > l do 2 if n < 3 then
3 [_ A':= L|J;a++ 3 I return 1
4 for i := l;i++;2a do 4 else

5 \^t:=2+t 5 3 ••= l;
6 while j < n do
7 L ^' :=^' +2
8 return Pippo (^.) • Pippo (^) + v/n
 C* °LktL L@#%^tÈ^Q.!.OLkli= L@@° ^R*.ó-LD®°ùS • E@HO<? ó^ «v LV O - l-3^Lvii^L© (O

Prova di Algoritmi e Strutture Dati II

Non. si possono consultare ne appunti ne testi
II Appello Straordiiiario + II Esonero A.A: 2009-2010
12 Maggio 2010

Esercizio l. (punti 11) Nella città della Perquisizione, vi sono n postazioni, connesse fra loro da
un insieme E di vie. Ciascuna via è caratterizzata da un proprio verso di circolazione e da una
data lunghezza. Fra le postazioni, vi sono ni posti di blocchi, che si possono attraversare
solo accettando di essere perqusiti e n.s postazioni libere. Nota bene, se si arriva o si parte da
un posto di blocco non si è perquisiti, ma se si arriva, e si riparte dallo stesso posto di blocco
(ossia, se lo si attraversa) si è perquisiti, I cittadiiii della città della Perquisizione vogliono
trovare, per ogni coppia di postazioni (i.j), un camniino da. i a. j che sia percorribile senza
incorrere in perquisizioni (Se tale calumino non esiste, l'algoritnio restituirà il valore +00).
Se per una data coppia di postazioni esistono più cammini con tale proprietà, l'algoritmo
trova il camniino di luiighezza mimma.

Esercizio 2. (punti 11) Dato un grafo G = (1/,£') orientato e aciclico, i cui archi sono pesati
con la funzione TU : £'-4 N~, con v-i € V nodo sorgente e •Un £ l7 nodo pozzo, progettate un
algoritmo per trovare il cammino di peso miniino da 1:1 a l'n. Discutete la complessità della
soluzione proposta.

Esercizio 3. (algoritmi 2) (punti 11) Dati un disco di capacità D e un insieme F = {/i ,/2.. • • ,/n}
di n file, ciascimo di lunghezza li, coli l < t < n, progettate un algorifcnio per trovare un
sottoinsieme Sol C F dì cardinalità inassinia che soddisfi ^j^soih < ^ì- Studiare la
complessità computazionale dell'algoritmo proposto. Sapreste dimostrare perché la strategia
adottata trova l'ottinio?

Esercizio 3. (esonero) (punti 11) Dato un grafo G == (T/,-E) [Link], progettate un algoritmo
ottimo per costrmre il grafo trasposto G — (V, ET) tale che se (i,j) £ E allora (j,ì) £ £'T.
Discutete la complessità e l'ottimalità della soluzione proposta.

i>
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
7 Maggio 2019 - C
Esercizio l Deteniiiiiare, se esistoiio, le frequeiize di 4 caratteri elle sono codificate coil i codici
'•'(, di HufFmaii con:
• 0,10,111,110 S'
• 00, 100, 101, 11 (T-V^
Scrivere lo pseiidocodice dell'algoritmo che calcola l'albero del codice di H-Liffman date le frequenze
>s dei caratteri.

Esercizio 2 Proporre uu'istaiiza dello isaino frazioiiario per cui, insereiido iielìo zaiiio sempre
K l'elemeiito coi], il massimo valore (assoluto), non si ottieiie mia soluzione [Link].. Scrivere lo
pseudocodice dell'algoritmo che calcola la soluzione ottinia per lo zaino frazioiiario.
-y:" rv\'o'v- \'
v Esercizio 3 Dato un grafo G = {V, E} non orientato, e una sorgcritc s e V, trovare il nodo u e V
a massima distanza da s. Progettare l'algoritmo per risolvere il problema, darne lo pseudocodice
e studiare la coiuplessità dell'algoritiiio proposto.

Esercizio 4 Dato im grafo G = (l/,-B) oricntato c pesato, o dato vs. sottoinsieme dei vortici
V C V, trovare i cammini minimi fra tutte 1c coppie dei vortici di V che passano sDlo per i vertici
in \ . Progettare l'algoritino che risolve il problema proposto, darò lo pseudocodico e discuterne
la complessità ili tempo.
 COGNOME NOME

Prova di Algoritmi e Struttiire Dati II

Non si possoiio consultare ne appunti ne testi
IV appello
29 Settembre 2010

Esercizio l (Punti 11). Dato iin grafo G == (V, E) orieiitato e pesato, con pesi positivi per
tutti gli archi tranne per gli archi uscenti dalla sorgente v-^ che possono avere peso qualsiasi,
si determinino in ordine non decrescente i costi dei cammini minimi dsd vertice vi a tutti
i rimanenti vertici di G. Precisamente:

l. progettare im algoritmo e darne lo pseudocodice, e

2. discutere la complessità dell'algoritmo proposto (anche al variare delle strutture dati
iitilizzate) ;
3. come varia l'algoritmo se nou è iiot.o che vi sia una sorgente.
Esercizio 2 (Punti 8). Sia I = {Ji,J2r---irA'} un insieme di N attività ciascuna carat-
fcerizzata da un tempo di inizio e un tempo di fine. Precisamente, Ij ha inizio al tempo Sj
e finisce al tempo /j, con l < j <. N. Due attività sono compatibili se non si intersecano,
ossia fj < si o fi < Sj. Si viiole selezionare mi sottoinsieme I' C I di attività compatibili di
massima cardinalit.à, A questo scopo si utilizza il segiiente algoritmo;
• si ordinano le attività per inizio crescente Ji, li,..., IN
• si scandiscono poi le attività una ad una e ogni volta che l'[Link]à scandita è coinpatibile
con quelle precedentemente scelte si inserisce nella soluzione,
L'algoritmo non. è corretto. Trovare un controesempio. Proporre iin algoritmo per risolvere
il problema.

Esercizio 3 (Punti 11). Codificare la. sequenza APPELLO ALGORITMI con il codice di
Huffman. Qual'è il risparmio rispetto una codifica ASCII? Scrivete lo pseudo codice dell'al-
goritmo per costruire l'albero binario da cui si deriva la codifica. Discutete la complessità
della, costruzione dell'albero.
 Prova di Algoritmi e [Link] Dati
Noil si possono consultare ne [Link] ne testi

16 Maggio 2.017

Esercizio l. Dato uu [Link] G == {V,E) nou [Link], progettare un algoritmo per trovare tutte
le componeiiti coniiessc' del grafo. Disciitere la, complessità in tempo dell'algoritmo proposto;
anche ili base all:implementazioiie del gTafo.

Esercizio 2. Dato un righello di cioccolata liiugo n, c data mia tabella di prezzi pi,p2—--:pn.
ciasciuio corrispondente a.1 ricavo ottembile vendcudo un pezzetto di cioccolata di lunghez'/a
i con l < i < n, decidere come tagliare il righello di cioccolata per [Link]ìzzare il ricavo.
Progettare un algoritmo per trovare la soluzione di ricavo alassimo. Disciitere la complessità.
in tempo dell'algoritmo proposto.

Esercizio 3. Dato un gTa}'y\^neutato G = (V,E'] ed una sorgente .s, i cui archi sono pesati cou
iiiteri [Link] nell'intervallo [0,b] progettare uii algoritmo per trovare l'allH'ro di copcrturEi
TC; di costo niiuhno. Discutere la coinplcssità in [Link] dell'algoritnio proposto. Coinè, varia
l:all)ero di copertiira se la sorgente scelta varia? E' possibile dare in tciupo costante uà
iipper-tjotind al costo di T(-,'?
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
7 Maggio 2019 - A
Esercizio l Iiiserite in una tabella liasli T di diiuensioiie m = 11 coil le collisioni risolte mediante
coiicateiiameiito le seguenti n chiavi l,3,122,5,16. [Link] T dopo aver inserito Is chiavi. Qual'è
il fattore di carico della tabella? C'è un limite superiore al numero di chiavi che si possoiio
uiserire ili T? Esprimere la complessità in fmizione della luiighezza della lista, di coucateiiamento
delle operazioni di iiiserzione, ricerca e cancellazione. Scrivere le procedure in pseudocodice per
l'operazione di ricerca di una chiave k in T gestita sotto le ipotesi prima descritte.

Esercizio 2 Calcolare il codice di Huffmaii per la seguente stringa: 'A buon [Link] non malica
sella' (si ignorino gli spazi). Quanti bit sì risparmiano rispetto ad mia codifica che assegiia a ciasim
carattere 8 bit? Scrivere lo psendocodice dell'algoritmo che calcola l'albero del codice di HiifEman
date in input le frequenze dei caratteri.

Esercizio 3 Dato mi grafo G =: {Vi E} iiou orìeutato, progettare uii algoritmo per testare se il
grafo è aciclico. Stiidiare la complessità hi tempo dell'algoritmo proposto.

Esercizio 4 Dato iin grafo non oricntato o pesato G = (V, £') c il suo albero di copertura di costo
minimo T, si consideri il grafo G = (V U r, E U {(•r,r) : V-u € V} (ciascun nuovo arco c posato).
Sia T l'albero di copertura di costo minimo per G . Dire per ogni affermazione se è vera. o falsa
(giustifìcaiido la risposta):
• r'==r

• T C T' (sia i vertici che gli archi di T sono un sottoinsicmo di quelli di T')
• Esiste uu arco iiicideute al nuovo vertice r in T'

• Esiste uno ed un solo arco incidente al nuovo vertice r

Dare lo pscudocodicc di un algoritmo visto a lezione por calcolare; l'albero di copertura di costo
minima. Discuterne la complessità in tempo.
 ?p^p%^/ ^ur^^^^ ^>UÌQU^

Prova di Algoritmi e Strutture Dati

Non si possono consultare ne appunti ne teyti
Appello Straordinario A.A. 2016-2017
9 Maggio 2018
Esercizio l. Dato un array A ordinato in senso crescente di cardinalità n contenente numeri
interi negativi e -[Link] positivi, trovare U quinto intero positivo in A. Progettare e dare
lo pseudocodice dell'algoritmo proposto. Ana-lizzare la complessità m tempo della soluzione
proposta e discuterne l'ottimalità.
Esercizio 2. Dato un grafo C? == {V, E) diretto aciclico e pesato u': £' ^ N, dato un. intero
fe € N, e data, una sorgente s c V, trovare i vertici in V che distane al più k da s. Descri-
vere un algoritnio che risolve il problema e darne Io pseudocodice. Studiare la complessità
dell'algoritnio proposto. Discutere l'ottimalifcà della soluzione proposta.
Esercizio 3. Per il Guiness dei primati, il paese Pizzasì ha prodotta una pizza di n metri, Per
strani motivi, la pizza può essere vendilta solo a misure multiple del metro. Uà taglio di
i metri si può acquistare pagando pi litri di birra, con l < i <n. Mr. Guinness ha B
litri di birra con sé. Può comperare tutta la pizza? Qual'è la massima quantità di pizza
che può comperare? Dare lo pseudocodìce dell'algoritmo e gìiistifìcare la soluzione proposta.
Discutere la complessità in tempo dell'algoritmo proposto.
 /~~)
•YQ^T^
^ <, ..^, -flc~ - & *- -w&
<-^,:^.'r;^""'&
^ j^~^
! ^^ ^ K
^v^sr ^'u-
^^ /^ J ..;"'. ^ ^^(^ ^1
/U/Y. C^ -^-l- -' _^^ ^,0^6<^<-;
^ ^»"^' ^ ' ;; ,^. ^^e, ^°f^^' "-"
^.
^^c^y^ .^ '
^ ,[Link]. C; ^ -^^ /-
SG^^^ ^ ^
^jl^e/i^o

^(^^^^-^^0^^
 6

Prova di Algoritm.i e Strutture Dati

Non si possono consultare ne appunti ne testi
Ill D esonero A.A. 2013-2014
30 Aprile 2014
Esercizio l. Punti 10 Si consideri il grafo pesato ed orientato G = (V, E) con V = {s, a, b, c, d}
e. E = {(s, a; 8), (s, &; 10), (a, &;4), (a, c; 3),, (6, d; l), (c, o; l), (c, d; 7)}. Si calcoli per ogni coppia
di vertici il costo del cammino minimo che attraversa al più due archi.
Esercìzio 2. Punti 15 Si devono assegnare N > M operai a M lavori. Per ogni lavoro m,
con l ^ m < M, si conosce il tempo T[m, n] necessario per completarlo con n operai, con.
l <n > JV'. Tutti i lavori iniziano contemporaneamente. Il tempo di fine è ristante in
cui tiitti gli M lavori sono completati. Non possoao essere assegnati più di ^V operai e
nessun operaio può essere assegnato a più di un lavoro. Dare la descrizione ad alto livello
dell'algoritmo. Determinare l'asseguamento che minimizza il tempo di fine. Descrivere la
complessità dell'algoritmo proposto. Provare a disciitere perché l'algoritmo è corretto.
Esercizio 3. Punti 10 Si consideri un grafo orieutato e pesato G =- (V,£?), con w : E —> R'r e
sia T l'iabero dei cammini ininimi di G partendo dal vertice s £ V. Per ogni arco e E E,
sostituiamo il costo Cg con il costo Cg + 5, creaiido una nuova istanza con lo stesso grafo ma.
costi diversi. Discutete se l'albero T è l'albero dei canimini iniiiimi di G anche per la nuova
istanza.
 Prova di Algoritm.i e Strutture Dati
Non si possono consultare ne appunti ne testi
Ill B esonero A.A. 2013-2014
30 Aprile 2014
Esercizio l. Punti 10 Si consideri il grafo pesato e non orientato G = (V, E) con V = {s, a, b, c, d}
e E = {(s,a;8),(s,&:10),(u,&;4),(a,c;3),(&,d;l),(c,fc;l),(c,d;7)}. Si calcoli l'albero di
copertura di costo imnimo di G.

Esercizio 2. Punti 15 Siano dati un iatero R e un insieme X =: {.TI, 3:2,..., a;n} di n interi.
Si descriva un algoritmo per trovare un [Link] S di cardinalità |S = -R tale che sia
massima la soiuma degli elementi in S, ossia trovate S = arg max{3';]3']^fi} S^igs' :Ki- Dare la
descrizione ad alto livello dell'[Link]. Descrivere, la complessità dell'algoritmo proposto.
Provare a discutere perché l'algoritmo è corretto.

Esercizio 3. Punti 10 Si consideri un grafo diretto e pesato G = (V,-E), con w : E —r R+,

e l'albero T dei cammini minimi di G partendo dal vertice s e V. Per ogni arco e e E,
sostituiaaio il costo Ce con il costo c^, creando vina nuova istanza con lo stesso grafo ma costi
diversi. Discutete se l'albero T è l'albero dei cammini minimi di G anche per la iiuova istaiiza.
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
Ili C esonero A.A. 2013-2014
30 Aprile 2014
Esercizio l. Punti 10 Si consideri il grafo pesato ed orientato G == (V,E) con V = {s,a,b,c,d}
e E = {(s, a; 8), (s, b; 10), (a, 6; 4), (a, c; 3), (b, d; l), (c, &; l), (c, ci; 7)}. Si calcoli per ogm coppia
di vertici il costo del caminino nummo che passa per i vertice {a, c} o un loro sottoinsieme.
Esercizio 2, Punti 15 Si deve riempire di acqua un barile di volume R nel minor tempo possibile,
Si hanno a disposizione misure di vohime l,'u,-u2,..., •u'1. Per riempire ima misura, di qualsiasì
vokuiie e versare l'acqua nel barile è richiesto im tempo costante t. Qual'è il miaimo tempo
necessario per riempire il barile? Dare la descrizione ad alto livello dell'algoritmo. Descrivere
la complessità dell'algoritmo proposto. Provare a discutere perché l;algoritmo è corretto.
Esercizio 3. Tunti 10 Si consideri un grafo non orientato e pesato G = (V, £"), con w. E ^ R+,
e sia /(T') la somma dei costi degli archi l'albero T di copertiu-a di coBto minimo per G. Per
agili arco e E E, sostituiamo il costo Cg con il costo Ce + 10, creando una nuova istanza con
lo stesso grafo ma costi diversi. Discutete se il costo }(T ) del nuovo l'albero T di copertiira
di costo minimo della nuova istanza può essere calcolato in tempo costante.
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ile testi
Ill esoaero A.A. 2012-2013
21 Maggio 2013

Esercizio l. l. Dato uno zaino di capacità 10 e gli oggetti iti tabella,

valore | Ingombro
01 6 l
0-2 l 8 2
03 25 5
04 10 3
0.5 16 4

trovare
zato.
lo zaino di valore massimo. Dare la complessità in tempo dell'algoritmo utiliz-
2. SuppoiierLdo di aver risolto il problema nel caso precedente, dare un algoritmo per risol-
vere il problema: Trovare lo zaino di valore massimo quando la capacità è 7 e gli oggetti
sono gli stessi della tabella precedente.
Esercizio 2. Dato un grafo non [Link], i cui archi sono colorati di rosso, verde, e blue, trovare
la dimensione della più grande componente coiinessa i cui vertici inducono uu sottografo con
tuttì e soli archi verdi (attenzione, il grafo iiidott.o è costituito da tutti gli archi i cui vertici
stanilo nella componente couaessa).
Esercizio 3. l. Data un grafo nou orientato C =• (.V, E) e. pesato w : E —> R (nota che i
pesi possono essere negativi), trovare l'albero di copertura di costo miuirno. Dare lo
pseudocodFce e disciitere la complessità deU'algoritmo proposto.
2. Si consideri poi il grafo G' = (V U s, S = {(s,v) : V r 6 l'} U E), dove il peso di
ciascun nuovo arco è 0. Si ricalcoli l'albero di coperti.u-a di G'. Dare lo pseudocodice
dell'[Link] e studiarue la complessità.
3. Iiifìue, se i costi di tutti gli archi di G sono negativi, ossia, if : E —> R~, quanto costa
ricalcolare l'albero di copertiira di G/?
Esercizio 4. Topolino è alla stazione della metropolitana della città iu cui si è trasferito Pippo.
Ha comperato un biglietto a. [Link] oraria. Di ogni tappa ( percorso fra due fermate), conosce
la durata iu minuti. Topolino vuole sapere le località che può' raggiungere in al più 60 minuti
a partire, dalla stazioiie della metropolitana. Puoi aiutarlo? Dare lo pseudocodice e disc;utere
la coniplessità. della soluzione proposta.
 Prova di Algoritmi e Strutture Dati II
Non si possono consultare ne appunti ne testi
VI appello

15 Febbraio 2006

Esercizio l. (punti 4) Sia G = (V, E) una rete di fliisso con sorgente r e pozzo s. Sia V =
{r,p,a,s,fr,Q}e£={(r,p;l,l),(r,g;4,2),(p,a;l,l),(p,6;3,l),(a,p;l,l),(a,s;l,l),(9,a;3,l),
(g,6;l,l),(ò,Q;l,0),(6,s;4,2)} ove la quadrupla (u,v;c,f) rappresenta l'arco (u.,v) con ca-
pacità e fliisso c e /, rispettivamente. Determinare il flusso corrente. Costruire la rete residua
Gf. Trovare un cammino aumentant.e.
Esercizio 2. (punti 8) Dato un grafo orientat.o G = (V,-E), i cui vertici memorizzano un intero,
scrivere un algoritmo enumerativo per determinare una partizione dei vertici ili V in 2 sot-
toinsieini V{ and V^ tali che il prodotto degli interi inemorizzati nei vertici di V{ sia doppio
del prodotto degli interi memorizzati nei vertici di Vo.
Esercizio 3. (punti 8) Sia G = (V, E) un grafo [Link] e pesato, dove i pesi degli archi sono
reali, positivi, unici e sono tali che i pesi siigli archi di CÌEUJCUU cammino minimo dalla sorgente
.s € V ad un vertice v e V formano una sequeiiza crescente. Modificare l'algoritnio dei
cammini iiiinimi da sorgente siiigola cosi da sfruttare l'ipotesi aggiuiitiva sul grafo G. Scrivere
iiiia [Link] dell'algoritmo in pseudocodice e giustificare la complessità della soluzione
proposta.

Esercizio 4. (punti 6) Si risolva il problema dello zaino intero con ripetizioni per uno zaino
di capacità M == 23 considerando 4 oggetti con ingombro fei == 10, A:2 = 5,A;3 = 6,^4 = l e
valore z'i = 8, l'a = 4, vs == 6,114 = l, rispettivamente. Descrivere la complessità dell'algoritmo
adottato.

Esercizio 5. (punti 4) Codificare con i codici di Huffmau la seguente sequeiiza "MICKEY MOUSE".

5 -AO>®S'-Sno®3fT9°-1^?o@©^Tl^rIo*S
a?%o^©i^J,-ù-« ©oAÒoE^-iAQA^OÙ^ad •8 AE'MI©ÒAE
 o
PJL ENTER LANGUAGE = PCLXL
) HP-PCL XL;l;l;Comment Copyright Artifex Sofware, I
^.°Lk^ L@%£É ,%*OLkll= L©@° ZR L

Prova di Algoritmi e Strutture Dati I

Non si possono consultare ne appunti ne testi
II appello

15 Febbraio 2006

Esercizio l. (punti 4) Trovare un limite superiore per la ricorrenza T(n) == T(^) + Ioga ?i, as-
sumendo che T{n) sia costante per n < 4 e n sia una potenza di 2. Spiegare la soluzione.
Esercizio 2. (punti 8) Un array A = [l,.,.,?ì] contiene n interi, tiitti compresi fra O e n. Sì
assuma n = 2fc, con fc > 0. Si assuma che l'array A sia ordinato in senso crescente. De-
scrivere un algoritmo che trova l'intero niancante in tempo O(logn). Dare lina realizzazioiie
dell'algoritmo in pseudocodice e giustificare la complessità della soliizione proposta.
Esercizio 3. (punti 4) Si siipponga di applicare la teciiica della scansione lineare per risolvere
le collisioni in lina tabella hash di dimensione m, ov-vero si utilizzi la funzione haah /i(fc;i) =
(/I)(A;) +ic) mod »ri). Sec=3 eni = 9, può fallire un' inserzione di lina chiave con la tabella
non [Link] piena? Motivare la risposta. Dare uu valore di c, con c -^ l, per cui
l'inserzione fallisce solo coii tabella piena.

Esercizio 4. (punti 6) Dato uu grafo orientato G = [V,E), descrivere un algoritmo per con-
trollare se G è un grafo aciclico. Dare mia realizzazione dell'algoritmo in pseudocodice e
giustificare la complessità della soluzioiie proposta.
Esercizio 5. (punti 8) Descrivere un algoritnio per ordinare in tempo 0(?ì) n. niinieri iiiteri
compresi nell'intervallo da O a n3 — l. Dare una realizzazione dell'algoritmo in paeudocodic.e
e giustificare la complessità della soluzioiie proposta.

l'^^m , %@J^J^ ^ttJBT^AdOO ^aeUIUIOD.'T.'T.^X r[3d-dH (

..EOV^ T; .:••• A@@8ru» z.t An nnTnnnnn
nn n;-I?:r^?T: aoSQSN^^
^'®'T^TUr f.
 ^

Prova di Algoritmi e Strutture Dati II

Non si possono consultare ne appiuiti ne testi
IV appello
28 Settembre 2006

Esercizio l. (punti 12) Sia G = [V,, E) sia un grafo non orientato con n nodi. Un sottoinsieme
J dei vertici di G è un insieme indipendente se nessuna coppia dei vertici di J è connessa da
im arco m E, ossia se per ogni coppia di vertici u,'u 6 -T è soddisfatto {u,v) ^ E. Progettare
l. una procedura Pascal polinomiale non deterministica,
2. una procedura Pascal deterministica enumerativa
per trovare un insieme indipendente di cardinalità massima hi G.
Esercizio 2. (punti 12) Sia D = (Vr, jB) iin cammino e si associ a. ciascun vertice ViGV un intero
positivo Wi, detto peso. Si consideri il probleina di trovare un insieme indipendeute J di n il
cui peso totale, ossia la somma dei pesi dei vertici in I, sia massimo.
l. Progettare un algoritmo greedy che risolva tale problema e dame una realizzazione m
pseudocodice.
2. Dimostrare che l'algoritmo è ottimo o dare un esempio in cui tale Algoritmo noli trova
la soluzione ottima.

Esercizio 3. (punti 6) Si risolva il problema dello zaino intero senza, ripetizioni (zaino 01), con
M == 10 e coiisìderando gli oggetti o; = (z'i, fc;), cou l < i ^4, tali che:
oi =(.3,5); os =(5,7); os =(2,8); 04 =(1,3)
°^-SBOÙS'A®l,&*-L@lié<LÈÀ-¥ ° L»o££U^@Q^4oo±H@^:pQ^@05èÓ?-LÈ*Sl-T<Ìlt±?QOÌ

Prova di Algoritmi e Strutture Dati I

Non si possono consultare ne appunti ne testi
I appello
25 Gennaio 2006

Esercizio l. (punti 10) Progettare im algoritmo divide-et-impera per il calcolo del massimo di
un vettore A non ordinato contenente n interi. Tale algoritmo divide A in tré parti e organizza
ricorsivameute la ricerca. In particolare:
(punti 2) Descrivere a parole la struttura dell'algoritmo di risoluzione
(punti 4) Dare lina realizzazione dell'algoritmo in pseudocodice
(punti 4) Valutare la complessità in tempo dell'algoritmo spiegando il risultato indicato. Discutere
l'ottimalità in tempo dell'algoritmo proposto.
Esercizio 2. (punti 14) Si consideri un MAX heap [Link] di n nodi e altezza h.
(punti 2) Descrivere le proprietà di un MAX heap quaternario.
(punti 3) Descrivere un'irnplementazione efficiente dello heap quaternario tramite un vettore A,
indicando le formiile per calcolare la posizione del padre, del primo; del secondo, del
terzo e del quarto figlio di un nodo i. Si assiima la radice dello heap memorizzata in
posizione l di A.
(punti 4) Dare una realizzazione in pseudocodice dell'operazione Insert-KeyfA, k) per lo heap
quaternario. Analizzare la complessità della soluzione proposta.
(punti 5) Dare una realizzazione iu pseudocodice dell'operazione Max-Heapify(A,i) per lo heap
quaternario. (Max-Heapify(A;i) ristabilisce le proprietà dello heap dopo che A[i] è stato
decrementato. I sottoalberi radicati nei figli di i non violano le proprietà dello heap).
Analizzare la complessità della sohizione proposta.
Esercizio 3. (punti 4) Calcolare la coniplessità in tempo nel caso pessimo del segiiente algoritmo
ricorsivo:
function Pippo (A, i, j);
vai- sum, k: integer;
if (i = j") then return 1;
sum := 0;
for k :=i. to j do

return (Pippo(A,z,(?)*Pippo(A,i,g) + sum).

Esercizio 4. (punti 4) Esegiiire la visita in profondità (DF.S), del seguente grafo [Link] G =
(V,E), ove V = {1,2,3,4,5} e E = {(1,2), (1,3),(1,4),(2,4), (3,5), (4,3), (4,5)}. Specificare
il tipo di ogni arco visitato.
 Prova di Algoritmi e Strutture Dati I
Non si possono coiisultare ne appunti ne testi
Ili appello
12 Giugno 2006

Esercizio l. (punti 8) Verificare se

• T(n) =- T(log2 n) + 0(1) 6 0(log* n)
• 23n e 0(2")
Esercizio 2. (punti 12) Dato un grafo diretto G == (V, E), progettare zin algoritmo che decide se
G è un grafo ciclico. Se G contiene cicli, l'[Link] ne ritorna uno. Valutare la complessità
in teiupo dell'algoritmo proposto.
Esercizio 3. (punti 12) Un array A[l..n] contiene gli iiiteri fra. O e n, tranne uno. Ciascuii
infcero è rappresentato in binario. Non è possibile leggere un intero completo di A, ma
l'unica'operazione di lettura possibile è leggere il bit j-esimo di A[i}, con O ^ j < \log^(n)^ e
l ^i <. n. Tale operazione richiede tempo costante. Progettare un algoritmo divide-et-impera
che in tempo O (n) trova l'intero mancaiite.
(punti 2) Descrivere a parole la struttura dell'algoritmo di risoluzione
(punti 5) Dare una realizzazioiie dell'algoritmo in pseudocodice
(punti 5) Valutare la. coiiiplessità in tempo dell'algoritmo spiegando il risultato indicato. Discutere
l'ottimalità in tempo dell'algoritmo proposto.

fc
I: '[Link]ÌOS X9?T-4J[Y ^qB-c^AdoD ^usuiuio^.'T .'T ; ^x T:Dd-dH (
rIx^^d == ssvnoNvi yaANa ^^d
 Prova di Algoritmi e Strutture Dati II
Non si possono consultare ne appunti ne testi
II appello

20 Luglio 2006

Esercizio l. (punti 12) Dati un grafo non orientato G ed un intero k, il problema dell'afòero di
copertura limitato, chiede se esiste un albero di copertura T per G tale che in agili nodo di
T siauo mcideati al più k archi. Tale problema è NP-completo. Si progettino per risolvere
questo problema:

l. uua procedura polinomiale non deterministica,

2. una procedura deterministica enumerativa.
Esercizio'2. (punti 6) Determinare il mininw numero di chiavi che contiene un B-albero di
altezza h e avente grado minimo t, con t > 2. Spiegare il risultato.
Esercizio 3. (punti 4) Sia L una Hash Table Estensibile, inizialmente vuota, con ciascun po-
sizioae in grado di [Link] fino a 2 chiavi. Si niostri il conteimto di L dopo aver inserito
le chiavi 5 ={0000,0010,1000,1010,0111,0110} nell'ordine in cui appaiono nella Usta 5'.
Esercizio 4. (punti 10) Si formiili il seguente problema P coinè un problema di flusso massimo,
ossia si disegni una rete di flusso associata a P il cui flusso massimo si trasforma facilmente
in una soluzione del problema P.
Problema P: Data una matrice quadrata M con 2 x 2e gli interi {5,7,4,8}, determinare i
valori M[i, j] > 0, inemorizzati in M, tali che la somma degli interi memorizzati nella colonna
l sia 4, quella degli elementi nella colonna 2 sia 8, [Link] la somma degli interi niemorizzati
nella riga l sia uguale a 5 e quella degli elementi nella riga 2 sia 7.
 Prova di Algoritmi e Strutture Dati I
Non si possono consiiltare ne appunti ne testi
IV appello

20 LugUo 2006

Esercizio l. (punti 12) Dato un grafo non diretto G = (^,5), progettare un algoritmo per
visitare tutti i vertici a distanza al più k da un dato vertice s € V. Dare una realizzazione
dell'algoritmo in pseudocodice e valutarne la complessità in tempo.
Esercizio 2. (punti 12) Progettare un algoritmo divide-et-impera per determinare l'elemento
di rango 3 in un array A == [l,...,?ì], contenente n = 2k interi. Dare una realizzazione
dell'algoritmo in pseudocodice e giustificare la complessità della soluzione proposta.
Esercizio 3. (punti 8) Calcolare
• la complessità in tempo nel caso pessimo del seguente algoritmo ricorsivo:
function Pippo (n);
begin
if (n < 8) then return 1:
x := 2 Pippo([§J):
i :=: l;
while i < nf'2 do begin
J:=l;
while j < 2 Ioga n do
J:=J+2;
i := i* 2;
end
return (x)
end

• un limite superiore per la ricorrenza T(n) = 2T(^/n) + logs n, assumendo che T(n) sia
costante per n <, 4. en sia. una. potenza di 2. Spiegare la soluzione.
 Prova di Algoritmi e [Link] Dati
Non si possono consultare ne appunti ne testi
IB esonero A.A. 2013-2014
2.0 Novembre 2011

Esercizio l. Studiate, la complessità in tempo nel caso pessimo del seguente algoritmo assumen-
do die l'array A sia ordinato in senso crescente:

l Guess-Wha<;(A,k,p, u):booleau
2 int step;
s while (p < u) do
4 l step:=[_v^^,
s I if (k == Afp+step]) V ^; = A{p+2*[Link]]) then
L return: True
e if fc < A[-p+sptep] then
7 l l u := p+step-1
s l else
9 l l if fc < Alp+Z^sptepì then
io l l l p:=p+step+l;u:=p+2*step-l
il l l else
12 l l [_ p:=p+2*step+l
return: False

Esercizio 2. Ordinate in ordine crescente di grandezza le segueiit.i funziom e giustificate l'ordine

scelto:

410g4 ÌOSis, " • l610g-< lost6 "; 210g'1 "

Inoltre, applicaiido la definizione di ordine, di gi-aiidezza determinare costanti Ci > 0, es > O

e no > O che verificano:

Tlogg n — 6 log4 ri + 16 € ©(Ioga n}

Esercizio 3. Trovate un limite asintotico superiore per la complessità in tempo del seguente
algoritmo ricorsivo e dimostratelo per indiizioiie:

l Pippo(n : iuteger):[Link];
2 int f :== l; k := l:
3 while £< n-1 do
4 forint ì:= l, ì< f, i++do
5 L A :=fe+l
6 f:=3*f
7 if n > O then
8 Pippo:=Pippo(Ln/3j) * Pippo([n,/2J)
8 else
io |^ Pippo:=12

Esercizio 4. Descrivete al variare del parametro e > O la complessità dell'Eq. di ricorrenza:

f4 if n $ 2
T(n.)
<[ 4T(1)+ne if n > 2
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
Appello VII A.A. 2018-2019
21 Gennaio 2020

Esercizio l. Dato un testo T, si vogliono sostituire i caratteri che appaiono in esso con una codifica tale
da minimizzare la luiighezza del testo T dopo la codifica. Descrivere un algoritmo che restituisce la
codifica da sostiture a ciascun carattere in T. Descrivere la complessità dell'algoritmo di codifica.
Motivare perché l'algoritmo proposto minimizza la dimensione del testo T dopo la compressione.
Esercizio 2. Dato un grafo non orientate G = (V, E) connesso e aciclico, si vogliono etichettare i vertici
in V in modo che gli estremi di ogni arco siano assegnati a due etichette diverse. Descrivere un algo-
ritmo che risolve il problema c darne lo pscudocodice. Quante etichette sono utilizzate dall'algoritmo
proposto? Il grafo G c un albero? Studiare la complessità in tempo dell'algoritmo proposto.
Esercizio 3. Dato un grafo G = (V, E) diretto e pesato w : E —f N+, data una sorgente s e V, trovare il
vertice u tale che il cammiiio da s a u sia quello di peso d(s, u) minimo in G'. Descrivere un algoritmo
che risolve il problema e dame lo pseudocodice. Studiare la complessità dell'algoritmo proposto.

Esercizio 4 Calcolare la complessità in tempo dei seguenti algoritnai:

1 Test; int s := n; a :^= l; t := O 1 Pippo(n : int) : int

2 while s > l do 2 if n < 3 then
3 L &• := L|J;a++ 3 I return 1
4 else
4 for i •= l;i++;2a do
5 \_t--2+t • 5 j ••= l;
6 while j < n do
7 [_j:=j+2
8 return Pippo (^) . Pippo (|) + ^fn
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
Appello VII A.A. 2018-2019
21 Gennaio 2020

Esercizio l. Dato un testo T, si vogliono sostituire i caratteri che appaiono in esso con mia codifica tale
da minimizzare la lunghezza del testo T dopo la codifica. Descrivere un algoritmo che restituisce la
codifica da sostiture a ciascun carattere in T. Descrivere la complessità dell'algoritmo di codifica.
Motivare perché l'algoritmo proposto minimizza la dimensioiie del testo T dopo la compressione.

Esercizio 2. Dato un grafo non orientate G = (V, E) connesso e aciclico, si vogliono etichettare i vertici
in V in niodo che gli estremi di ogni arco siano assegnati a due etichette diverse. Descrivere un algo-
ritmo che risolve il problema c darne lo pseudocodicc. Quante etichette sono utilizzate dall'algoritmo
proposto? Il grafo G c un albero? Studiare la complessità in tempo dcll'algoritnio proposto.
Esercizio 3. Dato un grafo G = (V^ E) diretto e pesato w : E —^ N+, data una sorgente s ^ V, trovare il
vertice u tale che il cammino da s a u sia quello di peso c?(s, u) miiiimo in G. Descrivere un algoritmo
che risolve il problema e darne lo pseudocodice. Studiare la complessità dell'algoritmo proposto.
Esercizio 4 Calcolare la complessità in tempo dei seguenti algoritmi:

1 Test; int s := n; a:=l; t := O 1 Pippo(n : int) : int

2 while A' > l do 2 if ?z < 3 then
• 3 L A':= [jj;a++ 3 I return 1
4 else
4 for i := l:t++;2a do
5 L t:=2+t 5 j ••= l;
6 while j < n do
7 L J :=^' +2
8 return Pippo (^) . Pippo (j) + /'n
PJL ENTER LANGUAGE =: PCLXL - . ._ - +
) HP-PCL XL;l;l;Comment Copyright Artifex Sofware, I

COGNOME NOME
Prova di Algoritmi e Strutture Dati II
Non si possono consultare ne appunti ne testi
IV appello
24 Settembre 2008

Esercizio l (Punti 12}. Il problema del calcolo dei cammini mmimi da sorgente singola in
un grafo orieatato e pesato si può esprimere come un prodotto tra una matrice e un vettore.
Progettate tale algoritmo. (Sugg. Modificate l'algoritmo analogo alla moltiplicazioae di
matrici per il calcolo dei canunini minimi fra tutte le coppie). Discutete la complessità
computazionale della soluzione proposta.
Esercizio 2 (Punti 12). Data una stringa S = a-ia^.-.an di n caratteri, considerate il
problema di determinare la lunghezza t della sottostringa (composta da caratteri consecutivi)
palindrome S' più lunga m 5. Progettate un algoritmo per determinare l m tempo 0(n2).
Esempio: S=ASAACA, S'==ASA o S'=ACA -» ^ = 3
Esercizio 3 (Punti 6). Disegnate un grafo non orientato pesato G [V,E}coii\E\>\V\,
il cui albero di copertura di costo minimo sia unico.
 Prova di Algoritmi e Strutture Dati I
Non si possono consultare ne appunti ne testi
VI appello

23 Settembre 2008

Esercizio l. (punti 10) Si consideri il ciclo così definito:

while n > 2 do n := J'(n);

Tftovate il costo computazionale dell'esecuzione di tale ciclo while per ciascuoa funzione /(n):
• /(ra) =: n — 5
• /(n) = n 12
• /(7!,)=log7l
• f(n) == Vn
•/(")-Ktn
Esercizio 2. (punti 10) Un vettore V di n interi diatmti è detto convesso-semplice se esiste un
indice j, con l < j <:n, tale che y[l] = V[2] = ... = V[j] e V[i] < V[i + l] per j <,i<n.
• Progettate un algoritmo che, dato un vettore convesso-semplice V di n ^2 interi, trovi
l'indice j in tempo O(logn).
• Discutete l'ottimalità della soluzione proposta.
Esercizio 3. (punti 10) Data una tabella hash T ad indirizzamento aperto di dimensione m,
progettate un algoritmo per cercare una chiave k in T. Come si deve modificare l'algoritmo
di ricerca se si permette ]a caDcellazione fisica delle chiavi da T? Quanto costa in tempo, nel
caso pessimo, la ricerca in entrambi i casi?
 Prova di Algoritiiti e Strutture Dati II
Non si possono consultare ne appunti ne testi
VI appello
13 Febbraio 2008

Esercizio l. (punti 10) Dato un grafo orientato e pesato G = (V, £) e il vertice v. £ V, verificare
se esiste un ciclo di peso negativo da v a v di lunghezza <. 4.
l. Dare lina realizzazione in pseudocodice (ad alto livello) dell'algoritmo proposto.
2, Valutare la complessità dell'algoritmo proposto.
Esercizio 2. (punti 12) Sia G = (V, S) un grafo connesso non orientato pesato, con pesi interi
(sia positivi che negativi). Un [Link] di [Link] di costo minimo 5" per G è un sottogi'afo
conuesso di G il cui peso totale, dato dalla somma dei pesi degli archi in 5", è minimo,
l. Descrivere a parole un algoritmo che risolva il problema.
2. Valutare la compleyyità dell'[Link]
Esercizio 3. (punti 8) Si rappresentino diie heap binomiali BI eBs di 13 e4 chiavi, rispettiva-
mente. Si rappresenti poi lo heap risidtante dalla unione di B) e Ba. Discutere la complessità
in tempo dell'operazione Union fra heap binomiali.

+
y(;©J^O^^Ql)'i^^'W^fela@<^<?©LN(^-Lfi^^S?>Pyafe04.0LklL^@o^l4?^®y^3^fiy3-y3-v3y^3,' k

COGNOME NOME (

Prova di Algoritmi e Strutture Dati II

Non si possono consultare ne appunti ne testi
Ili appello
3 Settembre 2008

Esercizio l (Punti 10). Dato un grafo orientato e pesato G == {V,E), con una funzione
peso w :E —> R,e data una destinazione z e V, considerate il problema di trovare un
cammino di costo minimo da ciascun vertice v € V alla destinazione z. Progettate un
algoritmo efficiente per calcolare il costo mmimo di tali cammini. Date la realizzazione
dell'algoritmo proposto in pseudocodice e calcolatene la complessità in tempo e spazio.
Esercizio 2 (Punti 10). Sia A = {01,02,..., On} un insieme di avvisi pubblicitari e W
la pagina web in cui tali avvisi possono essere inseriti. Inserendo l'avviso pubblicitario a, in
W, occupate pi righe di W e ricevete credito c; dall'azienda pubblicizzata. Considerate il
problema di selezionare un sottoinsieme degli avvisi pubblicitari in A in modo che la somma
dello spazio occupato da ciascun avviso non superi lo spazio P a disposizione in W e in modo
che sia massimizzata la somma dei crediti che potete ricavare. Progettate un algoritmo che
risolva m modo ottimo la selezione degli avvisi pubblicitari in tempo 0(nP).
Esercizio 3 (Punti 10). Descrivete brevemente le principali differenze fra gli heap blno-
miali e gli heap di Fibonacci. Trovate una sequenza di operazioni degli heap di Fibonacci che
crea un heap di Fibonacci formato da un solo albero che è una catena lineare di n nodi, one
n intero positivo.
ogèE®&*SLkéé^@«ì?R^óA-v@«*s"v©l»ao"®"^v©'^r^©*.»"év©^«"è8@?@"Q^"è<i©*@"èi@*@"'ll©®
è
o^°LklLl^ °%<LÈ9
64°LkU=L©®oc,RL-°Ó-Ló©OÙS-Ó@93ÙL ?L@ ?L© ?L© ?L© ?L

COGNOME NOME
Prova di Algoritmi e Strutture Dati II
Non si possono consultare ne appunti ne testi
II appello
25 Giugno 2008

Esercizio l (Punti 12). Data un grafo orientato e pesato, progettate un algoritmo per trovare
tutti i vertici che appartengono ad un ciclo di peso mmimo e negativo, e lunghezza < c, ove
c è una costante positiva. Disditele, in funzione di c, \V\, e \E\, la complessità hi tempo nel
caso pessimo dell'algoritmo proposto.

Esercizio 2 (Punti 12). Sia data una matrice M == [m;j] di dimensione m x n contenente in-
teri positivi. Progettate un algoritmo greedy che trovi un sottoinsieme S C M i cui elementi
abbiano somma massima, con il vincolo che non ci siano in S due o più elementi che apparten-
gono alla stessa riga di M (mentre due elementi possono appartenere aJla stessa colonna).
Discutete la complessità in tempo della sohizione proposta. Dimostrate che la scelta greedy
da voi proposta porta ad una sohizione ottima.

Esercizio 3 (Punti 6). Discutete la. complessità in tempo dell'algoritmo di Dijkstra per il calcolo
dei cammini minimi da sorgente singola al variare, dell'implementazione della coda di priorità
che memorizza le stime dei cammini minimi.
 Prova di Algoritmi e Strutture Dati con Laboratorio

Non si possono consultare ne appunti ne testi

I AppeUo A.A. 2016-2017

19 Settembre 2017 (A)

Esercizio l. (punti 8) Per uno stesso problema sono stati disegnati tré diversi algoritmi le cui
complessità in tempo sono:

• /l("); •^n
^k=l'(fe2 + fc)
V [Ioga nj fn2"
/2(n) - 2^fc=o- ~ [2^

• /3(") J T(n- 2) +2 n > 2

^ l n=l
Qual'è l'algoritmo più efficiente? Ordinare gli algoritmi dal più efficiente al meno efEciente.
Motivare adeguatamente la risposta.

Esercizio 2. (punti 8) Un'impresa edile deve eseguire alcuiii lavori di restauro in un apparta-
mento. Tra i lavori il proprietario ha posto dei vmcoli di precedenza. L'impresario che
vorrebbe appaltare i lavori è convinto che non sia possibile soddisfare tali vincoli. Progettare
un algoritmo per verificare o confutare l'ipotesi dell'impresario. Dare lo pseudo-codice del-
l'algoritmo e studiare la complessità in tempo della soluzione proposta. (Sugg. U problema
è modellabile con un grafo orientate.)
Esercizio 3 (Punti 8). Siano mi, mz,. ..'mfc = l le taglie intere di una nuova moneta cordata
nel paese-che-non-c'è. Nel paese-che-non-c'è, è necessario fare il resto restituendo il minimo
numero di monete, ma le taglie non sono multiple una deU'altra. Dato Re N, progettare un
algoritmo per formare il resto R secondo le regole del paese-che-non-c'è. Dare lo pseudo-codice
dell'algoritmo e studiare la complessità in tempo della soluzione proposta.
Esercizio 4 (Punti 8). Sia T un albero binario di ricerca. Progettate un algoritmo per ordinare
le chiavi meinorizzate m T. Discutete la correttezza della soluzione proposta. Discutete la
complessità in tempo della soluzione proposta.
Esercizio 5 (Punti 8). Dato 3 vettori ordinati Ai, Ag e As, ciascuno di dunensioae n, progettare
un algoritmo che calcoli l'insieme ordinato A == Ai UAs UAs, Date lo pseudo-codice della
soluzione proposta e la complessità di tale soluzione. Discutete l'ottimalità della soluzione
proposta.
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
x Maggio 2019 - D
Esercizio l Si coiisideri uii'[Link] del probleiiia dello [Link] fra..iiouario ili cui '.lìtt.i gli oggetti
haiuio lo stesso peso. Si costruisca la solu-ziione ottima di tale istanza seleziouando seìnpre l'oggetto
di valore inassimo. Provare o coiifutare che l'algoritmo proposto trova la soluzione ottima. Dare
lotalepseudocodice
algoritmo.
dell'algoritmo proposto per questo problema. Studiare la complessità iu tempo di

Esercizio 2 Proporre uii'istauza del probleiiia della selezione delle attività per crii, seleziouaiido
coinè regola greedy l intervallo più breve, non si ottieiie uiia soluxioiie ottima. Scrivere lo pseu-
docodice dell'algoritaio greedy visto a lezioue che calcola la soluzione ottima per la selezione di
attività. Studianie la complessità ili tempo.

Esercizio 3 Dato mi grafo orieiitato G == ty,E), eseguire la visita ili profoiicìità del grafo e
restitmre per ogiii arco iu E il suo tipo. Dare lo pseudodice dell'algorituio, e studiar3 la coinplessità
ili tempo dell'algoritmo proposto.

Esercizio 4 Data una sequenza di matrici Ai, Aa,... ,A,t, dctcnmnareil miniino nuiTicro di
prodotti scalari richiesti per calcolare la matrice prodotto H = Ai -Ao ... • A,,.. Descrivere
l'algoritino, darne lo pseudocodice, e valutarne la complessi'eà in tempo.
 Prova, di Algoritmi e Strutture Dati II
Non si possono consultare ne appunti ne testi
VI Appello
16 Febbraio 2011

Esercizio l. (punti 10) Nella città Balzelli-Su-e-Giù, si possono percorrere al più 5 tratte con-
secutive con lo stesso mezzo di trasporto (tram, bus, metro'). Per ogni mezzo di trasporto,
la mappa della città è rappresentato da un grafo orientato in cui i nodi sono le ferniate del
mezzo e gli archi le tratte percorribili. Ciascuna tratta ha un costo diverso. KIr. Scrooge
abita vicino ad una fermata del bus. Egli vuole determinare per ogni altra fermata del bus, se
è raggiungibile con il bus, e, quando lo sia, il costo minimo per raggiungerla. Potete aiutarlo?
Dare lo pseudo-codice dell'algoritmo da eseguire e determinarne la complessità in tempo.
Esercizio 2. (punti 10) Sia MST+ un algoritmo per calcolare l'albero di copertura, di costo
mininio di un g'[Link] C? non orientato che assiime che i costi degli archi in G siano [Link]
positivi. Come si può applicare l'algoritmo AIST+ ad un grafo non orientato G = (V, E) i cui
archi sono pesati secondo la funzione w : £ —* R (quindi i costi possono essere anche negativi)
per calcolare correttamente l'albero di copertura di G'ì Si scriva l'[Link] modificato. Si
disciita. la correttezza e la complessità della soluzione proposta.
Esercizio 3. punti 10) In un albero orientato T dalla radice verso le foglie, i cui archi sono
pesati, un sofctoinsieme degli archi e detto univoco se non contiene 2 o più archi uscenti dallo
stesso nodo. Si consideri il problema di trovare un insieme univoco A di archi di T di peso
massinio.

l. Dare un algoritmo greedy per risolvere tale problema.. L'algoritmo proposto è ottimo?
2, Dare una. realizzazione in pseudocodice dell'algoritmo proposto.
3. Valutare la complessità in tenipo della soluzione.
 Prova di Algoritmi e Strutture Dati II
Non si possono consultare ne appunti ne testi
7 Giugno 2011

Esercizio l (Punti 15). Si consideri il seguente algoritmo S-&IST per calcolare un albero
di copertura T di costo mininio di un grafo connesso, non orientato e pesato G •= (V, E), i
cui pesi sono tutti distinti.
Algoritmo S-MST(G,T):
• ordina, l'insieme E degli ardii di G in senso decrescente rispetto ai loro pesi, tale che.
È! > G2^ ... > era:
• r := £;
• for (i =m;ì < l; i—-) do
if G = (V.T - {e,}) è un grafo connesso then T •.-=T - {ei};
• return T

l. Dire. se l'algoritiuo S-MST calcola un albero di copertura di costo mininio per G.

[Link] la risposta.
2. Scrivere, in pseudocodice una procedura per verifìcare se G è coiinesso.
3. Discutete la complessità computazionale di S-MST

Esercizio 2 (Punti 10). Consideriamo un grafo G = {V, E) orientato e i cui archi sono
p&sati. Siano s e t due sorgenti in G. Tutti gli archi in E hanno peso non negativo, traime
alcuni archi uscenti da s. Si consideri il problema di calcolare i canimini minimi da sorgente
singola in G. In tale grafo G, la scelta della sorgent.G può iiifluenzare il costo coniputazionale.
[Link]'algoritiuo? Motivare, la risposta. Progetta.t.e un algoritmo per risolvere in C? il calcolo
dei canimini minimi verso tutti i vertici dalla sorgente s. Discutete la coiuplessità in teiupo
della soluzione proposta.
Esercizio 3 (Punti 5). Codificare con i codici di HufFman la. strìnga BING. Qual'è il
risparmio rispetto al codice che codificcT. ciascun carattere, [Link] cleUa stringa con una
sequenza di 2 bit (ad es, B-=00, I==01, N=11, G=10)? Dare una stringa di 4 caratteri per
la quale sia vantaggioso applicare i codici di Huffman rispetto al codice che codifica ciascuii
carattere distinto della stessa stringa con una sequenza di 2 bit.
 o

COGNOME NOME
Prova di Algoritmi e Strutture Dati II
Non si possono consultare ne appunti ne testi
IV appello
30 Settembre 2009

Esercizio l (Punti 15). Un lavoro L richiede N passi, nell'ordme <\,2,... ,N >. Soiio
disponibili diie macchine A e B. Se il passo i è eseguito sulla macchina i, esso richiede
tempo a», meutre se è esegiiito sulla macchiila 5, richiede tempo &i. II trasferimento dalla
macchina A alla macchuia B dopo il passo i richiede tempo t.4fi('1)] mentre-il trasferimeato
dalla macchina B alla macchina A dopo il passo i richiede tenipo fs/i(t), con l <i <n— l.
Dare una formulazione basata sulla programmazione dinamica per determinare il tempo
minimo necessario per esegiiire L e per ricostruire la soluzione di costo minimo. Dare Io
pseiido codice dell'algoritmo proposto.
Esercizio 2 (Punti 15). Dato un grafo G = {V, E), orientato e pesato, determinate il
vertice c di G, detto centroide, tale che Sy^v d(c, i() sia mmima, ove d(c, u) denota la distanza
fra c e u. Descrivete un algoritino per risolvere il problema e studiate la complessità in tempo
dell'algoritmo proposto.
JL ENTER LANGUAGE PCLXL
) HP-PCL XL;l;l;Comment Copyright Artifex Sofware, I

COGNOME NOME
Prova di Algoritmi e Strutture Dati II
Non si possono consultare ne appunti ne testi
II appello

30 Giugno 2009

Esercizio l (Punti 12). Dato un grafo G =- {V,E} orientato e pesato, con. pesi non nega-
tivi, si determinino il costo e il numero di archi di ciascun cammiiio minimo dal vertice l'i a
tutti i rimanenti vertici di G. Precisamente:

l. progettare un algoritmo e darue lo pseudocodice,

2. discutere la complessità dell'algoritmo proposto.

Esercizio 2 (Punti 10). Data un vettore 5' = [ai,a2,.,. ,a.n] di n uiteri, considerate il
problema di determinare una sequenza o- di indici z'i <ìz < -.. im tali che S[ii} > S^} >
. . . 5'[?'rn,] e di lunghezza m massima. Descrivere un algoritmo per determinare m e cr. Dis-
cutere il costo computazionale in tempo e in spazio della soluzione proposta.
Esempio: 5'= [1,12,3,7,8,2], o-- 12,3,2 o cr •= 12,8,2 e m =3.
Esercizio 3 (Punti 8). Si disegnino due foreste binomiale Fi e -Fa di 11 e 5 nodi, rispettiva-
mente. Inoltre, di quanti alberi binomiali consiste la foresta F == -FI U-F27 Inoltre, descrivete
ad alto livello l'operazione Consolidate definita per riutilizzare uno heap di Fibonacci.
 COGNOME NOME

Prova di Algoritmi e Strutture Dati II

Non si possono consultare ne appunti ne testi
Ili appello
09 Settembre. 2009

Esercizio l (Punti 10). Sia dato il grafo G =: (V, E), non orieutato, i cui archi sono pesati
secondo la funzione peyo w : E —* 'St. Sia w(r) il costo dell albero T di copertura di costo
minimo di G. Si cousideri ora il grafo G . G difi'erisce da G solo per il costo degli archi. Il peso
di ciasciin arco in G e' ottenuto dal peso dello stesso arco in G aggiuiigendo un costo fisso A.
Precisamente, Ve 6 -E' w'(e) =- w[e) + A. Progettare mi algoritmo per calcolare l'albero di
copertura di costo minimo ili G . Descrivere la complessità dell'algoritmo proposto. Discutere
l'[Link]à della, soliizione proposta.
Esercizio 2 (Punti 10). In un grafo [Link] e pesato G, im sofctoinsieme degli archi è detto
univoco se non contiene 2 o più archi uscenfci dallo ytesso nodo. Si conyideri il probleiiia di
trovare un iiisieme univoco A di archi di G di peso massimo.
l. Dare iiu algoritnio greedy per risolvere tale problema. L'algoritmo proposto trova, la
soluzione ottima?
2. Valutare la complessità in tempo della soliizioiie.
Esercizio 3 (Punti 10). Dato un intero K ed im insieme A di 2n iiiteri ai,a.2,.. .,a2n, deter-
minare, se esiste, un sottoinsieme SOL di A tale [Link], o- == A' Sa^SOL °•• Progettare per
risolvere questo problema;
l. una procedura Pascal-like polinomiale iion determiiiistica,
2. una procedura Pascal-like deterministica enumerativa.
 Prova di Algoritnii e Strutture Dati II
Non si possono consultare ne appunti ne testi
IV APPELLO
11 Febbraio 2009

Svolgere a scelta due fra i seguenti esercizi:

Esercizio l. (punti 15) Consideriamo un vettore di interi X. Un sotto-vettore d.i X e otteimto
da X cancellando aldini elementi di X. Un sotto-vettore decrescente di X è un sofcto-vettore.
di X i cui elementi, visitati ili ordine crescente di indice, hanno valori decrescenti. La
lunghezza di iin [Link]-vettore è il numero di elementi che lo compongono. Dato il vettore
X == X[l], X[2],... ,X[N\, trovare la luiighezza del sotto-vettore decrescente di lunghezza
massima.

l. Descrivere l'algoritino proposto. (Suggerinient.o: Dare iin'equazione di ricorrenza per

deterniinare la luiighezza di iin sotto-vettore decresceiite).
2. Valutare la complessità dell'algoritino proposto.
Esercizio 2. (punti 15) Dato un grafo orientato G == (V, E) ed un intero h < |V , considerate
di voler trovare l'iiisieme dei vertici di G a distanza. < h.
l. Descrivere in pseudocodice l'algoritmo proposto.
2. Valutare la complessità dell'[Link].
Esercizio 3. (punti 15) Sia G un grafo non orientato, pesato e sia T un albero di copertura di
costo minimo di G. A G è. aggiunto un iiuovo vertice v e l'insieine dei nuovi archi incidenti a
v, ottenendo cosi il grafo G'. Progettate un algoritmo per trovare il nuovo albero dì copertura
T' di G'.
l. Descrivere l'algoritnio proposto.
2. Valutare la. complessità dell'algoritino proposto.

^^eóxoà®ó^^OOà^A^^T&9^so©[Link]ì,à@HTOo^^^©^^,^, A-Ya?^^-^i®<,snoSs^o
 Prova di Algoritmi e Strutture Dati I
Non si possono consultare ne appunti aé testi
II appello

10 Febbraio 2009

Esercizio l. (punti 10) Determinate per qiiali valori di a. e 6 il limite [Link] della ricorrenza
T{n) = a.(?ì/?»]+??, supera quello della ricorrenza T(n) == 3T(rì./3)+n2. Applicando il principio
di ìndiizione, verificare la soluzione dell'equazioue di ricorrenza T(n) = 3T{n/3) + n2.
Esercizio 2. (punti 10) Sia S' un insieme di n = qk mteri, suddivisi in k vettori Si,Sy:,..., Sk,
ciascuno contenente q interi e tali che gli interi in Si precedono tiitti quelli in 5';-i-i, con
l <i< k- l. Progettate un algoritmo ottimo per ordinare 5'. Si discuta l'ottiinalità della
soluzione proposta.

Esercizio 3. (punti 10) Sia G = (V, E) un grafo non orientato i ciu nodi possono essere rossi
o verdi. Progettate un algoritmo che conti i nodi rossi in G e determini se il sottografo dei
soli nodi rossi è coiinesso.
o'
»°ùS-b@Z2¥- yLk^-L«y2^ÈLvVO<b.!.aBkU:<te@°2R.é<tl^i-<@'tl-1àa(?<@(?$^~XTéù^^à?g?<SCD?Cl-Iiì-»

Prova di Algoritmi e Strutture Dati I

Non si possono coiisiiltare ne appzuiti ne testi
IV appello
29 Giugno 2009

Esercizio l. (punti 10) Scrivete iin algoritnio divide-et-impera

• la cui complessità in tempo sia esprimibile da un'equazione di ricorrenza a partizioni
bilanciate,
• il cui lavoro di ricombmazione sia 0(n2),
• e che richieda, nel caso pessimo, tempo 0{n2'logn).
Esercizio 2. (punti 10) Dato un vettore A di dimensione n, progettate iin algoritmo ricor-
sivo per il calcolo del massimo in A la cui complessità in tempo, nel caso pessimo, sia
espressa dall'equazione di ricorrenza T{n) == ST(^) + Q(l). .Discutere l'ottimalità in tempo
dell'algorifcmo proposto.

Esercizio 3. (punti 10) Dato un max-heap H din interi, progettate un algoritmo per ordinare in
senso crescente gli iiiteri in H. Tale algoritmo deve richiedere al più 0(1) memoria aggiuntiva.
Discutete la complessità in tempo della soluzione proposta.

}
?JL ENTER LANGUAGE = PCLXL
HP-PCL XL;l;l;Comment Copyright Artifex Sofware, I
o

Prova di Algoritmi e Strutture Dati I

Non si possono consultare ne appunti ne testi
Appello straordinario per fuori corso
5 Aprile 2006

Esercizio l. (punti 8) Progettare un algoritmo divide-et-impero, che, dato un vettore di O e l,

determini se il vettore contiene pili O che l.
(punti 2) Descrivere a parole la struttura dell'algoritmo di risoluzione
(punti 4} Dare lina realizzazione dell'algoritmo in pseudocodice
(punti 2) Valutare la complessità in tempo dell'algoritmo spiegando il risiiltato indicato. Discutere
i'[Link]à in tempo dell'algoritmo proposto,
Esercizio 2. (punti 12) Dato un grafo orientate G = (V,E}, un pozzo è un vertice con nessun
arco uscente ed esattamente \V\ - l archi entranti, lino per ogni vertice.
(punti 2) Si dimostri che, se esiste, il pozzo è unico.
(punti 4) II grafo G è rappresentato mediante il vettore di adiacenza. Scrivere una procedura in
pseiidocodice per trovare, SG esiste, il pozzo in G e valutarne la complessità in tempo.
(punti 6) II grafo G è rappresentato mediante matrice di adiacenza. Scrivere una procediira in
pseiidocodice con complessit'a 0(|V|) per trovare, se esiste, il pozzo in G.
Esercizio 3. (punti 4) Calcolare la complessità in teinpo nel caso pessimo del segiieate algoritmo
ricorsivo:

function Pippo (n);

begin
if (n < 4) then return 1;
x := Pippo(LfJ);
i :== l;
while i < n do begin
3 := l;
while j < n do
J :=J*5;
i := i + 4;
end
l:=Pippo([fJ):
return (x + y)
end

Esercizio 4. (punti 6) Dato un albero binario di ricerca T, siano a, 6 due interi memorizzati in
T. Trovare tutti gli interi in T compresi fra a e 6,
(punti 4) Dare una realizzazione dell'algoritmo in pseudocodice
(punti 2) Discutere la complessità in tempo dell'algoritmo proposto.
 COGNOME NOME
Prova di Algoritmi e Strutture Dati II
Non si possono [Link] ne ap])iinti ne testi
I appello
8 Giugno 2005

Esercizio l. Eseguire l'algoritmo di Dijkstra per calcolare i canunini niinimi con sorgente
liei vertice l nel grafo di Figura l. Si discuta la complessità in tempo dell'algoritino, a] variare
della struttura ciati utilizzata nell'iniplementazione (coda FIFO. Heap).
4
2 3
8

2 3 12
2

5
2

Figure 1:

Esercizio 2. Codificare con i codici di Hiiffmaii'la [Link] sequeiiza "COMPITO CORTO".

La codifica ottenuta e. uiiica? Qual e.' il rispcu'mio riiipett.o uiia codifica ASCII? Qual e' una
condizioiie. suflìciente affiiiclié la [Link].a sia unica?

Esercizio 3. Si considerino 3 oggetti con uigoiiìbro A-i = l,fc-j == [Link] ^ 2 e. valori ri =;

5, ('2 =- 17, t'3 == 20. Si deterniini la soluzione, ottiina del problenia dello zaino 01 (zaino intero)
con ripetizioni di merci e dimensione M =11. Si discuta la complessità dell'algoritrno di
prograiniiiazioiie dinamica con [Link] si è trovata la soluzione. Qual è l'occupazione di niemoria
dell'algorituio?

Esercizio 4. Scrivere una procedura enumerafciva che, dato un jiisieme di interi S =-

{ai.u^,... ,a,>}, stampi tutti i sottouisiemi X eli 5'.
Esercizio 5. Calcolare secoiido la procedura di Knuth-Morris-Pratt il vettore NEXT per il
segiiente pattern; 01100011.

Esercizio 6. Si consideri i) grafo orientato pesato G = (V,E}, con V = (1,2,3,4) e.

E == {(l. 2; l), (l, 3; 4), (3, 2; 2), (3,4; 3), (4.1; l)}, ove ogni arco è rappresentato dalla tema
(sorgente, destinazione; peso). Si cletermuii coli l'algoritmo di FIoyd-\'\''arshaU, per ogni cop-
pia di vertici di G il costo del cammiiKi di peso minimo.
 Prova di Algoritmi e Strutture Dati II
Non si possono consultare ne appunti ne testi
Ili appello
6 Settembre 2005

Esercizio l. (punti 9) Dato un grafo orientato senza cicli (DAG) G (V, E), trovare il cammino
con il maggior numero di archi in G
l. Descrivere a parole la struttura dell'algoritino di risoluzione
2. Dare una realizzazione dell'algoritmo in pseudocodice
3. Valutare la complessità dell'algoritmo apiegando il risultato indicato.
Esercizio 2. (punti 9) Sia G = {V, E) un grafo onentato nel quale ogni arco (u,'u) e £' ha
un valore associato r(u,'u), che è un numero reale nell'mtervallo [0, l]. Sia r[u,v) il grado di
afBdabilità deU'arco (u,'u). In particolare, se r(u,v} = O l'arco è totalmente affidabile, mentre
se r(u,v) = l l'arco è totalmente maffidabile. Trovare il cammÌBo in G più affidabile tra due
vertici dati x,y ^.V.
l. Descrivere a parole la struttura dell'algoritmo di risoluzione
2. Dare una realizzazione dell'algoritmo in paeudocodice
3. Valutare la complessità dell'algoritmo spiegando il risultato indicato.
Esercizio 3. (punti 4) Si risolva il problema dello zaino reale con uno zaino di capacità M == 12
considerando 4 oggetti con ingombro fci == 10, fez = 3,fcs = 4,A:4 = 14 e valore vi =. 10,1)2 =
30,V3=36,'U4==28.
Esercizio 4. (punti 4) Si calcoli la sequenza più lunga a comune (LGS) fra le due sequenze
X = AABBCDEF e Y = BABBDHE
Esercizio 5. (punti 4) Comprimere la sequenza PECCATOTUTTAPANNA

^
o
 Prova di Algoritm.i e Strutture Dati
Non si possono consultare ne appunti ne testi
IA esonero A.A. 2017-2018

12 Febbraio 2018

Esercizio l. Dati k array ordmati ciascuno di ^ [Link], progettare e dare Io pseudocodice un

algoritmo che imisce i fe array in un unico array ordinato di n elementi in tempo 0(nlog2 A;).
Esercizio 2. Dato un array A ordinato in senso crescente di cardmalità n, e dato un intero k,
con l < fe <n, progettare e dare lo pseudocodice dell'algoritmo per trovare quante volte k
è presente in A. Analizzare la complessità in tempo della soluzione proposta e discuterne
l'ottunalità.

Esercizio 3. Data una tabella Hash di dimensione 11, e data la funzione hash ad indirizzamento
aperto con scaiisione lineare Ai(fc) == h(k)+i mod 11 dove fa'(fc) == fe(A) mod 11, inserire nella
tabella le chiavi: {10,22, 31,4,15,28,17, 88,59} e mostrare la tabella finale.
Esercizio 4. Dato due array A e B ordinati in senso crescente, restituire il minimo elemento e
il secondo elemento m AUB (le chiavi possono essere ripetute in A U B). Progettare e da,re
lo pseudocodice dell'algoritmo e discutere l'ottimalità della soluzione proposta.
•^1
^ l^ì ^ <-^\ é.3
^ AL-J ^^ ^^ <^^ '^.
^^ A^J^
^n
; ^c^^ ^w^^^
^ ' • , ,—c ,-, \ ^-z.^l"
<;JZ,..._....li..J'-5:-fc? -^^- nc A,.-,^ ^ ^"-1
0^3 ^ ^ ^ /L-o
—^ [/ -A

u--^ ^CC

^,^y^r
Qì^ ^3^^--
\T^it^^^)
C> ^-TA.-^
^^y^:^^')
'y^^^^^r fc"
^i!iA-!>U-^ f - ^}
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
ID esonero A.A. 2017-2018
12 Febbraio 2018
Esercizio l. Dato un albero binario di ricerca T, realizzato con puntatori, e dato il puntiatore
al nodo x che memorizza la chiave fe(a;), progettare un algoritmo per trovare il successore /
di x in T, cioè il nodo che contiene la chiave che segue k(x) iiell'insieme ordinato delle \/
chiavi memorizzate ìa T. Discutete la correttezza dell'algoritmo e la complessità in tempo
dell'algoritmo.

Esercizio 2. Sia dato un insieme A di n interi, ciascuno compreso fra l e n (ossia, per ogni
l <i<n, l < A[i] < n). Si progetti in pseudocodice un algoritmo per ordmare A la cm
complessità in tempo sia minima. Discutere la complessità in tempo dell'algoritmo proposto.
L'algoritmo proposto è in piace (sul posto)7 Motivare la risposta. ./K/3 (Spt-^-c^t-y ?-siJS~
Esercizio 3. Dati due array ordinati A e B ciascuno di n elementi e una chiave k, contare ^.^^-^-
quanti sono complessivamente gli elementi mmori o uguali [Link]-AeB. Progettare e dare lo
pseudocodice di un algoritmo che risolve il problema. Si discuta la complessità della soluzione

Esercizio 4. Progettare e dare Io pseudocodice dell'operazione di estrazione di una chiave da

una Pila (Stack). Descrivere come è implementata la pila e discutere la complessità della
soluzione.

^<f f-
.0
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
IB esonero A.A. 2017-2018
12 Febbraio 2018
Esercizio l. Dati due aiin-heap Jfi e ffz di "l e ng elementi ciascuno, memorizzati in un unico
array H. Precisamente, -firi è memorizzato nelle prime n\ posizioni, e Hy, nelle posizioni
successive, ossia da ni +1 a ni 4- n2- Progettare e dare lo pseudocodicedeU' algoritmo che
richiede tempo 0{logy,n} per creare un nuovo heap H con n = ni +02 elementi.
Esercizio 2. Dato un albero binario di ricerca T, realizzato con puntatori, e dato il puntatore
al nodo x che memorizza la chiave fc(a;), progettare e dare lo pseudocodice dell' algoritmo
per trovare il predecessore di x in T, cioè il nodo che contiene la chiave che precede k{x)
nell'insieme ordinato delle chiavi memorizzate in T. Discutete la correttezza dell'algoritmo e
la complessità in tempo dell'algoritmo proposto.
Esercizio 3. Sia A un array, indicizzato daO a n- l. Per O <i ^j, sia A[i} == 2i. Per j +1 <
i < n—1, sìa. A[i] = 2i +1. Determmare j l'indice massimo per cui A[j] = 2j. Progettare
e dare lo pseudocodice dell'algoritmo che risolve il problema. Analizzare la complessità in
tempo della soluzione proposta. Discutere la complessità.
Esercizio 4. Data una tabella Hash di dimensione 11, e data la funzione hash ad indirizzamento
aperto con scajisione hi{k) = A'(fc) + i2 mod 11 dove fa'(fc) = h(fc) mod 11, inserire nella
tabella le chiavi: {10,22, 31,4,15,28,17,88, 59} e mostrare la tabella finale.

^^"^i-^. ^
^ ye^
^-cU
oo k Gè X'T4- ^
y^
~0 ^ ^- '^)

o l z_2-+^-^
~!s\
@ST5?Irl4^
^ 4^''' .l)^ ^^-
»r^l-^ft^>
A

l ^rA^''r<j
a^/^Q'
@S1
^ ,^t:^ ^-^ ^ CL
uu7^^^ ^ ,/fc^Ì
^7c^ —l 2 7'^ ^
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
1C esonero A.A. 2017-2018
12 Febbraio 2018
Esercizio l. Dato un inin-heap H di dimensione n ed una posizione k, progettare un algoritmo
che sostituisce ad H[k} la chiave H[k] — c e riordina, se necessario, lo heap. Discutere la
complessità in tempo dell'algoritmo proposto, con c > 0.
Esercizio 2. Dato un albero binario di ricerca T, realizzato con puntatori, e data la chiave k, pro-
gettare e dare lo pseudocodice dell' algoritmo per inserire la chiave fc nell'albero T. Discutete
la correttezza dell'algoritmo e la complessità in tempo dell'algoritmo proposto.
Esercizio 3. Sia dato un iasieme A di 2n interi, ciascuno compreso fra l e n (ossia, per ogai
l < i < 2n, l < A[i] < 2n). Determinare per ogni valore j e [l :n], quanti sono gli interi in
A con valore < j. Progettare e dare lo pseudocodice dell'algoritmo, discutere la complessità
in tempo e l'ottimalità.
Esercizio 4. Data una tabeUa Hash di dimensione 11 con liste di trabocco, e data la funzione
hash h'(k) == h(fc) mod 11, inserire nella tabella le chiavi: {10,22,31,4,15,28,17,88,59} e
mostrare la tabella fmale.

.».
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
Ili C esonero A.A. 2017-2018
7 Maggio 2018

Esercizio l. Dato un grafo C ^ (V, E) orientato, progettare un algoritmo per trovare il grafo
aumentato 6'4 = (1^, fi'4) in cui esiste un arco per ciascuna coppia di vertici (•i,j) tali che la
distanza fra i e j è&\ più 4 in G, ossia tali che d(i,j) ^ 4. Discutere la soliizione proposta e
discutere la complessità in tempo della soluzione proposta.
Esercizio 2. Dato un grafo orienfcato G = (^,^) e pesato io : £'—» R e dato un vertice v E V,
scrivere un algoritmo per calcolare i cammini di peso niinimo con destinazione v, ossia il peso
del cammino mininio da -u a v, per ogui vertice u e V. Dare la complessità dell'algoritmo
proposto.

Esercizio 3. Dato un grafo non-orientato G = {V, E), scrivere lui algoritmo per verificare se esiste
mia componente connessa in G di dimensione almeno ^. Discutere la complessità in tempo
dell'algoritmo proposto.
 Prova di Algoritmi e Strutture Dati
Non si possono consiiltare ne appunti ne testi
II F esonero A.A. 2015-2016
24 Maggio 2016
Esercizio l. Dato im grafo orientato G =: (V, E} s uii vertice s £ V, trovare il iiodo t e. V
a distanza iiiassiina da s. Progettare un algoritaio per risolvere tale problenia. Si dia lo
pseudo-codice dell'algoritino e se iie discuta la coiiiplessità. in tenipo e spazio. Si uoti che il
gTafo lion è pesato.
Esercizio 2. Dato un gTafo G = (V, E; w) orientato e pesato con w : B^ R,e dato un intero
''' $ l ^ 11 progettare uii algoritino per trovare, se esiste, uà ciclo di costo negativo composto
da al più r eu-clìi. Dare il codice dell'algoritnio ili C. Discutere la coniplessità in tenipo della
sotuzioiie proposta.
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
Ili A esonero A.A. 2017-2018
7 Maggio 2018

Esercizio l. Dato un grafo G = {V, E) non orientato, i cui archi hanno peso w(e) = {-1,0,1},
progettare un algoritmo per trovare l'albero di copertura T di costo minimo. Discutere la
soluzione proposta e discuterne la complessità in tempo. Inoltre, provare o confutare le
seguenti aft'ermazioni sotto le ipotesi dell'esercizio:
l. Tutti gli archi di costo negativo soiio in T.
2. Il costo di T c minore di \V\.
Esercizio 2. Dato uu grafo orieiitafco G = {V, E}, scrivere lui algoritmo che ritorna true se il
grafo contiene un ciclo e false diversamente. Studiare la complessità in tempo dell'algoritmo
proposto.

Esercizio 3. Dato un grafo non orientato G == {V, E), scrivere mi algoritmo per determmare il
grado niedio di G. Studiare la coniplessità in tempo dell'algoritmo proposto in funzione della
rappresentazione utilizzata per G.
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
Ill B esonero A.A. 2017-2018
7 Maggio 2018

Esercizio l. Dato un grafo orientato e aciclico G -^ [V, E) pesato -tu : £'-> R, e dato una sorgente
$ € V, progettare un algoritmo per trovare i cammini di costo minimo da s verso tutti gli
altri vertici in V. Discntere la soluzione proposta e discutere la coniplessità in tempo della
soluzione proposta. La soluzione proposta è ottima? Motivare la risposta.

Esercizio 2. Dato vai grafo orientat.o G = (V, E), con. |£| = 2 V], scrivere un algoritmo per
calcolare il grafo trasposto di G, Dare la complessità in tempo dell'algoritmo proposto e
studiare come varia l'algoritmo al variare della rappresentazione utilizzata per il grafo.

Esercizio 3. Dato un grafo non [Link] G == (V, E) c dato un vertice v 6 V, scrivere un algoritmo
per trovare il nodo w 6 V più lontano da v. Discutere la complessità in tempo dell'algoritmo
proposto.
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti uè testi
II C esonero A.A. 2012-2013 30 Gemiaio 2013
Esercizio l. Un array A conteneiite n interi ordiuati in senso cresceut.e è ruotato ciclicamente
verso destra, di k posizioni. Progettare un algoritmo per determiuare il valore di k. Dare la
descrizione dell'algorltmo in pseudo-codice e discutere l'ottimalità della soluzione proposta
utilizzando le tecuiche viste a lezione per valutare la complessità iiitrinseca di mi problema.
Esempio. Input: n==6 e A == [3,5,7,8, l, l], Output: fc = 2.
Esercizio 2. Dato un min-heap H di n [Link], progettare un algoritino per incrementare di
6, con S > 0, la cliiave m posizione k nello heap. Dare la descrizione in pseudo-codice
dell" algoritmo e discutere la complessità della soluzione proposta. Discutere la complessità
della stessa operazione quando lo heap H ha la forma di un albero d-ario, con d ^ 3.
Esercizio 3. Siano A e B due vettori ordinati di n interi. Progettare un algoritmo per trovare
l'elemento di raiigo 4 nell'insieme AUB. Dare la descrizioae in pseudo-codi(;e dell'algoritmo
proposto e discutere l'ottimalità della soluzioae proposta.
 Prova, di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
II D esoiiero À.A. 2012-2.013 so Gennaio 2013
Esercizio l. Dato un insieme ordinato di n interi, i cui valori sono nel range l e n— l ed appaiono
tutti almeno lina volta in A, trovare l'intero g duplicato. Progettare lui algoritmo per risolvere
il problema, dame la descrizione in pseudo-codice e discutere l'ottimalit.à della soluzione
proposta utilizzando le tecuiche viste a lezione per ^'aiutare la complessità intriuseca di un.
problema.
Esempio. Input: n=6 e A=- [l, 2, 2,3,4,5]; Output: g = 2.
Esercizio 2. Dato uu inax-heap H di n. elementi, progettare uii algoritino per trovare l'elemento
di rango 4 in H. Dare la descrizione in pseudo-codice dell'algoritmo e discufcere la complessità
della soliizione proposta. Discutere la complessità, della stessa operazione quando lo heap H
ha la forma di uii albero d-ario, con d > 3.
Esercizio 3. Sia A un vettore di n interi, ciascuu nell'inter-rallo [l, n3]. Progettare uii algoritmo
per ordiuare A, darne la dcscrizioiie in pseudo-codice e disciitere. l'[Link]à della soluzioue
proposta.
 q

Prova di Algoritmi e Strutture Dati

Non si possono consultare ne appunti ne testi
Il A esonero A.A. 2012-2013
30 Gennaio 2013

Esercizio l. Dato un insieme A ordinato di n mteri ael range {1,2,3}, trovare l'intero q con il
maggior numero di occorrenze m A. Progettare un algoritmo per risolvere il problema, darne
la descrizione in pseudo-codice e discutere l'ottimalità della soluzione proposta utilizzando le
tecniche viste a lezione per valutare la complessità intrinseca di un problema,.
Esempio. Input: n=6 e A = [1,1,2,2,2, 3]; Output: q=1.
Esercizio 2. Dato un max-lieap H di n elementi, progettare un algoritmo per iuserire in H una
nuova chiave k. Dare la descrizione m pseudo-codice dell'algoritmo e discutere la complessità
della soluzione proposta. Discutere la complessità della stessa operazione quando lo heap H
ha la forma di un albero d-ario, con d > 3.
Esercizio 3. Dato un vettore di n interi tutti distinti, progettare un algoritmo per modificare
quicksort in modo che possa essere eseguito in tempo 0(n log n) nel caso peggiore. Dare la
descrizioue in [Link] dell'algoritmQ e motivare la coinplessità della soluzione proposta.
 s

q^°Lkll=L©VO%ùÉ8
X4°Lk^L^)%<LÉW
"•OLklLL@@°£RL

Prova di Algoritmi e Strutture Dati

Non si possono consultare ne appunti ne testi
II B esonero A.A. 2012-2013 àoGemiaio 2013
Esercizio l. Dato uu insieme A di n numeri interi, ordinato in senso crescente, ed uii reale fe,
trovare l'indice a; in -A tale che la differenza fra A[x] e fc sia [Link] in valore assoluto, ossia
x == arg miuKKn |A[f] — A|. Progettare un algoritmo per risolvere il problema, darne la
descrizione in pseudo-codice e discutere l'ottimalità della soluzioiie proposta utilizzando le
teciiiche viste a lezione per valutare la complessità intrinseca di iin problema.
Esempio. Input; n = 6, A= [1,3,5,7,8,10] e A; = ^.: Output: A[3] = 5.
Esercizio 2. Dato un max-heap H di n elementi, progettare un algoritmo per incrementare di
ù, coil 5 > 0, la chiave in posizioae k nello heap. Dare la descrizione in pseudo-codice
dell'algoritmo e discutere la complessità della soluzione proposta. Discutere la complessità
della stessa operazione quando lo heap H ha. la. forma di un albero d-ario, con d ^ 3.

Esercizio 3. Progettare un algoritmo per ordinare n interi nell'mtervallo [a, 6j, con. b—a+l<n.
Dare la descrizione in pseudo-codice dell'algoritmo e discutere la complessità della soluzione
proposta.
 p LEg¥ggRLASgQHè§E= =Pg£^XL
) ) H®P PEGLXXI;, 3.^ ?.} CTBre®it].t CQggys-È^t ^Cfcia-f:^x Ss^g^^i^ , li

Prova di Algoritmi e Strutture Dati

Non si possouo consultare ne appunti uè testi
II C esonero A.A. 2013-2014
21 [Link] 2.014
Esercizio l. Sia data una matrice r x c di interi in cui gli elementi di ogiii riga e di agili coloiina
soiio ordinati iu seiiso crescente. Si progetti uà algoritmo divide-et-impera per determinare se
un dato iiitero k e contenuto nella matrice. Dare la descrizione dell'algoritmo in pseudo-codice
e discutere la complessità dell'algoritmo proposto.
Esercizio 2. Siano dati n insiemi 5i,52,... ,5'n che coiitengouo m chiavi ciascuno. Le chiavi
ili Si precedono quelle in 5i+i, eoa l <i <. n-1. Progettate, un algoritmo per ordinare
5 == (J?=i •S'i- Date la descrizione in pseudo-codice dell'algoritmo e discutete l'ottimalità della
soluzione proposta.

Esercizio 3. Sia A im vettore di n interi, ciascun nell'intervallo [l, n2]. Progettare un algoritmo
per ordinare A, darne la descrizioiie in pseudo-codice e discutere l'ottimalità della soluzione
proposta.

-|ÌI?o@©q=)]'S{T:oA_
M3?%@n^snoA<3:
L
8a?%oA@^Ti^no^©
o- - - -AO>®3f-Sno®3fTO°-l^'?o@©n]^rIo4n
! a?%o<C@iTlJ,-e.-« ©oAÒoe^-iAOA^QÓ^Bd •8 AEf@SAe
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
II A esonero A.A. 2013-2014

21 Gennaio 2014

Esercizio l. Si coiisideri un insieme A di n record. Ciascun record ha una chiave primaria key
che pilo assumere i solo valori {ROSSO, VERDE, BIANCO }. Si vuole ordinare l'insieme in
tempo 0 (n) in modo che tutti gii eleuieati con chiave VERDE precedaiio tutti gli elementi
con chiave BIANCO, che a. loro volta devono precedere tutti gli elementi con chiave ROSSO.
Le uniche operazioni permesse sui record sono l'[Link] delle cliiaw, e lo scambio di due
record. Progettare un algoritino per risolvere il problema, darne la descrizione in pseudo-
codice e discutere l'ottimalità della soluzione proposta utilizzando le tecniche viste a lezione
per valutare la complessità intrinseca di un problema.
Esempio.
Input: Tz=4 e A= [{y,rl},{Ar2},{y,7-3},{B,r4}];
Output: A' = [{l/',rl},{7,r3},{5,r4}, {-R,r2}].
Esercizio 2. Dato un inax-heap H di il eleinenti e l'indice k, progeUare un algoritmo per sostituire
H[k] con H[k} -10 e ripristinare le proprietà dello heap. Dare la descrizione in pseudo-codice
dell'algoritmo e discutere la complessità della sohizione proposta. Discutere la complessità
della stessa operazione quando lo heap H ha la forma di un albero rì-ario, con d == [loggnj.
In quale dei due heap (heap binario o heap d-ario) è [Link] esegiiire l'operazione?
Esercizio 3. Dato un vettore A di n interi tutti distinti, si ha iin'inversìoue tra gli elementi A[i}
e A[j] se i < j e A[i] > A[j}. Progettare un algoritmo che modifica inergesort per contare
in tempo O (n. log n) il numero totale di iiiversioni presenti in A, Dare la descrizione in
pseudo-codice dell'algoritmo e motivare la complessità della soluzione proposta.
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
II C esonero A.A. 2015-2016
24 Maggie 2016
.Esercizio l. Si consideri un grafo non orieiitato e pesato G (V, E) e un albero di copertura TQ
di costo miiiiiiio per tale grafo,
• Descrivere un algoritmo per calcolare TQ oveG" == (VUt,E' = £'U{(it,u;ii.i(t,u))|u e 7}.
Dare lo pseudocodice di tale algoritmo e trovare la complessità dell'algoritmo proposto.
• Descrivere un algoritmo per calcolare T'Q ove G' è ottenuto da G sommando a ciascun
arco una data costante c < 0. Dare lo pseudococlice di tale algoritnio e trovare la
complessità dell algoritmo proposto. Discutere l ottimalità della soluzioiie.
Esercizio 2. Sia & e Ne siaG— (V,E;w] mi grafo orientato e pesato con w : E —^ {—b,b}.
Trovare i caroniini miuimi dalla, sorgente s e V a tutti gli altri vertici m G. Dare il codice
dell'algoritnio in C. Discutere la complessità in tenipo della soluzione proposta.
 Prova, di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
II B esonero A.A. 2013-2014
21 Gennaio 2,014
Esercizio l. Siano dati due vettori A e B contenenti n interi ciascuno e ordinati in seiiso crescente.
Sia dato inoltre iin iiitero A:, con l < fe < [log; ni. [Link] l'elemeato di rango k in AUB.
Progettare un algoritmo per risolvere il problema, darne la descrizione in pseudo-codice.
Studiare la complessità della soluzione proposta e discuterne l'ottimalità.
Esercizio 2. Siano dati due max heap H^ e Hy. Si vuole construire l'insieme 5 ordinato in senso
crescente delle chiavi in H} U fì'a- Progettare l'algoritnio per risolvere il problema, darne la
descrizione in pseudo-codice. Stiidiare la complessità della soluzione. E' possibile risolvere il
problema in 0(n), dove n = \HI\ + \Hiì\'?
Esercizio 3. Dato un grafo orientato G = (V, E), descrivere l'algoritmo per la visita iu profondità
di G. Tale algoritmo deve essere modificato ia modo da restituire per ciascuu arco 11 suo
tipo. Progettare un algoritmo per risolvere il problema, darne la descrizione in pseudo-codice
e discutere l'ofctimalità Discutere la. complessità della soluzione proposta in teinpo ed in. spazio
al variare della rappresentazione utilizzata per G.
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
II E esonero A.A. 2015-2016
24 Maggio 2016
Esercizio l. Dato un gTafo orieiitato G = (V, E), progettare HII algoritino per deteniiinEire se il
grafo è un DAG. Discutere la coiiiplessità in tenipo della soluzione proposta. Discutete poi
qiiale algoritiiio, fra quelli visti a lezioni, applicliereate per calcolare i cammiiii ininimi da
[Link] siiigola s G V su uii DAG.
Esercizio 2. Sia dato a. £ N, e uii grafo G == {V,E\w) òrieiitato, pesato con w : E —t [l, a] e con
1/1 =: T).. Progettare uii algoritnio per trovare i caitiiiiuii iniiùnii dal vertice fl e V a tutti
gli altri vertici. Dare il codice dell'algorifctiio ili C. Discutere la coniplessità in tenipo della
soluzione proposta.
 Prova di Algoritmi e Struttiire Dati
Non si possono consultare ne appunti ne testi
II D esonero A.A. 2015-2016
24 Maggio 2016
Esercizio l. Dati un insieme S di n interi {ai, 02,..., an}, ciascuno con peso u,, con l < i <n,
e dato uà intero W, si vuole determiuar^^òttoinsieme T C S dì somma inassinia e somuia
dei pesi minore od [Link] a W. Si dia lo pseiido-codice dell'algoritmo e se ne discuta la
coiuplessità ili tempo e spazio. Si giustifichi la correttezza dell'algorifciito, ossia si giustifichi
perché l'algoritiiio trova l iiisieme T di somiiia massima.
Esercizio 2. Dato un grafo G = (V,E;w) orientato e pesato con w -.E -^ R+ e\V\-= n,
progettare un algoritmo per trovare per tutte le coppie di vertici (uii'u:;) £ V il caniraino di
peso uiinimo che attraversa al più log'a n archi. Dare il codice dell'algoritmo in C. Discutere
la coiiiplessità ili tempo della soluzione proposta.
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti uè testi
II B esonero A.A. 2015-2016
24 Maggio 2016
Esercizio l. Sia dato uu gTafo G = (V, E) i cui archi sono eticliettftti {R,V,B}. Progettare uu
algoritiuo per verificai'e se esiste uiia coniponente coiiiiessa i cui archi sono tutti eticliettati
R. Discutere la coinplessità in teiiipo dell'[Link] proposto.
Esercizio 2. Sia. dato un grafo orlentato e pesato G = (V,-E; w) con w : E -^ R (pesi qualsiasi).
Inoltre sia [E\ = 2|V|, ossia G è uu [Link], Progettare un algoritiuo per calcolcire i cam-
iiiiiii miniiui fra tutte le coppie. Dare il codice dell'algoritiiio ui C. Discutere la complessità
ili tempo della soluzione proposta, Si faccia particolare atteiizioae a scegliere l'[Link] più
efficiente per il problema da risolvere.
 Prova di Algoritmi e Strutture Dati
Non si possono conyultare ne appuut.i ne testi
II A esonero A.A. 2015-2016
24 Maggio 2016

Esercizio l. Sia A un array ordinato che contiene N interi liei raiige [Ar,2JV —2.1 [Link] in A
soiio tutti distiiiti, traiine lili valore che è ripetuto 2 volte. Progettare un algorifcuio ottimo
per deteniuuare il iminero ripetuto. Valutare la coinplessità iritrinseca del prohlenia.
Esercizio 2. Dato fe £ N e dato un grafo G = (V,£';w) orientato e pesato w : E —^ R~t, pro-
gettare un algoritmo per deteniiinare i cammini ininimi fra ogiii coppia di vertici in G coiila
condizione aggiuntiva che ciascun canimino può attraversare al più h vertici iiiteniiedi. Dare
il codice dell'algoritmo in C. Discutere la coinplessità in tempo della soluzione proposta.
 ?

Prova di Algoritmi e Strutture Dati II

Non si possono consultare ne appunti ne testi
IV appello

27 Settembre 2005

Esercizio l. (punti 9) Dare un algoritmo efficieiite per trovare la lunghezza (numero di archi)
di uu ciclo di peso negativo di lunghezza minima all'interuo di uii grafo. In particolare:
l. Descrivere a parole la struttura dell'algoritmo di risoliizione
2. Dare una realizzazione deU'algoritmo in pseudocodice
3. Valutare la complessità dell'algoritmo spiegando il risultato indicato.
Esercizio 2. (punti 4) Tra le seguenti lezioni che condividono la medesima aula e che si svolgono
negli intervalli di teinpo indicati accanto, determinare un insieme di lezioni compatibili di
cardinalità i-nassima:

ai = (9,11);02 = (10,12); fl3 = (8,10); a^ = (15, 17); 05 = (16,18); ae = (14,16).

Esercizio 3. (punti 4) Si risolva il problema dello zaino intero coii ripetizioni per uno zaino di
capacità M = 14 considerando 3 oggetti con ingombro &i = 10, fca = 3, ^3 = 4 e valore
U] == 10, U2 = 3, V3 = 6, rispettivamente.
Esercizio 4. (punti 4) E' possibile risolvere il problema dello zaino intero coil ripetizioni con lo
stesso algoritmo usato nell'esercizio precedent.e se i valori degli oggetti sono numeri reaU? e
se i pesi degli oggetti sono numeri reali? (Motivare la risposta).
Esercizio 5. (punti 9) Si consideri una matrice M[ì ...9,1... 9] che contiene iateri compresi fra
l e9 in un sottomsieme S deUe sue posizioni. Il gioco del Sudoku consiste nel riempire
completamente M in modo die:
l. ciascuna riga contenga tutti gli interi fra l e 9, una ed una sola volta,
2. ciascuna colonna contenga tutti gli interi fra l e 9, una ed una sola volta,
3. ciascuna, delle 9 sottomatrici M[3r + l.. .3(r+ l),3s + l.. .3(s+ l)], conO <r < 2e
O < s <2 contenga tutti gli interi fra l e 9 una ed una sola volta.
(I valori già inseriti in M, ossia quelli nelle posizioni di 5', non violano le tré condizioni date).
Scrivere un algoritmo enumerativo per risolvere il problema del Sudoku.
3yC©"^3v 8" p"Q^ÓÙvÓVLù3°CTO@ •-?-Ttl:l^A°%£È 0.'.OLktLL^@°c,Rl-oó-LJE®oùS-JE®<QV- - o- t
]

Prova di Algoritmi e Strutture Dati II

Non si possono [Link] ne appunti uè testi
Ili APPELLO
4 Settembre 2007

Esercizio l. (punti 12) Consideriamo un vettore di interi X. Un satto-vettore di X è ot-

tenuto da A' cancellando alcuni elementi di X. Un sotto-vettore crescente di X f un sotto-
vettore di X i c\\ì elemeati, visitati ili ordine cresceiite di iiidice, haiino valori crescenti.
La. lunghezza di un sot to-vettore è il numero di elenieirti die lo compongono. Dato il vet-
tore X = Jif[l], ^Y[2],.. . ,X(Ar], trovare la lunghezza del sotto-vettore crescente di lunghezza
rnasy iiua.

l. Deycrivere l'atgorltmo proposto. (Suggeriinento: Dare un'equazione di ricorrenza per

determinare la lunghezza, di un sotto-vettore cresceute).
2. Dare una realizzazione in pseudocodice dell'algoritnio propoyto.
3. Valutare la. compleysità dell'[Link].
Esercizio 2. (punti 14) Dato un grafo orieiitato e pesato G = (l/, E} ed un intero l < /i< T/|,
consideriaino i] problema di trovare per agili coppia dei vertici •y.,w £ V il peso mininio di iin
camiiiiao qualsiasi da it a. w conteiiente al pii'i li ardu.
l. DcKCi'ivere a pcU'oIe l'algoritnio proposto.
2. Dare una realizzazione in pseudocodice - ad alt.o livello - dell'algoritnio proposto.
3. Valutare la complessità dell'algoritmo.
Esercizio 3. (punti 4) Come è noto, l'algoritmo di Dijkstra risolve il problema di calcolare i
caiumiiii mininii da sorgente unica. Mostrare, tuttavia, im'eyecuzioue dell'algoritmo di Dijk-
stra sii un grafo orientafco e pesato per il quale l'algoritmo di Dijkstra fallisce.
o^èÈ@oùS^®EK&^8%àEeCr LGr?Lg(&l^@o©RLfió-LB«°ùS?B@o<«0?^? ^l-"J-a®3àgvé^òxC@V@AS@?

Prova di Algoritmi e Strutture Dati I

Non si possono consultare ne appiiiiti ne testi
V appello

4 Settembre 2007

Esercizio l. (punti 12) Dato un grafo G = [V, E), la distanza d(v,w) fra due vertici v e w
è il minimo numero di archi su un caiiiiiiino da v a. w in G. il diametro diam(G') ==
max{d,(v,w)\v,w e V}. Progettare uu algoritmo per determinare il dianietro di G.
l. Descrivere a parole la [Link] dell'algoritmo proposto.
2. Dare una realizxazioiie dell'[Link] in pseiiclocodice,
3. Disictitere la complessità in tempo della. soluzioQC propoyta.
Esercizio 2. (punti 8) Dato un vettore A di il. iiiteri, progettare uii algoritnio che coiitrolla se
A è lili max-heap.

l. Deacrivere a parole l' algoritnio proposto per risolvere tale problema.

2. Dare una i-Ralizzazioue dell'[Link] iu pseiidocodice.
3. [Link] l'ottimalità della yoluzione propoKta.
Esercizio 3. (punti 10) • Provare con il metodo della yostitiizione che T[n) = O(nlogn) è
la soluzione dell'equazione di ricorrenze T(n) = 7'(n/4) +T{2n/3) + 0(?7,logn)
• Scrivere una semplice procedure Dummy la cui complessità ili fcenipo sia T(n) =
3n2 + 7 log li. Provare, applicando la defiiiizione di ordine di grandezza, che T(?ì.) ==
3n2+7logne0(n2).
 Prova, di Algoritmi e Strutture Dati I
Noil si possoiio consultare ne appunti ne testi
II appello

5 Febbraio 2007

Esercizio l. (punti 6) Discutere la complessità di Quicksort nel caso in cui tutti gli elementi del
vettore da ordinare abbiano Io stesso valore.

Esercizio 2. (punti 12) Data lina matrice M di interi di dinieiisione n x n, con n potenza di 2,
si viiole deterniinare l'elemento nuiiimo ili M.

l. Descrivere a parole la struttura di iin algoritmo divide-et-inipera per risolvere tale

proìjlema.
2. Danie una realizzazione dell'algoritmo ili pseudocodice.
3. Discutere l'eqiiazioue di ricorreiiza che descrive la complessità in tempo della soluzione
proposta e trovarne un liniite siiperiore.
4. Discutere l'ottimalità clGlÌEi yoluzione proposta.
Esercizio 3. (punti 12) La larghezza di iin albero radicato è il numero massimo di nodi che
stanno fcutti al medesimo livello.

l. Descrivere a parole la sfcnittura di un algoritmo cha calcola la larghezza di iin albero

radicato.
2. Dare una realizzazione dell'algoritiuo ili pseiidocodice.
3. Disciitere la coiiiplessit.à della soliizione proposta.
A°Lk^<o^ÉL<->°Lk^i°^Èe^°Lk^A°%.È^°Lk^@c°%.É|^Lk^?^Él^°Lk^=^

Prova di Algoritmi e Strutture Dati II

Non si possono [Link] ne appunti ne testi
Ili appello
5 Settembre 2.007

Esercizio l. (punti 15) Consideriamo il segiiente problema: Una ditta dispone di M operai per
eseguire Ar lavori, con M ^ N, e conosce una inatrice T di JV x M interi tale che T[i,j] indica
il tempo necessario per eseguire l'ì-esiino lavoro quando alla sua esecuzioi e sono assegnati
j operai. Una distribuzione degli operai ai lavori è una sequenza ji,J2,... ,ji\' di N interi
positivi, dove j, operai sono assegnati al lavoro i, tale che j\ +J'2 + ••• + 3N == M. Una
distribuzione degli operai deterniina un tempo di [Link] per l'esecuzione degli n lavori
gli Nalavori
pari max{7'dipende
[l,.)i],T[2,7'
dalla2],.. . ,T[N,j,\'}}.degli
distribuzione Chiaoperai
rainent.e, il teinpo complessivo per eseguire
ai lavori.
Deterniinare il mininio tempo di terminazione possibile per J'eyeciizione degli N lavori.
l. Dare una descrizione dell'algoritnio proposto. (Suggeriniento: Dare un'equazionc di
ricorrenza
lavori con per determincoli
m, operai, arelil<n.<Are
minimo [Link]
l < inpo<diAI],
terminazione P[n,m] per eBeguire n
2. Progettare uua realizzazioiie m pyeudocodice dell'algoritnio proposto.
3. Valutare la coniplessit.à dell'algoritmo.
Esercizio 2. (punti 12) Dato Lm intero K ed un inyieuie A di 2n interi 01,03,... ,a.2n, ci si
chiede se esiste iin [Link] SOL di A tale [ [Link] a z.
riyolvere questo problema: E(,g50£ "l $ J<- Progettare per
l. una procediira Pascal-like polinomiale noii determiniHbica,
2. uiia procedura Paycal-like deterniinistica eniimerativa.
Esercivide
zio [Link] (punti
nodo di6)unDeycri vere eil funzi
5-Albero onamento
discutere in qualidelcondizioiii
la, procedura B-Tree-Split-Child che di-
è iiivocata.
 Prova di Algoritmi e Strutture Dati II
Non si possono consultare ne appunti ne testi
V appello
16 Gennaio 2007

Esercizio l. (plinti 12) SiaA == {ai,a.2,... ,[Link]} uninsieinedin numerirealiesia W/unnumero

reale. Si consideri il problema di trovare un [Link] I c {l,..., n} tale che 5' =
£is/ o;' < W/- Per risolvere il probleina, progettare:
l. una procedura in pseudo-codice poUnoraiale non determiiiistica,
2. uiia procedura in pseudo-codice deterministica enumerativa
Esercizio 2. (punti 12) Sia T una matrice triangolare inferiore di dimensione n x n, contenente
interi positivi. Un percorso di T parte seiiipre da T[l, l e finisce in una qualche posizione
dell' ;?.-esiiiia riga. Ad ogni passo del percorso ci si può' muovere o verso il basso rinianendo
Biilla stessa colonna o verso il basso miiovendosi iu diagonale verso destra. In altre parole,
se T[i,j} è una cella su un dato percorso, i suoi possibili successori sono le celle T[i + l;j] e
T[i+l, j+l}- Lungo il percorso si sommaiio gli interi contenuti nelle celle visitate. Progettare
un algoritnio che deteniiini il percorso che ha somma massima. (Sugg. Si calcoli prima la.
somnia massima e poi il percorso seguito)
l. Indicare quale tecuica di programmazioDe si intende usare
2. Dare una. realizzazione in psezidocodice dell'algoritmo proposto.
3. Valutare la. complessità dell'algoritmo
Esercizio 3. (punti 6) Per rendere positivi i costi degli archi nel problema dell'albero di coper-
tura di costo minimo si somma a ciascun arco una quantità positiva, pari al peso negativo il
cui valore assoluto è massimo. Perché la stessa tecnica uon può essere usata nell'algoritmo
di Johnson per trovare i cammini niinimi tra tutte le coppie di un grafo?
 Prova di Algoritmi e Strutture Dati I
Non si possono consultare ne appunti ne testi
VI appello
26 Settembre 2007

Esercizio l. (punti 14) Dato un albero binario T, si progetti un algoritmo per controllare se T
è im albero binario di ricerca.

l. Descrivere un algoritmo ricorsivo per risolvere il problema.

2, Dare una realizzazione dell'[Link] in pseudocodice.
3. Stiidiare la coiiiplessità dsl}:alÉ'oritmo proposto.
4. Discutere l'otfciinalità della soluzione proposta.
Esercizio 2. (punti 10) Si consideri un vettore A di •n interi distiiiti e ordinati in senso crescente.
In posizione i di A, vi è un fc-salto se A[i + l] — A[i} ^ k, con l < i< n—ì, ossia se vi
yoiio due elementi consecutivi in A la cui differenza, è maggiore o uguale a k. Determinare il
A'-salt.o più a sinistra in A.

l. Progettare iin algoritmo basato sulla tecnica di programmazione dh-ite-et-impera per

risolvere il problema.
2. Dare una realizzazione dell algoritmo in pseiidocodice.
3. Studiare la complessità dell'algoritmo proposto.
4. Disciitere l'ottimalità della, soluzione proposta.
Esercizio 3. (punti 6) Risolvere l'equazione di ricorrenza. 'J'(n) == T(?i/2).+ 5, con n'= 2fc, e
 Prova di Algorituii e [Link] Dati I
^7ou si posyoiio coiisultare ne apt)iinti ile testi
I app(:'ll(j
02 Fi-bbraio 2011

Esercizio l. (punti 10) Dato uii intero k e nil vettcjn' ordinatu A di » iiiteri tali che, ycandendo
l'arra.y eia sinisti'ii verso destra, la diferciiza fra due posizioiii coiitigue dell'arrayè sfci'Rttanieiifce
crc'wceiite, ossia A[?1 - A[i — Ij < A[; + l] - .41?'] pRi- 2 < ;: $: n - l, progettare IDI algoritnio
ottiiiia per trovare, se esisfce, la posizione i fcalf che A[i\ — A[t — 1} ^ k. Motivare l'ottiiualit'à
[Link] soluzione.

Esempio: A'==3, A = {1,4,9.14,20.28}, i = 2 poiché A[2] - A[l| = 4 - l - 3.

Esercizio 2. (punti 10) Dato un intero ?' e [l,...,».] o un an'ay A di '» iuteri, selezioiiate gli (
t'le'nicnti i)iù granili ia A. Disciitct.e la coiiiplc'Hsiià dell'algDrifnio proposto al variare di i.
Esercizio 3. (punti 10 ) .[Link]'e e vt'fifìcate per iiicluzi(.)itR la suliizioiif (lell'eqiiazione di ricor-
ft'iiy.n r-lic (.lesc'.rive il teiiipo eli [Link] lici f'aso pessiiiK.) del segtlciit'e tilgoritiiii.):
Pippo l ( r . s ) : int ;
{if r>»
{for (< =1 : ; $|.'1|- !; i++S
For (J-1-4]: .?;"+1; .;--)
if (A[t]>A[j\'ì {scfiinbia ..l[i] fon ,4[./|}
}
else {int t[ == [r7ij;
Pippol = 3..Pippol(r.q-l)+Pippol((i~l.s)}
}

Cl'oiuc' varici la soluzione clell'eqiiazionp eli ricorreiizrt yc la pri)ft'dura Pipiicil f c'osì modificat.a:
Pippul (r , s) : int :
{ir ,•>.-,
{for (/= l: /S|/1|- l; ;-+)
For (j= |.4|; .;>M-1: j-~)
if (A[i}>Aij}} {scanibia /l[t| mn ,1[;)}
}
else {int q = L^J:
Pippol = Pippol (q/2+IU.s)}
}
 Prova di Algoritmi e Stnitture Dati II
Non si possono consultare ne appunti ne testi
VI appello
6 Febbraio 2007

Esercizio l. (punti 12) Dati un insieme M = {1,2,... ,'n.} di balocchi, [Link] di valore
{t'l, i'2,... ,t'n}, si chiede se esiste ima partizione dei balocchi di M tale che sia uguale. la
soaima del valore dei balocchi assegnati a ciasciiua partizione. Progettare per risolvere il
problenia:

l. una procedura polinomiale noil detenninistica,

2. una procedura deterministica enuiuerafciva

Esercizio 2. (punti 6) Dato un mtero n > 0, una costante fe, l'Tt-esimo minierò di Fibonacci*
E,; è definito ricorsivamcate come segue:

Fo=Q,Fi=F^=...^Fk=l

Fn=vza^F,^,J^Fi) V n> k
[=-1 1=1

l. Dare una realizzazione in [Link] di lili algoritiiio efficiente per calcolare F,i.
2. Valutare la couiplessità in teuipo e spazio dell'algoritmo.
Esercizio 3. (punti 6) Sia G un grafo non orieutato, pesato e sia T un albero di copertura di
costo miiiuno di G. A G è aggiunto iiu miovo vertice v s iiuovi archi incidenti, ottenendo
cosi il grafo G'. Sia (v, u) l'arco di costo minimo incidente su •t'. Dimostrare che T U (u, u) è
il nuovo albero di copertiira di costo niinimo per G oppure trovare un controesempio in cui
l'algoritmo fallisce.

Esercizio 4. (punti 6) Dimostrare per indiizìoue che iiu albero binomiale Bh ha (^) iiodi alla
profondità ;', can 0 < i < A'.
 Prova di Algoritmi e Strutture Dati I
Noil si possono consultare ne appunti ne testi
Ili appello

5 Giugno 200/

Esercizio l. (punti 12) E' dato ail array A ordinato di n interi, compresi fra l e 5. Si consideri
il problcnia di [Link] il iiuinero di occorreuze del numero 2 in A.
l. DeHcrivere a parole la struttura di uii algoritino divide-et-impera per riyolvere tale
problema.
2. Dare uiia realizzazione [Link]'algoritino in pseudocodice.
3. Disc'.utere l'equazione di [Link] che. deHcrive la complesyità in tempo della soluzioiie
proposta c [Link] un limite siiperiore.
4. Discutere l'ottinialità della soluzione proposta,
Esercizio 2. (punti 10) Dato un grafo noli orienfcato G == {y,E), sì conyideri il problema di
verificare se. G c un albero.

l. Descrivere a parole l algoritino proposto per riyolvere tale problema.

2. Dare uiia realizzazione dell'algoritmo in paeudococlice.
3. [Link] Biiperiormc'iue la compleyyità ili tempo della yoluzioue propoyta.
4. Discutere l'ottimalit.à della, soluzione proposta.
Esercizio 3, (punti 8) Calcolare la complessità in tempo nel caso peysimo del seguente algoritmo
ricorsivo:

procedure Pippo (n, ou,if);

begin
if (n < 4) then out:== 1;
else if n < 8 then :r := Pippo([^J)+Pippo(|^j)
else begin
a::=Pippo(^J);
t:=lG,
ouit:=2t;
while out > 2 do (mt := v/^rf;
end
end
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
8 Novembre 2022

Esercizio l Calcolare il limite superiore alla complessità in tempo dei seguenti algoritmi:

1 Test l (n : mt):int; 1 Test 2(n : int):int;

2 if n< 10 then 2 a:=0;
3 n := n— 5; 3 while n > 2 do
4 return 5; 4 ^ n := n—3; a := a+1;
5 else 5 while a > l do
6 if n < 100 then 6 b := a;
7 2*Tesèl(n-3) 7 while b^ l do
else
8 8 [_b:=b-l;
9 return 2 * Testl{n/2) + n2
9 a := a— l;

Esercizio 2 Dati due array A e B della stessa dimensione n che memorizzano interi, calcolare
l'array C tale che C[i\ = E}=i -^b'] - E}=i -B[j]> Per ogm l < i <n.
• Descrivere l'algoritmo a parole e dare lo pseudocodice

• Studiare la complessità in tempo della soluzione proposta

• Studiare l'ottimalità della soluzione proposta. Quanto memoria aggiuntiva usa l'algoritmo
proposto?

Esercizio 3 Dato un grafo G = (V, -E) orientato, scrivere un algoritmo per verificare se G è un
Directed Acyclic Graph

• Dare lo pseudocodice dell'algoritmo che risolve il problema

• Studiare la complessità in tempo della soluzione proposta

Esercizio 4 Dato un array S quasi ordinato, ossia gli elementi in posizione pari sono fra loro
ordinati e lo stesso quelli in posizione dispari. Scrivere un algorimo per ordinare 5'.
Esempio: S=l 43798 Soluzione S'= 134789

• Dare lo pseudocodice di un algoritmo che risolve il problema

• Studiare la complessità in tempo della soluzione proposta

• L'algoritmo proposto è in-place?

• Discutere l'ottimalità dell'algoritmo proposto

 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi

21 Gennaio 2020

Esercizio l. Dato un testo T, si vogliono sostituire i caratteri che appaiono in esso con una codifica tale
da minimizzare la luiighezza del testo T dopo la codifica. Descrivere un algoritmo che restituisce la
codifica da sostiture a ciascun carattere in T. Descrivere la complessità dell'algoritmo di codifica.
Motivare percliè l'algoritmo proposto miiiimizza la dimensioiie del testo T dopo la compressioiie.
Esercizio 2. Dato un grafo non orientato G = (V, E) connesso e aciclico, si voglioiio etichettare i vertici
in V in modo che gli estremi di ogni arco siano assegnati a due etichette diverse. Descrivere un algo-
ritmo che risolve il problema c darne lo pseudocodice. Quante etichette sono utilizzate dall'algoritmo
proposto? Il grafo G è un albero? Studiare la complessità in tempo dcll'algoritmo proposto.
Esercizio 3. Dato un grafo G = (V, £') diretto e pesato lu : E -^ N+, data una sorgente s e V, trovare il
vertice u tale che il canimino da s a u sia quello di peso d(s, u) minimo in G. Descrivere uii algoritmo
che risolve il problema e darne lo pseudocodice. Studiare la complessità dell'algoritmo proposto.
Esercizio 4 Calcolare la complessità in tempo dei seguenti algoritmi:

1 Test; int s := n; a := l; t :•• o i Pippo(n : int) : int

2 w^hile A > l do 2 if n < 3 then
3 |_ &•:-Ljj;a++ 3 I return 1
4 for •i := l;-(++;2a do 4 else
5 \_t:=2+t 5 j •= l;
6 while j < n do
7 L^':=J+2
8 return Pippo (^) . Pippo (|) + ^n
 Prova di Algoritmi per Fuori Corso
Non si possono consultare ne appunti ne testi
A.A. 2018-19
26 Marzo 2019

Esercizio l Calcolare la complessità in tempo del segiiente algoritmo:

l function Pippo('a : integer) :int,eger;

2 int k :== n;
3 while A: > l do
4 |_ fc ;== fe/5;
6 if?z > 1 then
|_ return: 2s!°Pippo(?ì. - 1}
6 else
L return:100

Esercizio 2. Dato una sequenza 5 di n matrici, Ai,A2,... ,An, con Ai •= pi-i x p,:, si vuole
determmai'e il minimo iiumero di prodotti scalari P[l, n} richiesto per [Link]'e fra loro le
matrici Ai AS • • • An. Dare lo pseudocodice deìl'algoritmo. Discutere la complessità m tempo
della soluzione proposta.
Successivaniente, trovare l'indice i compreso nell'intervaUo [l,..., n], tale che il iiumero
di prodotti scalari richiesti per calcolare il prodotto P[i,i + 3] delle 4 niatrici consecutive
AiA.i-i-iA.t+sAt+s sia minimo. Dare lo pseudocodice per risolvere questo problema e discutenie
la complessità.
Esercizio 3. Dato uii grafo G = {V, E) orientat.o e aciclico, calcolare l'ordinan'[Link] topologico dei
vertici di G. Dare lo pseudocodice della soluzione e cUscutere la complessità ili •tempo della
soluzione proposta.

Esercizio 4. Dati n. interi A = {ai, ag,..., Qn}, scrivere l'algoritnio di ordinaniento MergeSo'rt.
Dare lo pseudocodice dell'algorìtmo proposto (in tutte le sue parti) e discutere la coaiplessità
in tempo della sohizione proposta. L'algoritmo proposto è ottimo? Perché?
 Prova di Algoritmi e Strutture Dati
Non si possono consiiltare ne appiuit.i ne testi
7 Maggio 2019 - B
^Esercizio l Iiiserite ili lina tabella liash T ad indirizzaioeuto aperto di diinensioite m == 11 coii
le collisioiii risolte con la scaiisione lineare e passo unitario le [Link] 6 chiavi 1,3,122,5,16,15.
Supponete ora di ùiserire la chiave 12. Quante celle saranuo visitale? Scrivere ili pseudocodice la
procedura per l'operazione di inserzione di una chiave in T assumeiido che sia gesti'ia come appeiia
descritto. Studiarne la complessità in tempo. Si possono inserire 13 chiavi in T? E' possibile che
la tabella T appaia piena mentre esistono ancora celle disponibili?

Esercizio 2 Calcolare il codice di Hiiffman per la segueiite stringa: 'A chi troppo e a chi niente'
(si igiioriiio gli spazi). Qiianti bit si risparrniaiio rispetto la codifica standard che usa 8 bit per
ciascuii carattere? Scrivere Io pseudocodice dell'algoritmo che calcola l'albero del codice di Huffman
date le frequenze dei caratteri.

a Esercizio 3 Dato iiu grafo orieiitato e pesato G == {V, E}, mia sorgeute s € l'', m cui tutti i
cammini iTiinimi haimo lunghezza (iminero di archi attraversati) miliare of uguale a k. Progettare
uii algoritmo per calcolare i cammini minimi da s a tutti i vertici in G. Dare lo pseudocodice
dell'algoritmo e discutere la complessità ili tempo dell'algoritmo.

.^Esercizio 4 Sia dato un array A che contiene interi positivi, lina [Link] crescente in
A è mia seqiieuza di indici cresceiite m A i cui eleiueiiti hamio valore crescente. Progettare un
algoritino che ritonii la Imighezza della sottosequeiua cresceiifce di Iuughei;Ka iiiasshua. Dare lo
pseudocodice e discutere la complessità in tempo.
 Prova, di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
(Ili Appello) 2 Luglio 2019 -
Esercizio l Calcolare la complessità in tempo dei seguenti algoritmi:

1 Test l, 1 Pippo(n : int) : int

2 int t := n; 2 if n < 2 then
3 while t > l do 3 I return n
4 [_ t := log'it 4 else
5 |_ return 2 Pippo(['i:1) + n
1 Test 2;
2 int t := l;
3 while t < n2 do
4 [_ t :== 2*f

Esercizio 2 Dati un albero binario di ricerca T i cui elementi sono interi, distinti e non negativi,
c dato un intero k, progettare un algoritmo per restituire gli clementi di T minori o uguali a k.
Dare lo pscudocodicc della soluzione c discutere la complessità della soluzione proposta.

Esercizio 3 Dato un grafo G = (ì/, E) orientato e aciclico, progettare un algoritmo per lineariz-
zare G, ossia per restituire i vertici di G in modo tale che tutti gli arclu siano [Link] da sinistra
verso destra. Dare lo pseudocodice dell'algoritmo e studiare la complessità in tempo dell'algoritmo
proposto.

Esercizio 4 Data mi grafo G = (Vr, £') orientato e pesato con la fmrzione •ui : E —> N+ e data
una. destiuazioi-ie u 6 V, trovare per ogni vertice v 6 V il casto del cami-uino minimo per [Link]
in u. Progettare l'algoritmo e calcolare la. complessità in tempo dell'algoritmo.
 Prova di Algoritmi e Strutture Dati
Non si possono consultare ne appunti ne testi
(V Appello) 2 Settembre 2019 -
Esercizio l Calcolare la complessità in tempo dei seguenti algoritmi iterativi:

1 Test l; 1 Pippo(n : int) : int

2 int t := n 2 if n < 2 then
•
3 while t > l do 3 I return 2
4 [ t := t-2 4 else if n. < 200 then
5 int ,9 := 0; a := O
•
6 while j <, n do
7 |_ j :==j+l;a :=a+j
8 for i := 1/ t-il-+; a do
1 Test 2;
2 int t := l
9 L -'" := j -1
•
3 while t < n do io else
4 L f := t*3 il ] return Pippo(?z - 5)

Esercizio 2 Dato im array A ordinato in senso decrescente che contiene interi positivi e negativi,
progettare un algoritmo per trovare la posizione del primo intero negativo. Discutere la complessità
e l'ottimalità della soluzione,
Esempio
Input: 10, 3,1.. -5, -7 Output:4 perché A[4] = -5

Esercizio 3 Proporre un'istanza del problema della selezione delle attività per [Link], selezionando
come regola greedy l'intervallo più corto, non si ottiene una soluzione ottima. Scrivere lo pseudoco-
dice dell'algoritmo greedy visto a lezione che calcola la soluzione ottima per selezionare il massimo
numero di attività indipendenti. Stiidiarne la complessità in tempo.

Esercizio 4 Dato un grafo non orientato e pesato G = (V, E) e il suo albero di copertura di
costo minimo T, si consideri il grafo ottenuto aggiungendo l'arco pesato e = (zi, v), ossia G' =
(V, E U (it, -u)) (i vertici sono invariati). Sia T l'albero di copertura di costo mimmo per G . Dare
lo pseudocodice di im algoritmo che calcola il MST di G conoscendo G, e, e T. Discutere la
complessità in tempo dell'algoritmo proposto.
 Algoritmi e Strutture Dati con Laboratorio
Non si possono consultare ne appunti ne testi
VI appello
A.A. 2015-2016
Orale obbligatorio
31 Gennaio:2017

Esercizio l.

Applicando la definizione di ordine di grandezza, provate o confutate resistenza di una

costante c > O tale che:

22n e 0(2")

Trovate un limite asintotico superiore per la coniplessità in teiiLpo del seguente algoritmo:

l Pippo(n : integer):]
2 iut -{' := n;
3 while 2 > 2 do
4 l J:=l;
5 I while j < i do
s L J :== J'*2
7 l l :== t— l;

Esercizio 2. (Da svolgersi m C, per chi lo desidera) Dato un albero binario, realizzato con
puntatori, i cui nodi contengono interi, sostituire il valore inemorizzato in ciascun nodo con
l'intero che precede il valore memorizzato nel padre. Dare lo pseudocodice dell'algoritmo e
studiare la complessità in tempo deU'algoritmo proposto.
Esercizio 3. Sia A un array di n interi, ciascuiio compreso nell'intervallo [71,..., 3*n]. Progettare
un algoritmo ottimo per l'ordmameiito di A e motivare l'ottimalità ( ossia, studiare la com-
plessità in tempo intrmseca del problema e la complessità in tempo della soluzione proposta,
e dire se la soluzione proposta è ottima). Dare lo pseiidocodice dell'algoritmo proposto.
Esercizio 4. Dato uà grafo G = (V, E) non orientato, uii intero k con l ^ fc < |V[, trovare e
stampare tutte le coppie di vertici in G che sono a distanza minore od uguale a k.
• Descrivere i'algoritmo clie si propone
• Darne la descrizione in pseudocodice
• Discuterne la complessità in tempo dell'algoritmo in fuiizione di |y|, \E\ e del valore k.
• Se fc = |l/|, si può proporre una soluzione ad-hoc particolarmente efficiente? Spiegare
la risposta.
 Prova di Algoritmi
Non si possono consultare ne appunti ne testi
A.A. 2016-2017
19 Settembre 2017 (B)

Esercizio l Risolvere con l'albero della ricorsione l'equazione di ricorrenza che rappresenta la
complessità in tempo dell'algoritmo:

1 function Pippo{n : integer) :integer;

2 int k:= l; a:=:0;;
3 while k < n do
4 for int j:=l, j < n, j++ do
5 [_ a:= a+1
6 l fc :=2 * fc+a,
7 if n > 10 then
8 L Pippo:=Pippo([§J)+Pippo(LiJ)+5
9 else
io L Pippo:= 100

Esercizio 2. Dare una lista L realizzata con puntatori le cui chiavi sono ordinate in senso crescente,
e data una chiave k, si vuole progettare in pseudo-codice un algoritmo per verificare se fc
appartiene ad L. Si discuta la complessità m tempo dell'algoritmo proposto. Si discuta
l'ottimalità della soluzione proposta.
Esercizio 3. Dato un grafo G = {V,E) non orientato, un aodo s € V, trovare i nodi raggiungibili
da s in G. Dare lo pseudo-codice dell'algoritmo proposto. Discuterne la complessità in tempo
e spazio.

Esercizio 4. Dato una sequenza 5 di n matrici, Ai, A^,..:, An, con A, = pi-i,x p,, si vuole
determinare l'indice i che individua in modo univoco la sottosequenza AiAi-i-iAa+aAi+s di 4
matrici consecutive il cui prodotto P[t,? + 3] = Ai x AÌ-|-I x Ai+a x A^+3 richiede il minor
numero di prodotti scalari. Descrivere una soluzione basata sulla programmazione dinamica
per trovare 1'[Link] i. Dare lo pseudocodice dell'algoritmo. Discuterae la complessità della
soluzione proposta.
Esercizio 5. Dato un intero K, con l <, K < \logz\V\}, e un grafo orientato G, i cui archi sono
pesati con la funzione w : E -^ ]R+, descrivere un algoritmo per trovare per ciascuna coppia di
nodi il cammino di lunghezza minima che attraversa al più K archi. Discutere la complessità
iu tempo della soluzione proposta.
 Prova di Algoritmi e Strutture Dati I
^Ton si possono consultare ile appunti ne testi
IV Appello A.A. 2009-2010
17 Giugno 2010

Esercizio l. (punti 9) • Per il problema P si conoscoiio due soluzioni 5o/i e Sol'ì con com-
plessità in tempo T] (n) e T^n) rispettivamente, ove:
Ti(n) - 5 if n < 120
T(n/2)+n2 if n > 120
e

T2{n} 5 if n < 120

QT(n/f3) + n if n > 120
Per quali valori di a e /3, la soluzione Sol'i e più efficiente di Sol\ì.
• Studiate la complessità in tempo del seguente algoritmo iterativo:
Eserc'iz io (n : integer) ;
{i nt k =0;
while (fc<n) {
for (int j =1 ; jO" ; j++) {t++};
for (int r = L ; r <: k ; r++)
for (i nt s = l ; s<k ; s++)
{[Link] ;= l};
k++;

Esercizio 2. (punti 10) Dato un albero binario di ricerca T, e il puntatore al nodo che contiene.
la chiave A,', si progetti un algoritmo che sostituisce k con la chiave predecessore di k in T. Si
studi la coniplessità in tempo della soluzione proposta.
Esercizio 3. (punti 11) Dato un insieme .4 di n interi compresi nell'intervallo [0,n2]. Scrivete
un algoritnio ottimo per l' ordinainento di A. Discutete la complessità e l'ottimalità in
tempo della [Link] proposta.
 Prova, di Algoritmi
Non si possoiio consultare ne appunti ne testi
A.A. 2010-2011
30 Gennaio 2013

Esercizio l(Alg.l) La ricorreiiza T(n) == 8T(n/2) + nlog(n) descrive il tempo di esecuzione di

im algoritmo A. Un altro algoritmo A' ha un tempo di esecuzione T'(n) == aT"(n/4) + n2.
Confrontare le complessità dei due algoritmi al variare del parametro a.
Esercizio 2 (Alg. con Lab) Risolvere con l'albero deUa risorsione 1'equazion.e di ricorreiiza che
rappresenta la complessità in tempo dell'algoritmo:

l function Pippo^n : 'integer):integer;

2 int k:= l; a:==0; i:==l;
3 while k < n do
4 ] for int j:=i, j < n, j++ do
5 ' L. a::::::a+l
6 l i++; k:=2*]c;
7 if n > 10 then
8 L PÌPPO:-PÌppo([§J)+ PÌppQ([JJ)+2 * ^n
9 else
io L Pippo:= 100

Esercizio 3. (Alg.l) Dati due iiisiemi ordinati A e B ciascuno di n interi distinti e positivi,
trovare la mediana dell'insieme AU B. Dare l'algoritmo in pseudo-codice e discutere la
complessità in teinpo della soluzione proposta. Discutere l'[Link]à della soluzione proposta.
Esercizio 4. (Alg. con Lab., Alg. l) Dato un grafo G non orìentato, i cui nodi sono colorati
di giallo o di verde, trovare quante sono le compouenti coanesse in G che sono composte di
soli nodi gialli.

Esercizio 5. (Alg.2, Alg. con Lab.) Dato un albero di copertiu-a T di costo mimmo, sia o l'arco
di costo massimo in T. Verificare che T è un minimiim-bottleneck spaaniug-tree (MBST),
cioè verificare die non esiste nessun albero di copertiira di costo minimo il cui arco di costo
massimo costi meno dell'arco b. Dare lo pseudo-codice dell'algoritmo di verifica e discutere
la complessità in tempo della soluzione proposta.
Esercizio 6. (Alg.2) Data una stringa S, descrivere, un algoritmo per verificare se 5' è palin-
drome e discuterne la complessità. Trovare poi il minimo numsro di caratteri da iiitrodurre
per renderla palindrome. Descriveie una soluzione basata sulla programmazione dinamica.
Discutere la complessità in tempo della soluzione proposta.
Esercizio 7. (AIg.2) Data uu grafo orientato G, i cm archi sono pesati con la funzione w : E -T K,
descrivere uu algoritmo per verificare se esistono cicli di peso negativo in G. Ricordo che il
peso di un ciclo è definito come la somma dei pesi degli archi che vi appartengono. Discutere
la complessità in tempo della soluzione proposta.
 o

Prova di Algoritmi e Strutture Dati

Non si possono consultare ile appunti ile testi
IA esonero A.A. 2012-2013

12 Febbario 2013

Esercizio l,

Ordinate, rispetto l'ordine di graiidezza asintotico, le seguenti fuiizioni /(n) e. giustificate

l'ordiue scelto:

logs log?(n); 2 log; logn, Ioga n^ 2'°^ "; 210s' "1/:!

Applicando la definizione di ordine di grandezza, provate o coiifutate che:
n

^nog2!'e9(n)
1=1

Esercizio 2. Descrivete al variare dei parametri a e b la coiiiplessità. dell'Eq. di ricorreuza:

f4 if n < 2
T(n)
\aT^)+nì if n. > 2
Esercizio 3. Date l'equazioae di ricorreiiza che descrive la complessità in teinpo del segiiente
algoritmo ricorsivo:

l Pippo(u : integer):integer;
2 if n < 3 then
L return; 3
s else
4 int k:=l:
5 while /c < n—1 do
6 for int „?':= 1, j < n, j++ do
7 L fe ;= A+2
8 A: :== fe— 2*n+ l;
9 Pippo :=2:itPippo(Ljl)+5

Trovate un limite [Link] superiore per la coniplessità in tempo risolvendo l'equazione di

ricorrenza con l'albero della ricorsioiie e provaiidone la. soluzione per inrhizione.
Esercizio 4. Scrivete una procedura Dummy la cui complessità in tempo sia descritta daIl'Eq.
di ricorrenza:

r(n)
Jo(i) if n ^ 2
[3T^}+0(n) if n > 2

Stiruate un limite asintotico superiore per la coniplessità in tempo della procedura Dummy.
 PJL ENTER LANGUAGE = PCLXL
HP-PCL XL;l;l;Comment Copyright Artifex Sofware,

Prova di Algoritmi e Strutture Dati II

Non si possono consultare ne appiinti ne testi
II Appello
11 [Link] 2014

Esercizio l. (Algoritnii l, Alg. con Lab.) Ordinate ili ordine crescente di grandezza le seguen-
ti funzioni /(n) e giustificate l'ordine scelto: /i(?7.) == n.l/2, /2(") ^ 4losi6", ^(n) = 34 Ioga n
Risolvete la segueiite equazione di ricorreiiza e dimostratela per iaduzioiie:
T(n) = 4r(n/2) - 0(n3)
W)
Esercizio 2. (Algoritmi l, Alg. con Lab.) Dato un grafo [Link] e connesso G = (V, E),
scrivete una procedura per testare se G è un albero. Discutete la complessità della soluzione
proposta.

Esercizio 3. (Algoritnii l) Dato uno heap 77 di n elementi, inserite im nuovo elemento x ili
H. Progettate tale algoritmo e descrivetelo in pseudo-codice. [Link] la complessità in
tempo.

Esercizio 4 (Algoritnii 2). Dato un cammiiio P=-{1, 2, ..., il}, i cui nodi sono pesati con la
funzione u : {1,2,... ,n} -> Z+, progettate mi algoritmo per trovare uii [Link] S dei
vertici in P tale che:

l. 5' lion contieiie vertici adiacenti in P;

•^ 2. o- = [Link] U'[J} è massima.
Valutate la complessità in tempo dell'algoritmo proposto.
Esercizio 5 (Algoritmi 2, Alg. con Lab.). Si coiisideri il seguente algoritmo S-MST per calco-
lare un albero di copertura T di costo minimo di uà grafo iion orientato e pesato G = (V,E},
i ciu pesi sono tutti distinti.
Algoritmo S-MST(G,T):
• ordina l'insieme E degli archi di G in seuso decrescent.e rispetto ai loro pesi, tale che.
ei~S eg M . ..'"g em;
• T:=E\
• for (i- = m; i < l; t--) do
- ifG^(V,T- {e,}) è uii grafo connesso then. T:=T- {e.};
return T

l. Dire se l 'algoritmo S-MST calcola uii albero di copertiira di costo minimo per G.
Motivare la risposta.
2. Coinè si verifica se T è couuesso. Dare lo pseudocodice.
Esercizio 6 (Algoritmi 2, Alg. con Lab.). Codificare con i codici di Huffman la seguente se-
queiiza. BINGO GANG GANG. Qual'e' il risparmio rispetto uiia codifica ASCII?

: ^TE.^&%%±^*3^Àx^*sN»às%^*T^^l"@'^^^"^> ° éécis^^ ^rr*à^t@g®8aW3??^°

 Algoritmi e Strutture Dati con Laboratorio
Non-si possono consultare ne appunti ne testi
I appello A.A. 2013-2014
3 Giugno 2014

{Algoritmi l, Alg. con Lab.) Esercizio l. TroTOte un limite asintotico superiore per
la complessità in tempo dei seguenti algoritmi. Se si utilizza l'albero della ricorsione,
si provi la soluzione per induzione.

Pluto(n : integer); Pippo(n : integer) :mteger;

iut a; if n < 3 then
while n > 2 do L reéitrn: 3
l l int a ;= n; else
while a > 2 do int a := l;
while a ^ n do
L^-LtJ; L a:=a+2
n := n —3
Pippo :== 4*Pippo([jJ) + n2

(Algoritmi l, Alg. con Lab.) Esercizio 2. Sia A un array ordinato di n interi com-
presi fra {0,1]. Deteniiinare 5um(A) = Y^^A.[i]. Dare lo pseudocodice dell'algo-
ritmo. Studiare la complessità in teinpo intrinseca del problema e la complessità in
tempo della soluzione proposta, e dire se la sohizione proposta è ottima.
(Algoritmi l) Esercizio 3. Dato im. grafo orìentato G = {V,E), i cui archi hanno cias-
cimo costo unitario, ossia io: E -> l, trovare il costo dei cammini minimi dal vertice
s e V a ciasci.m vertice u E V. Descrivere l'algoritmo, darne Io pseudocodice e
studiai-ne la complessità.

(Algoritmi 2, Alg. con Lab.) Esercizio 4, Si hanno a dispozione barili con A capacità
diverse (nou multiple fra loro), [Ck > Ck-i > ... > C'2> C'i ==!}. Considerate il
problema di riempire una cisterna di capacità W travasando il minimo numero di barili.
Descrivete
0(Wk).
un algoritmo che risolve all'ottimo i! problema in tempo coiuputazionale

(Algoritmi 2) Esercizio 5. Si consideri un grafo G = (V, E) non orieiitato e pesato, con.

pesi io : E —r R. Sia e l'arco di peso massimo con Wg > 0. Descrivere im algoritmo
per verificare, senza calcolare TQ, se e appartiene o no al minimum spanning tree TQ
di G. Studiare la complessità in tempo della soluzione proposta.
[Algoritmi S, Alg. con Lab.) Esercizio 6. Dato un grafo G = (V, E~) pesato ed orieu-
tato, una sorgeiite s e V, ed un valore L, progettare uà algoritmo per trovare [Link] i
vertici a distanza al più L da s. Dare lo pseudocodice dell'algoritmo e discuterne la
complessità in tempo.
 Algoritmi e Strutture Dati con Laboratorio
Non si possono consiiltare aé appunti ne testi
II appello A.A. 2013-2014
24 Giugno 2014

(Algoritmi l, Alg. con Lab.) Esercizio l. Trovate un limite asintotico superiore per
la complessità in tempo dei seguenti algoritmi. Quando utilizzate l'albero della ricor-
sioue, provate la soluzione per induzione.

Minnie(ii : iiiteger);
iut i, t,b;
•= s-
•= 2- Pippo(n ; integer) :mteger:
t :=l;c:=2; if n < 3 then
l while c < n do L return:n
while (i < n) do else
t:=t+l; L Pippo := 64:iiPippo([^J) + n2
! :== 1 - 2';
L c :== c2

[Algoritmi l, Alg. con Lab.) Esercizio 2. Sia A un array ordinato di n interi com-
presi fra [0,n3]. Progettare un algoritmo di ordinamento che richiede tempo di esecu-
zio ne lineare in n nel caso pessiino.

{Algoritmi l) Esercizio 3. Dato un grafo [Link] G = (V, E), progettare un algoritmo

per testare se G è im Directed Acyclic Graph (DAG). Descrivere l'algoritmo, darne lo
pseudocodice e studiarne la complessità.
{Algoritmi S') Esercizio 4. Dato [Link] grafo G == (V,-E) orientato con archi pesati, e dato
im intero k, progettare un algoritmo per verificare se esiste zm ciclo di costo negativo
di lunghezza al più k. Descrivere l'algoritmo, darne lo pseudocodice e studiarne la
complessità. (Ricordo che il costo è definito come la somma dei pesi siigli archi del
ciclo, mentre la lunghezza è il iiumero di ardii attraversati dal ciclo.)
(Algoritmi 2, Alg. con Lab.) Esercizio 5. Si consideri un grafo G = (V, £') non onen-
tato e pesato, con pesi w. E —f R. Provate o confutate coil im controesempio questa
afFermazione: Gli archi dipeso negativo in E appartengono tutti all'albero di copertura
TG di costo minimo di G.

{Algoritmi 2, Alg, con Lab.) Esercizio 6. Data una sequenza di interi positivi cia-
scuuo compreso fra O e 9, ossia 01,03,... ,a.n con 0< a; $ 9, detenmnare k posizioiii
bj, with 1 <bj < n—l e bi < 63 < . ..bk, tali che, insereiido l'operatore aritmetico della
moltiplicazione dopo l'intero afe, per l <j ^k ed iiiterpretaiido la sequeiiza così otte-
nuta come k+1 numeri posizionali in base 10, l'espressione ottenuta sia massimizzata,
Descrivere l'algoritmo, darne lo pseudocodice e studiarne la complessità.
Esempio: Sia n = 3 aud fc - l esia data la sequenza Q]., 02,03 = 2,7,5. Si vuole
detenninare la posizione &i dove inserire il simbolo della moltiplicazione in modo da
massimizzare il risultato dell'espressione. Se &i =^ l, l'espressione diventa 2 * 75, il cm
v'[Link] è 150. Se 61 = 2, l'espressione diventa 27 * 5, il ciii valore è 135. Pertanto la
soluzioae del nostro problema è &i = l.