Domande esame di algoritmi

[Darèios89]

Ho alcune domande da farvi, sulle cui risposte non sono certo.

1)Data l' equazione di ricorrenza [tex]T(n)=4T(n/\alpha)+n^{\alpha}\log(n)[/tex], per quale valore del parametro alfa la sua soluzione è [tex]O(n^3)[/tex]


a)[tex]\alpha=1[/tex]
b) [tex]\alpha=2[/tex]
c) [tex]\alpha=3[/tex]
d) [tex]\alpha=4[/tex]


2) Siano dati n numeri in base b, ognuno di k cifre. Tali numeri possono essere ordinati in tempo:

a) [tex]\Theta(k(n+b))[/tex]
b) [tex]\Theta(n(k+b))[/tex]
c) [tex]\Theta(b(k+n))[/tex]
d) [tex]\Theta(bn+k))[/tex]


3) L' algoritmo Linear-Select prevede l' ordinamento di n/5 gruppi ognuno composto da 5 elementi. Il costo di tale operazione di ordinamento è calcolato nella equazione di ricorrenza, [tex]T(n)=T(n/5)+T(7/10*n)+cn[/tex] dal termine:

a) [tex]T(n/5)[/tex]
b) [tex]T(7/10n[/tex]
c) [tex]cn[/tex]
d) Nessuna delle risposte precedenti.



4) L' ordinamento topologico di un grafo orientato è unico:

a) Se il grafo è aciclico
b) Se il grafo non contiene archi
c) Se il grafo contiene un arco per ogni coppia di nodi
d) Se valgono entrambe le ipotesi a e c.



5) Siano A1, A2, A3 e A4 quattro array ordinate di n numeri distinti ciascuna. Si supponga di voler fondere le 4 array in un' unica array ordinata. Quanti confronti bisogna fare al più? (Scegliere la risposta più stretta).

a) n
b) 2n
c) 3n
d) 4n



Allora premetto che non è un mio compito ma sto postando per aiutare un mio collega, quindi ad alcune non abbiamo saputo rispondere e gradirei sapere la risposta corretta direttamente.


Per la prima e la seconda domanda non siamo riusciti a trovare una soluzione......per la terza abbiamo pensato alla risposta c, perchè nel testo mi sembra di avere letto che l' ordinamento è fatto linearmente.
Per la quarta, facendoci alcuni calcoli con dei grafi che abbiamo costruito avremmo messo la risposta d. Per finire nell' ultima domanda sempre in base ad alcuni disegni e calcoli io direi la risposta b.

Grazie e buone feste!!!

[hamming_burst]

"Darèios89":Ho alcune domande da farvi, sulle cui risposte non sono certo.

1)Data l' equazione di ricorrenza [tex]T(n)=4T(n/\alpha)+n^{\alpha}\log(n)[/tex], per quale valore del parametro alfa la sua soluzione è [tex]O(n^3)[/tex]


a)[tex]\alpha=1[/tex]
b) [tex]\alpha=2[/tex]
c) [tex]\alpha=3[/tex]
d) [tex]\alpha=4[/tex]

puoi provare a dare una risposta veloce tramite l'utilizzo del master

$n^{\alpha}\log(n) \in n^{log_{\alpha}(4)}$

e vedere ad occhio che per \alpha deve essere minore stretto di $log_{\alpha}(4)$ l'unico valore è quando $ log_{\alpha}(4) = 2$ cioè $\alpha=2$.
in aggiunta puoi ipotizzare la validità del terzo caso del master e trovare un $\epsilon$ e vedere che vale:
$n^{2}\log(n) \in \Omega(n^{log_{2}(4)+\epsilon})$
dimostrare che vale $O(n^3)$ è banale.

2) Siano dati n numeri in base b, ognuno di k cifre. Tali numeri possono essere ordinati in tempo:

a) [tex]\Theta(k(n+b))[/tex]
b) [tex]\Theta(n(k+b))[/tex]
c) [tex]\Theta(b(k+n))[/tex]
d) [tex]\Theta(bn+k))[/tex]

integer sort (oppure counting sort), dovrebbe essere la d)