Fac Simile B

Seconda Provetta

ASD1 2002-2003

Esercizio 1   Sapresti dare uno pseudocodice od una descrizione comunque efficace e formale per la $t$-Selection in tempo lineare? (La $t$-Selection era l'algoritmo che avevamo proposto per risolvere il Median Finding Problem in tempo lineare). Sapresti esprimere i punti salienti per l'analisi del running time di tale algoritmo?

Esercizio 2   Per $n$ elementi distinti $x_1, \ldots, x_n$ con pesi positivi $w_1, \ldots, w_n$ tali che $\sum_{i=1}^n w_i = 1$, il mediano pesato è l'elemento $x_k$ che soddisfa le seguenti diseguaglianze:

$$\sum_{x_i< x_k} w_i \leq \frac{1}{2}$$

e

$$\sum_{x_i> x_k} w_i \leq \frac{1}{2}.$$

Fornire un algoritmo che trovi il mediano pesato in tempo $\Theta(n)$.

Aiuto: Se non sai da che parte partire, prova a porti prima degli obbiettivi più modesti, che ti consentano di familiarizzare con il problema, ad esempio:

• sapresti dimostrare l'esistenza del mediano pesato?
• sapresti fornire un algoritmo $\Theta(n\log n)$ per la ricerca del mediano pesato?

Esercizio 3   Agli archi di un grafo $G=(V,E)$ sono associati dei pesi (valori reali o interi, come preferisci). Abbiamo cioè una funzione $w:E \mapsto R_+$. Vorremo trovare un albero di copertura di peso minimo. Poggiando su uno heap di servizio (preso come black-box), si dia uno pseudocodice per l'algoritmo di Prim per il computo di una soluzione ottima. Si assuma che la soluzione $T$ venga costruita a partire da un certo nodo $s$, aggiungendo gli archi uno alla volta. Nello pseudocodice, gli archi siano colorati verde, giallo e rosso, secondo il seguente schema:

rosso

ad ogni istante, è rosso ogni arco che sia già stato infilato nella soluzione corrente $T$;

giallo

si consideri un arco $uv$ con un estremo $u$ già raggiunto da $T$ e l'altro estremo $v$ non ancora raggiunto. L'arco $uv$ è giallo se $u$ è il primo nodo raggiunto da $T$ tra quei nodi $z$ che minimizzano $w(zv)$ con $zv\in E$ e $z$ già raggiunto da $T$;

verde

altrimenti.

Nello pseudocodice, i nodi siano colorati bianco, grigio e nero, secondo il seguente schema:

bianco

se non si è ancora individuato un cammino da $s$ al nodo in questione;

grigio

se si è già individuato qualche cammino da $s$ al nodo in questione $v$, ma $v$ non è stato ancora estratto dallo heap di servizio;

nero

il nodo in questione è già stato estratto dallo heap di servizio.

Dimostrare poi le seguenti invarianti:

1.

ad ogni iterazione, ad uno specifico passo della tua procedura da te indicato, puoi affermare che i nodi grigi sono tutti e soli i nodi nello heap di servizio;

2.

quando $v$ è nero, allora $v$ ed $s$ sono già connessi in seno alla soluzione parziale $T$ (fatta dagli archi rossi).

3.

esiste una soluzione ottima per il problema ricevuto in input che contenga $T$, ossia tutti gli archi rossi.

Esercizio 4   Con riferimento al precedente esercizio, sapresti condurre l'analisi del running time nel caso peggiore evidenziando inoltre le differenze qualora lo heap sia sato realizzato come Heap Binomiale o come Heap di Fibonacci?

Esercizio 5   Sapresti esprimere in una mezza paginetta (e max una pagina) i punti salienti dell'analisi del QuickSort?