Mar 16 Luglio, 00:10:12 - 2019

Autore Topic: Soluzioni esami recenti (parte di Algoritmi)  (Letto 9550 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline heavenriver

  • Global Moderator
  • Direttore di Dipartimento
  • *****
  • Post: 1060
  • FeedBack: +103/-67
  • z = z² + c
    • Mostra profilo
    • Sito web (Curriculum Vitae)
Soluzioni esami recenti (parte di Algoritmi)
« il: Sab 12 Gennaio, 21:44:33 - 2013 »
Ho svolto quasi tutti gli esami del 2011 e del 2012 e li ho uppati su pastebin, quindi ho pensato di condividerli con i bisognosi :P Se volete contribuire correggendo eventualmente i miei errori (non ho fatto girare il codice, quindi non garantisco che funzioni) oppure integrare con Modelli o con altri esami o con altre cose che non ho già messo su, oppure semplicemente aggiungere il vostro contributo o la vostra versione del codice, postate! Così facciamo una bella raccolta di (potenziali) soluzioni da lasciare ai posteri ;)
Per gli esercizi sui grafi ho usato questa implementazione con leggere modifiche a seconda della richiesta specifica della traccia.
In ordine decrescente di data:

12 settembre 2012 ~ Esercizio 2
24 luglio 2012 ~ Esercizio 2 | Esercizio 3
18 giugno 2012 ~ Esercizio 2 | Esercizio 3
22 febbraio 2012 ~ Esercizio 2
19 gennaio 2012 ~ Esercizio 2
11 novembre 2011 ~ Esercizio 3
14 settembre 2011 ~ Esercizio 2
21 giugno 2011 ~ Esercizio 2 | Esercizio 3
6 maggio 2011 ~ Esercizio 2 | Esercizio 3
4 marzo 2011 ~ Esercizio 2 | Esercizio 3
7 febbraio 2011 ~ Esercizio 3

Offline tEtO

  • Studente
  • *
  • Post: 19
  • FeedBack: +1/-0
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #1 il: Mer 16 Gennaio, 16:28:22 - 2013 »
Ciao, scusami ma sulla soluzione dell'esame del 19, esercizio 2, nel metodo ricorsivo findAll, quando fai la verifica della grandezza delle chiavi con quella data non andrebbero invertiti i controlli sui figli??
mi spiego meglio :

 if(n == null || (n.getKey() > key && !n.hasLeft()) || (n.getKey() < key && !n.hasRight())) return;


Se la chiave di n è maggiore di key significa che andremo nel figlio destro quindi il controllo andrebbe fatto su n.hasRight così che se non ha figlio destro possiamo restituire il valore null.

Lo stesso vale per qualche riga dopo, dopo l'add ..

Spero di non aver detto una scemenza e di essermi fatto capire..   ;D

Offline heavenriver

  • Global Moderator
  • Direttore di Dipartimento
  • *****
  • Post: 1060
  • FeedBack: +103/-67
  • z = z² + c
    • Mostra profilo
    • Sito web (Curriculum Vitae)
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #2 il: Ven 25 Gennaio, 21:08:12 - 2013 »
Scusa se rispondo così tardi ma non avevo notato il tuo post :asd:
No, non penso che i controlli vadano invertiti, perché n.getKey() restituisce la chiave sul nodo corrente, e key è la chiave da trovare. Quindi, se la chiave del nodo corrente è maggiore di quella da trovare, bisogna scendere nel sottoalbero sinistro, dove si troveranno chiavi più piccole. Viceversa se la chiave del nodo corrente è minore di quella da trovare, bisogna scendere nel sottoalbero destro, dove si troveranno chiavi più grandi.
Tutto chiaro?

Offline Ale_G

  • Neo-Laureato
  • **
  • Post: 76
  • FeedBack: +4/-3
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #3 il: Mer 13 Febbraio, 16:02:48 - 2013 »
Io non ho capito che cosa fa il tuo potatura dell'esame del 18 giugno 2012 esercizio 2

Offline davidepic91

  • Studente di Dottorato
  • ***
  • Post: 232
  • FeedBack: +6/-39
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #4 il: Dom 17 Febbraio, 18:59:43 - 2013 »
Esame 24/07/2012 . Nell' esercizio 2c) ho trovato un piccolo errore sui parametri formali e attuali :) . Infatti il primo metodo ritorna sempre un nodo null perchè il secondo metodo non fa side-effect sul Nodo out . Non so se mi sono spiegato .
Comunque io l'avrei fatto così:

public Node maxCompleto(){
   return maxCompleto(root);
}
private Node maxCompleto(Node n){
   if(isCompleto(n) return n;
   if(hasLeft(n)) return maxCompleto(left(n));
   if(hasRight(n)) return maxCompleto(right(n));
   return null ;
}

EDIT : errore simile in 22-02-12 esercizio 3c)
« Ultima modifica: Ven 22 Febbraio, 19:27:30 - 2013 da davidepic91 »

Offline ael

  • Neo-Laureato
  • **
  • Post: 94
  • FeedBack: +10/-0
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #5 il: Lun 18 Febbraio, 16:14:57 - 2013 »
il metodo potatura del 18 non mi sembra del tutto giusto.

Offline Xzed

  • Studente di Dottorato
  • ***
  • Post: 228
  • FeedBack: +2/-9
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #6 il: Lun 18 Febbraio, 18:37:51 - 2013 »
Nell'esame del 12 Settembre 2012, nel punto c dell'esercizio 2 hai usato il metodo inOrder, ma vedendo come si sviluppa l'albero nella slide del mergeSort del professore penso che sia più adatto PreOrder.

Offline heavenriver

  • Global Moderator
  • Direttore di Dipartimento
  • *****
  • Post: 1060
  • FeedBack: +103/-67
  • z = z² + c
    • Mostra profilo
    • Sito web (Curriculum Vitae)
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #7 il: Dom 24 Febbraio, 20:48:24 - 2013 »
Confermo le segnalazioni di davidepic91 e di Xzed :sisi: Grazie!
Il metodo potatura rimuove tutti i nodi con chiave non compresa in un intervallo [a, b]. Ael, cos'è che non ti torna del codice?

Offline Mhz

  • Neo-Laureato
  • **
  • Post: 62
  • FeedBack: +3/-3
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #8 il: Ven 24 Maggio, 16:17:10 - 2013 »
Ho un dubbio sulla implementazione della classe Grafo proposta http://pastebin.com/0VCHXeSm
Nella classe Vertex il metodo public addAdjacent(Vertex v); non dovrebe ricevere un Edge?
public addAdjacent(Edge e)

Offline heavenriver

  • Global Moderator
  • Direttore di Dipartimento
  • *****
  • Post: 1060
  • FeedBack: +103/-67
  • z = z² + c
    • Mostra profilo
    • Sito web (Curriculum Vitae)
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #9 il: Ven 24 Maggio, 22:57:14 - 2013 »
Ho un dubbio sulla implementazione della classe Grafo proposta http://pastebin.com/0VCHXeSm
Nella classe Vertex il metodo public addAdjacent(Vertex v); non dovrebe ricevere un Edge?
public addAdjacent(Edge e)

Credo che la versione con Edge come parametro passato sia effettivamente più comune, ma sono entrambi valide che io sappia. :sisi:

Offline x-file

  • Studente
  • *
  • Post: 17
  • FeedBack: +1/-0
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #10 il: Lun 15 Luglio, 10:46:55 - 2013 »
sviluppatore android

Offline lucanox

  • Professore Associato
  • *
  • Post: 587
  • FeedBack: +61/-35
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #11 il: Lun 15 Luglio, 11:38:51 - 2013 »
per me il metodo append è theta(n)... bit O(nlogn)..

Offline unòzer

  • Studente di Dottorato
  • ***
  • Post: 194
  • FeedBack: +10/-4
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #12 il: Lun 15 Luglio, 14:44:25 - 2013 »
per me il metodo append è theta(n)... bit O(nlogn)..

D'accordissimo!

1a) c'è un ciclo for è banalmente theta(n)

2a) T(n) = T(n/2) + nC = T(n/2i) + inC
      la ricorsione si ferma per i=log n quindi,
      T(n) = O(n log(n) )

Offline lucanox

  • Professore Associato
  • *
  • Post: 587
  • FeedBack: +61/-35
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #13 il: Lun 15 Luglio, 15:11:16 - 2013 »
perfetto :D sto cominciando a capire qualcosa allora  :asd:

Offline lucanox

  • Professore Associato
  • *
  • Post: 587
  • FeedBack: +61/-35
    • Mostra profilo
Re:Soluzioni esami recenti (parte di Algoritmi)
« Risposta #14 il: Lun 15 Luglio, 15:41:35 - 2013 »
qua dicono bit theta di log^2 n.. http://solo.dis.uniroma1.it/index.php?topic=16365.0