Algoritmi e strutture dati domande teoriche

[giacomovicinanza]

Salve a tutti. Purtroppo ho ricevuto un voto basso (20) all'esame di algoritmi e strutture dati e naturalmente ho rifiutato. Ringrazio tutti coloro che aiuteranno

PRIMO QUESITO
"Spiegare il funzionamento della funzione Merge utilizzata dal MergeSort e indicarne il tempo di esecuzione nel caso ottimo e nel caso pessimo"

Data una porzione di un array, mergesort la divide in due parti della stessa dimensione a cui applicare l’algoritmo stesso, poi fonde ordinatamente le due parti:
L’ordinamento per fusione o Merge Sort riconduce il problema dell’ordinamento al problema della fusione di array ordinati , che può essere formulato come segue:
Date due sequenze ordinate a0, . . . , an1 e b0, . . . , bm1, vogliamo ottenere una nuova sequenza, anch’essa ordinata, di n+m elementi c0, . . . , cn+m1, che contenga tutti gli elementi delle due sequenze di partenza.
Una volta trovata una soluzione per questo problema, possiamo utilizzarla per risolvere il problema dell’ordinamento attraverso una decomposizione ricorsiva:
dividiamo la nostra sequenza da ordinare in due parti, che ordiniamo separatamente attraverso la ricorsione; quindi fondiamo le due parti ordinate in un’unica sequenza anch’essa ordinata
L'algoritmo mergesort ha complessità O(nlogn) nel caso peggiore, e O(n) nel caso migliore, cioè quando l'array è già ordinato.

SECONDO QUESITO
"Mostrare la relazione di ricorrenza che descrive il tempo di esecuzione nel caso pessimo (in termini di numero di operazioni richieste) della ricerca binaria (o dicotomica); spiegare, quindi, gli step che portano alla sua risoluzione indicando infine il tempo di esecuzione"

Si procede utilizzando tre variabili u (ultimo indice del vettore), p (primo indice del vettore), m (indice corrispondente al punto medio tra u e p). Nel calcolare il punto medio m si considera la divisione tra interi prendendo sempre l’intero inferiore corrispondente alla divisione
All’inizio p corrisponde a 0, indice del primo elemento del vettore, mentre u a n-1, indice dell’ultimo elemento del vettore.
Si calcola il punto medio e si verifica se la chiave di ricerca è contenuta nella posizione m, in caso affermativo si è trovato l’elemento.
Se non è in posizione m allora si verifica se si può trovare nel sotto vettore di sinistra o di destra in base al valore della chiave e del valore dell’elemento in posizione m.

Nel caso in cui il valore in posizione m (v[m]) sia maggiore della chiave di ricerca (v[m]> key), significa che se esiste si troverà nel sotto vettore di sinistra per cui l’indice u è spostato in posizione m-1 (mentre p resta invariato), altrimenti si potrebbe trovare nel sotto vettore di destra, in questo caso p diventa m+1 (u resta invariato). Si ripete questa operazione con un ciclo while fino a quando p<=u e pos==-1 (non trovato), così procedendo si divide sempre il vettore in due e la complessità si riduce in modo significativo.
Per calcolare la complessità ipotizziamo che il numero di elementi n sia una potenza di 2, cioè n = 2k. Ad ogni iterazione la dimensione del vettore si dimezza e dopo k iterazioni diventa di dimensione 1, quindi nel caso peggio quando lo trovo nell’ultima iterazione, o non lo trovo, la complessità è k.

2k, 2k-1, 2k-2, … , 2k-k = 1
Nel caso peggiore eseguo k volte il ciclo (il passo 5 non viene eseguito), quindi la complessità è k = log2(n).
La ricerca dicotomica ha dunque complessità O(log2(n)).

TERZO QUESITO
" Supponiamo che in un albero binario ordinato sia inserita la seguente sequenza (nell'ordine della sequenza).
5,7,3,6,4,9,2,8,14,13. Indicare l'output delle visite InOrder, PreOrder, PostOrder effettuate dopo l'inserimento di tutta la sequenza"

ordine di visita InOrder: 9, 4, 2, 6, 8, 3, 14, 7, 13, 5
ordine di visita PreOrder: 5,7,3,6,4,9,2,8,14,13
ordine di visita PostOrder: 13,14,8,2,9,4,6,3,7,5

QUARTO QUESITO
"Descrivere la procedura di eliminazione (cancellazione) in una tabella hash a indirizzamento aperto"
Quando si cancella una chiave la cella viene marcata con DELETED e non con NULL
• La sequenza di scansione durante l’inserimento si interrompe quando trova un NULL oppure un
DELETED
– in questo modo le celle marcate DELETED vengono
riutilizzate
– piccola modifica rispetto allo pseudocodice già visto
• La sequenza di scansione durante la ricerca si interrompe quando trova un NULL, ma continua
quando trova un DELETED
– non occorre modificare lo pseudocodice già visto