Tags:
create new tag
view all tags

Testi di esami recenti

Tipo Data Testo in pdf Svolto
Esame 18/02/2021 2021-02-18_Esame.pdf Si
Esame 28/01/2021 2021-01-28_Esame.pdf Si
Esame 10/09/2020 2020-09-10_Esame.pdf - Note alla correzione Si
Esame 07/07/2020 2020-07-07_Esame.pdf - Note alla correzione No
Esame (testo A) 11/06/2020 am 2020-06-11_Esame_A_Caminiti.pdf - Soluzioni Si
Esame (testo B) 11/06/2020 pm 2020-06-11_Esame_B_Caminiti.pdf - Soluzioni Si
Autovalutazione pre esame 03/06/2020 2020-06-03_Autovalutazione.pdf - Soluzioni No
Esame (straordinario) 07/05/2020 Esame2020_05_07.pdf No
Esame 03/02/2020 Esame2020_02_03.pdf Si
Esame 13/01/2020 Esame2020_01_13.pdf Si
Esame (straordinario) 05/11/2019 Esame2019_11_05.pdf Si
Esame 18/09/2019 Esame2019_09_18.pdf No
Esame 05/07/2019 Esame2019_07_05.pdf Si
Esame 10/06/2019 Esame2019_06_10.pdf Si
Esonero (secondo) 31/05/2018 Esonero2_2018_05_31.pdf No
Esonero (primo) 19/04/2018 Esonero1_2018_04_19.pdf No

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

Edit | Attach | Watch | Print version | History: r16 < r15 < r14 < r13 < r12 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r16 - 2021-02-26 - SaverioCaminiti






 
Questo sito usa cookies, usandolo ne accettate la presenza. (CookiePolicy)
Torna al Dipartimento di Informatica
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2021 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback