SoloDIAG

III Anno - BIAR => Corsi della triennale non più erogati => Fondamenti di Informatica II (fino A.A. 2013/14) => Topic aperto da: heavenriver - Sab 12 Gennaio, 21:44:33 - 2013

Titolo: Soluzioni esami recenti (parte di Algoritmi)
Inserito da: heavenriver - 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 (http://pastebin.com/0VCHXeSm) con leggere modifiche a seconda della richiesta specifica della traccia.
In ordine decrescente di data:

• 12 settembre 2012 (http://www.dis.uniroma1.it/~fiii/esame/AA%202011-12/5.appello--12-09-2012/fiii20120912_FI2.pdf) ~ Esercizio 2 (http://pastebin.com/QCaz8nui)
• 24 luglio 2012 (http://www.dis.uniroma1.it/~fiii/esame/AA%202011-12/4.appello--24-07-2012/fiii20120724_FI2.pdf) ~ Esercizio 2 (http://pastebin.com/Qe3pUrHP) | Esercizio 3 (http://pastebin.com/NFV0vEQ2)
• 18 giugno 2012 (http://www.dis.uniroma1.it/~fiii/esame/AA%202011-12/3.appello--18-06-2012/fiii20120618_FI2.pdf) ~ Esercizio 2 (http://pastebin.com/GaeVva63) | Esercizio 3 (http://pastebin.com/PJhd0ijK)
• 22 febbraio 2012 (http://www.dis.uniroma1.it/~fiii/esame/AA%202011-12/2.appello--22-02-2012/algoritmi/fiii20120222_FI2.pdf) ~ Esercizio 2 (http://pastebin.com/afYnauFf)
• 19 gennaio 2012 (http://www.dis.uniroma1.it/~fiii/esame/AA%202011-12/1.appello--19-01-2012/algoritmi/fi2-alg/20120119_FI2_DISTRIBUITO.pdf) ~ Esercizio 2 (http://pastebin.com/GrDze8sn)
• 11 novembre 2011 (http://www.dis.uniroma1.it/~fiii/esame/AA%202010-11/straordinario--11-11-2011/algoritmi/fiii20111111_F2.pdf) ~ Esercizio 3 (http://pastebin.com/Bxngj3yA)
• 14 settembre 2011 (http://www.dis.uniroma1.it/~fiii/esame/AA%202010-11/4.appello--14-09-2011/algoritmi/fiii20110914_F2.pdf) ~ Esercizio 2 (http://pastebin.com/91aSRgED)
• 21 giugno 2011 (http://www.dis.uniroma1.it/~fiii/esame/AA%202010-11/3.appello--21-06-2011/algoritmi/fiii20110621_F2.pdf) ~ Esercizio 2 (http://pastebin.com/KS4m9tpi) | Esercizio 3 (http://pastebin.com/R980ht2J)
• 6 maggio 2011 (http://www.dis.uniroma1.it/~fiii/esame/AA%202010-11/straordinario--06-05-2011/algoritmi/fiii20110506_F2.pdf) ~ Esercizio 2 (http://pastebin.com/iUtNEM5s) | Esercizio 3 (http://pastebin.com/ydWvYCwC)
• 4 marzo 2011 (http://www.dis.uniroma1.it/~fiii/esame/AA%202010-11/2.appello--04-03-2011/algoritmi/fiii20110304.pdf) ~ Esercizio 2 (http://pastebin.com/cnFQTCn1) | Esercizio 3 (http://pastebin.com/sSbpk0R1)
• 7 febbraio 2011 (http://www.dis.uniroma1.it/~fiii/esame/AA%202010-11/1.appello--07-02-2011/algoritmi/fiii20110207_F2_compitoA.pdf) ~ Esercizio 3 (http://pastebin.com/aTPYjJPv)
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: tEtO - 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
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: heavenriver - 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?
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: Ale_G - 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
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: davidepic91 - 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)
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: ael - Lun 18 Febbraio, 16:14:57 - 2013
il metodo potatura del 18 non mi sembra del tutto giusto.
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: Xzed - 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.
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: heavenriver - 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?
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: Mhz - Ven 24 Maggio, 16:17:10 - 2013
Ho un dubbio sulla implementazione della classe Grafo proposta http://pastebin.com/0VCHXeSm (http://pastebin.com/0VCHXeSm)
Nella classe Vertex il metodo public addAdjacent(Vertex v); non dovrebe ricevere un Edge?
public addAdjacent(Edge e)
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: heavenriver - Ven 24 Maggio, 22:57:14 - 2013
Ho un dubbio sulla implementazione della classe Grafo proposta http://pastebin.com/0VCHXeSm (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:
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: x-file - Lun 15 Luglio, 10:46:55 - 2013
Soluzione Personale GIUGNO 2011.

- TESTO -> http://www.dis.uniroma1.it/~fiii/esame/AA%202010-11/3.appello--21-06-2011/algoritmi/fiii20110621_F2.pdf (http://www.dis.uniroma1.it/~fiii/esame/AA%202010-11/3.appello--21-06-2011/algoritmi/fiii20110621_F2.pdf)

Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: lucanox - Lun 15 Luglio, 11:38:51 - 2013
per me il metodo append è theta(n)... bit O(nlogn)..
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: unòzer - 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) )
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: lucanox - Lun 15 Luglio, 15:11:16 - 2013
perfetto :D sto cominciando a capire qualcosa allora  :asd:
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: lucanox - 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
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: yoshy87 - Lun 15 Luglio, 15:51:03 - 2013
In questo esame viene richiesto il costo in termini di spazio del metodo

http://www.dis.uniroma1.it/~fiii/esame/AA%202011-12/4.appello--24-07-2012/fiii20120724_FI2.pdf

come si calcola?  :oooo: :help:
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: unòzer - Lun 15 Luglio, 16:20:24 - 2013
Secondo me è O(n) con n numero di elementi dell'array. Perché ad ogni passo ricorsivo salva in temp un elemento dell'array per poi invertirlo.
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: heavenriver - Mar 16 Luglio, 08:40:41 - 2013
Secondo me è O(n) con n numero di elementi dell'array. Perché ad ogni passo ricorsivo salva in temp un elemento dell'array per poi invertirlo.

Ragionevole, concordo. Più in generale, per "spazio" si intende quanto occupa in memoria rispetto alla dimensione dell'input :sisi:
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: Vagabond - Dom 08 Settembre, 18:56:10 - 2013
Ciao ragazzi. Come fareste il punto b (rendere iterativo il metodo) del primo esercizio del 11 Novembre 2011?

public class mistero {
   
   private static double mistero(double[] a, int i, double x){
      if(i == a.length-1) return a;
      return a + x*mistero(a,i+1,x);
   }
   
   public static double mistero(double[] a, double x){
      return mistero(a,0,x);
   }
}
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: heavenriver - Lun 09 Settembre, 09:25:08 - 2013
E' un semplice metodo che calcola la somma dei valori contenuti in un array. Basta fare un banale ciclo for per convertirlo in iterativo :sisi:
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: lucanox - Lun 09 Settembre, 10:12:26 - 2013
non calcola la somma dei valori..  moltiplica i valori a* x e li somma .. per esempio dato un array di double { 1.0 , 2.0, 3.0  } e un double x (per esempio 2.0  )l'output sarà 1.0 +2.0*(2.0+2.0*(3.0+ 2.0*(1.0))) = 25.0
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: Giurina - Lun 09 Settembre, 14:39:24 - 2013
non calcola la somma dei valori..  moltiplica i valori a* x e li somma .. per esempio dato un array di double { 1.0 , 2.0, 3.0  } e un double x (per esempio 2.0  )l'output sarà 1.0 +2.0*(2.0+2.0*(3.0+ 2.0*(1.0))) = 25.0

Io farei:

INT m = a[a.length-1];
For(INT i = a.length-2; i>= 0; i--){
     m = m per x;
     m += a;
}
Return m;

Controlla se è giusto che l'ho fatto al volo e scritto con il cell
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: Giurina - Mar 10 Settembre, 12:18:42 - 2013
Ragazzi, qualcuno ha fatto il problema 3 del compito del 14/09/2011?
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: ciaociao - Mar 10 Settembre, 13:21:11 - 2013
Ragazzi, qualcuno ha fatto il problema 3 del compito del 14/09/2011?

Ho provato a farlo sfruttando il DFS ed aggiungendo ai vertici un campo int per memorizzare l'altezza dell'albero DFS  a cui si trova; ho scritto lo pseudocodice supponendo di aver gia settato tutti i vertici e gli spigoli unexplored:

Algorithm DFS(G, v)
Setlabel(v, visited)
For all e ∈ G.incidentEdge(v)
     If getlabel(e) = unexplored
     W <- opposite(v,e)
     If getlabel(w) = unexplored
         Setlabel(w, discovery)
         DFS(G,w)
     Else if w.getaltezza() = v.getaltezza() setlabel(e, cross)
     Else if w.getaltezza() > v.getaltezza() setlabel(e, forward)
     Else setlabel(e, back)



Back (v,w) = w è un antenato di v nell'albero degli archi discovery
Forward (v,w) = w è nel livello successivo di v nell'albero degli archi discovery
Cross (v,w) = w nello stesso livello di v nell'albero degli archi discovery

Che ne dite? Ha senso?
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: Giurina - Mer 11 Settembre, 09:38:18 - 2013
Domanda sull'esame dell' 11/11/2011
Il problema 2b dice:
Citazione
istanziare(in java) il PQ-sort nel caso di coda di priorita implementata con lista ordinata e confrontarlo con l'insertion-sort(descritto in java)

Sulle slide c'è scritto:
Citazione
Insertion-sort è una variante di PQ-sort dove la coda di priorità  è implementata con una sequenza ordinata

Quando mi chiede di confrontarli cosa devo fare visto che in teoria sono la stessa cosa?
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: Giurina - Mer 11 Settembre, 11:03:46 - 2013
Del problemama 3 ho svolto il punto c che nelle soluzioni gia postate non c'era;
Secondo voi va bene??????
Codice: [Seleziona]
public boolean compute(String x){
      Return compute( x, this.root(), 0); // ho supposto che il grafo abbia una radice che rappresenta lo stato iniziale
}

Public boolean compute(string x, vertex r, int i){
     If (i<x.length) return r.isFinal();   //isFinal() ritorna un booleano a seconda se lo stato n è finale(true) o no(false)
     Char c = x.charAt(i);
     Iterator<edge> it = incidentEdge(r).iterator();
     While(it.hasNext()) {
          Edge e = it.next;
          If (e.getSimbolo() = c) {
              Vertex v = opposite(r, e);
              return compute(x, v, i+1);
          }
      }
      Return false;
}
Titolo: Re:Soluzioni esami recenti (parte di Algoritmi)
Inserito da: yellow - Sab 14 Settembre, 21:17:44 - 2013
Vorrei chiedere secondo voi se è esatta questa implementazione per il problema 2 di questo testo d'esame http://www.dis.uniroma1.it/~fiii/esame/AA%202011-12/5.appello--12-09-2012/fiii20120912_ASD.pdf
Grazie!
qui il codice: http://pastebin.com/wBnzyxzz
o qui sotto:
Codice: [Seleziona]
public class RecursionTree{
 
        private RecursionNode nodo;
        private RecursionTree root;
        private RecursionTree figlioS;
        private RecursionTree figlioD;
        private countNode;
       
        public RecursionTree(RecursionNode n){}
        public RecursionTree(){}
       
        public int size(){}
        public RecursionTree getRoot(){}
        public RecursionNode getNode(){}
        //se il RecursionTree è vuoto questo metodo aggiunge la radice
        public RecursionTree addFiglio(){}
        private RecursionTree aggFiglioS(RecursionNode fs){}
        private RecursionTree aggFiglioD(RecursionNode fd){}
        private RecursionTree getFiglioS(){}
        private RecursionTree getFiglioD(){}
        private RecursionTree removeFiglioS(){}
        private RecursionTree removeFiglioD(){}
        public RecursionTree remove(){}
        private boolean isLeaf(){}
        private RecursionTree removeInternal(RecursionNode n){}
        public RecursionTree removeExternal(RecursionNode n){}
       
       
       
       
       
        public static RecursionTree mergeSort(int[] a){
                RecursionTree result=new RecursionTree();
                return mergesortRic(a,0,a.length-1,result);
        }
       
       
       
        public static RecursionTree mergeSortRic(int[] a,int i, int j, RecursionTree tree){
                if(i>=j) return tree;
               
               
                else{
                        int medio=(i+j)/2;
                        mergeSortRic(a,i,medio,tree.getFiglioS());
                        mergeSortRic(a,medio+1,j,tree.getFiglioD());
                        return tree.addFiglio(merge(a,i,medio,j,tree));
                }
                // i while hanno un costo di O(2((j-1)+1))
                //il mergeSort ha funzione T(n)=T(n/2)+T(n/2)+nc2,T(0)=c1; dunque 2T(n/2)+nc2 per il master Theorem 2==2 e quindi O(n^1*log(n)) come già sapevamo
                //poichè le operazioni sugli alberi sono fatte sequenzialmente il loro costo è O(1) per ogni inserimento di un nodo e quindi il costo totale è O(n)
                // il costo totale di mergeSort(int[] a) è dunque O(nlogn)
        public static RecursionTreee merge(int[] a,int i, int medio, int j, RecursionTree tree){
               
                int it1=i;
                int it2=medio+1;
                int[] aux=new int[(j-i)+1];
                int countAux=0;
/*              while(it1<=j){
                        aux[countAux++]=a[i++];
                }
                iti=i;
                countAux=0;
        */
                while(it1<=medio && it2<=j){
                        if(a[it1]<=a[it2]){
                                aux[countAux++]=a[it1++];
                        }else{
                                aux[countAux++]=a[it2++]
                        }
                       
                }
                while(it1<=medio){
                        aux[countAux++]=a[it1++];
                }
                while(it2<=j){
                        aux[countAux++]=a[it2++];
                }
                countAux=0;
                it1=i;
                while(i<=j){
                        a[it1++]=aux[countAux++];
                }
                return new RecursionTree(aux);
       
        }
        //costo O(n) dove n è il numero di nodi quindi size(), poichè visita tutti i nodi una sola volta
        public static void preOrder(RecursionTree t){
                if(t==null) return;
                else{
                        System.out.println(t.getNode().geElement());
                        preOrder(t.getFiglioS());
                        preOrder(t.getFiglioD());
                }
       
        }