Testi di esami recenti

Per i testi marcati come Svolto è disponibile la registrazione dello svolgimento fatta dal docente. Tutte queste registrazioni si trovano in mp4 nella cartella Esami svolti dentro la cartella condivisa del corso su Google Drive.

Esercizi degli anni precedenti

Testo degli esercizi della prova intermedia del 14/04/2016
La soluzione di questi esercizi si trova al link http://twiki.di.uniroma1.it/pub/Intro_algo/AD/WebHome/SolProvaInt.pdf

1. Si descriva la funzione di estrazione del massimo in un MaxHeap, analizzandone il tempo di esecuzione.

2. Si descriva l'algoritmo per la trasformazione di un array qualunque in un MaxHeap, analizzandone il tempo di esecuzione.

3. Si descriva l’algoritmo di fusione di due array di interi di dimensione n ed m rispettivamente, analizzandone il tempo di esecuzione.

4. Si descriva una delle due versioni fornite a lezione dell’algoritmo di partizionamento di un array di interi, intorno a un pivot.

5. Si risponda alle seguenti domande, motivando brevemente la risposta. a. Si confronti n2lg n con n2: è vero che n2 = Θ(n2 lg n) oppure n2 = O(n2lgn) b. Se si dimostra che un algoritmo ha tempo di esecuzione Θ(n2) nel caso peggiore, posso dedurne che nel caso migliore terminerà in O(n2) passi?

6. Si risponda alle seguenti domande, motivando brevemente la risposta. a. Si confronti nlg n con n: è vero che n = Θ(n lg n) oppure n = O(nlgn) ? b. Se si dimostra che un algoritmo ha tempo di esecuzione Θ(n) nel caso peggiore, posso dedurne che nel caso migliore terminerà in O(n) passi?

7. a. Si confronti nlg n2 con n2lg n: è vero che nlg n2= Ω(n2lg n) oppure n2lg n= O(nlg n2)? b. Si risponda alla seguente domanda, motivando brevemente la risposta. Se si dimostra che un algoritmo ha tempo di esecuzione Θ(n2) nel caso peggiore, è possibile che in qualche caso l'algoritmo termini in Θ(nlg n) passi?

8. a. Si confronti n2lg n con nlg2 n: è vero che nlg2 n = Ω(n2lg n) oppure nlg2 n = O(n2lg n)? b. Si risponda alla seguente domanda, motivando brevemente la risposta. Se si dimostra che un algoritmo ha tempo di esecuzione Θ(n) nel caso peggiore, è possibile che in qualche caso l'algoritmo termini in Θ(1) passi?

9. Scrivere un algoritmo che verifichi se esiste almeno una coppia di conoscenti la cui età differisce di 1, dati in input: • un vettore di interi C di dimensione n. Tali interi sono le età di n persone differenti; • una matrice quadrata e simmetrica A di dimensione nxn, a valori 0 ed 1. A[i,j] é uguale ad 1 se e solo se la persona i conosce la persona j. L'algoritmo dovrebbe dare in output una coppia con le coordinate di due conoscenti le cui età differiscono di 1 se ce ne sono oppure la coppia (0,0). Valutare asintoticamente il tempo di esecuzione dell’algoritmo presentato.

10. Si definisce punto singolare di una matrice quell'elemento che gode della proprietà di essere massimo di riga e minimo di colonna. Scrivere un algoritmo che riceve in input una matrice A e dia in output gli indici di un punto singolare in A, (0,0) se non ce ne sono. Si valuti asintoticamente il tempo di esecuzione dell’algoritmo proposto.

11. Si definisce punto di sella di una matrice quell'elemento che gode della proprietà di essere minimo di riga e massimo di colonna. Scrivere un algoritmo che riceve in input una matrice A e dia in output gli indici di un punto di sella in A, (0,0) se non ce ne sono. Si valuti asintoticamente il tempo di esecuzione dell’algoritmo proposto.

12. Scrivere un algoritmo che verifichi se esiste almeno una coppia di conoscenti coetanei, dati in input: • un vettore di interi C di dimensione n. Tali interi sono le età di n persone differenti; • una matrice quadrata e simmetrica A di dimensione nxn, a valori 0 ed 1. A[i,j] é uguale ad 1 se e solo se la persona i conosce la persona j. L’algoritmo dovrebbe dare in output una coppia con le coordinate dei due conoscenti coetanei se ce ne sono oppure la coppia (0,0). Valutare asintoticamente il tempo di esecuzione dell’algoritmo presentato.

Testi degli esercizi sulla prima parte della prova di esame del 7/06/2016: Testo1A7Giugno16.pdf, Testo1B7Giugno16.pdf

Testi degli esercizi sulla seconda parte della prova di esame del 7/06/2016: Testo2A7Giugno16.pdf, Testo2B7Giugno16.pdf, Testo2C7Giugno16.pdf, Testo2D7Giugno16.pdf

Testi degli esercizi sulla seconda parte della prova di esame del 30/06/2016: Testo2A30Giugno16.pdf, Testo2B30Giugno16.pdf

Testi degli esercizi della prova di esame del 19/09/2016: IntrAlgSett16-2.pdf

Testi degli esercizi della prova di esame del 1 /02/2017: IntrAlgFeb172.pdf

Testi degli esercizi della prova di esame del 28 /07/2017: EsIntrAlg28Giu17testoA.pdf,

EsIntrAlg28Giu17testoB.pdf