.dsy:it. (http://www.dsy.it/forum/)
- Filez (http://www.dsy.it/forum/forumdisplay.php?forumid=25)
-- [Goldwurm] Scansione appunti 2004-2005 (http://www.dsy.it/forum/showthread.php?threadid=14142)

17a lezione
(il 9 non ha spiegato niente, ha fatto solo alcuni esercizi delle dispense quindi non ho preso appunti)

18a e 19a lezione

20a lezione

21a lezione

22a lezione

23a lezione

24a lezione

25a e 26a lezione

27a lezione

28a lezione

29a lezione

SECONDO COMPITINO

Posto il testo del secondo compitino... magari può servire...



Esercizio 1
Eseguire l’algoritmo Quicksort sull’input

4, 2, 6, 0, 1, 7, 8, 9, 3, 5

mettendo in evidenza gli scambi eseguiti e assumendo sempre come pivot il primo elemento della sequenza corrente.


Esercizio 2
a) Definire la nozione di albero di ricerca binaria e descrivere ad alto livello due procedure ricorsive, la prima per la ricerca di un elemento in tale struttura e l’altra per l’inserimento di un nuovo elemento.
b) Descrivere ad alto livello due procedure non ricorsive per eseguire le medesime operazioni.


Esercizio 3
a) Descrivere una procedura del tipo divide et impera per il calcolo dell’espressione

X = a1 * a2 + a2 * a3 + a3 * a4 + ... + an-1 * an

su input n, a1, a2, … , an.
b) Assumendo il criterio di costo uniforme, valutare in funzione di n il tempo di calcolo e lo spazio di memoria richiesti dalla procedura su input n, a1, a2, … , an.
c) Supponendo che ogni ai sia un intero di k bit, fornire una valutazione O-grande del tempo di calcolo e dello spazio di memoria richiesti dalla procedura secondo il criterio logaritmico, in funzione dei parametri n e k.

Appunti del 25-1-2005