Sab 24 Agosto, 15:30:12 - 2019

Autore Topic: Homework 5  (Letto 9517 volte)

0 Utenti e 1 Visitatore stanno visualizzando questo topic.

Offline vinkia

  • Guru
  • Professore Associato
  • *****
  • Post: 696
  • FeedBack: +70/-30
  • http://teamend.altervista.org/chi-siamo
    • Mostra profilo
    • TeamEnd applicazioni per Android e non solo...
Re: Homework 5
« Risposta #15 il: Mer 12 Gennaio, 22:52:46 - 2011 »
Era stato detto esplicitamente che gli homework necessari per i 2 punti all'esame dovevano essere 4 o a seconda dei casi addirittura 3. Adesso non voglio essere polemico, però cambiare le modalità adesso che sono scaduti 5 homework su 7 non mi sembra corretto.
Voglio dire, mi sembra ovvio che più di una persona ha preferito trascurare o saltare un homework per dedicarsi ad altre altre materie (esonero di calcolatori in primis).
Sia chiaro, non sto criticando il nuovo regolamento, forse è anche più giusto che sia così, però non si possono cambiare le regole a cose fatte.
O sbaglio?

Quoto, anche perchè che io sappia gli anni precedenti ne dovevano fare 4, non avevano la domanda di programmazione, prendevano 2 punti di bonus e non avevano tempi ristretti a causa delle proteste.
Detto questo, se io non avessi chiesto a D'Amore conferma a riguardo del doverne fare 4, probabilmente saremmo arrivati all'esame convinti di una cosa invece di un'altra!
Non preoccuparti solo di essere migliore dei tuoi contemporanei o dei tuoi predecessori. Cerca solo di essere migliore di te stesso.

http://teamend.altervista.org/chi-siamo

Offline Gc24

  • Direttore di Dipartimento
  • ***
  • Post: 1637
  • FeedBack: +112/-34
    • Mostra profilo
Re: Homework 5
« Risposta #16 il: Mer 12 Gennaio, 23:57:58 - 2011 »
Quoto, anche perchè che io sappia gli anni precedenti ne dovevano fare 4, non avevano la domanda di programmazione, prendevano 2 punti di bonus e non avevano tempi ristretti a causa delle proteste.
Detto questo, se io non avessi chiesto a D'Amore conferma a riguardo del doverne fare 4, probabilmente saremmo arrivati all'esame convinti di una cosa invece di un'altra!
infatti...speriamo che ci sia un po' di comprensione.. :)
((to.be())||(!to.be()))

Offline kupo

  • Studente
  • *
  • Post: 11
  • FeedBack: +1/-1
    • Mostra profilo
Re: Homework 5
« Risposta #17 il: Gio 13 Gennaio, 14:41:44 - 2011 »
Nel dubbio ho incominciato a fare questo assignment, ma non ho capito bene questa frase!

Il metodo dovra' avere costo lineare rispetto al massimo tra
le dimensioni dei due dizionari.


L'idea di fondo è prendere per forza di cose tutte le chiavi di un dizionario, l'attraversamento di tutti i nodi avrà dunque complessità O(n). Per ognuna delle chiavi trovate, bisogna cercare nell'altro dizionario un'altra uguale, ricerca che costerebbe nel caso medio O(logn)... ma in caso di un albero sbilanciato degenere in una lista collegata dovrebbe essere O(n).

Spero fin qui di non aver fatto errori madornali...  ::)

Che vuol dire allora che il metodo deve avere un costo lineare?!  ???

Offline Lorixx89

  • Professore Associato
  • *
  • Post: 641
  • FeedBack: +60/-14
    • Mostra profilo
Re: Homework 5
« Risposta #18 il: Gio 13 Gennaio, 16:23:05 - 2011 »
Se il 1° bst ha n nodi ed il secondo bst ha m nodi il testo specifica che l'algoritmo deve avere costo pari a O(max(n,m)) che è
un costo lineare. Giusto?

Poi non vorrei dire magari un'altra boiata, ma se si implementa l'algoritmo come hai detto te, Kupo, il costo risulterebbe O(nlogn) che
anche se di poco, è più che lineare.
« Ultima modifica: Gio 13 Gennaio, 16:25:08 - 2011 da Lorixx89 »

Offline gabry

  • Studente di Dottorato
  • ***
  • Post: 141
  • FeedBack: +21/-17
    • Mostra profilo
Re: Homework 5
« Risposta #19 il: Gio 13 Gennaio, 16:41:46 - 2011 »
Citazione
se si implementa l'algoritmo come hai detto te, Kupo, il costo risulterebbe O(nlogn) che
anche se di poco, è più che lineare.

piu` precisamente, se n e` la dimensione del primo dizionario, e m quella del secondo, il costo sarebbe O(nlogm)... cmq non penso che vada bene... a questo proposito, chiederei, se non e` troppo saperlo: per ottenere il costo computazionale richiesto, e` necessario che gli alberi siano degli AVL?
"cerco un centro di gravita` permanente..."
informatico per caso
_

Offline Lorixx89

  • Professore Associato
  • *
  • Post: 641
  • FeedBack: +60/-14
    • Mostra profilo
Re: Homework 5
« Risposta #20 il: Gio 13 Gennaio, 16:43:42 - 2011 »
Si scusa, la storia della m è stata una distrazione. A me una cosa che mi sta fuorviando è il fatto che i nodi non hanno riferimento al parent.

Edit: Va bhe è banale fare un metodo che lo trova.. risolto.
« Ultima modifica: Gio 13 Gennaio, 16:47:14 - 2011 da Lorixx89 »

Offline vinkia

  • Guru
  • Professore Associato
  • *****
  • Post: 696
  • FeedBack: +70/-30
  • http://teamend.altervista.org/chi-siamo
    • Mostra profilo
    • TeamEnd applicazioni per Android e non solo...
Re: Homework 5
« Risposta #21 il: Gio 13 Gennaio, 17:13:13 - 2011 »
Si scusa, la storia della m è stata una distrazione. A me una cosa che mi sta fuorviando è il fatto che i nodi non hanno riferimento al parent.

Edit: Va bhe è banale fare un metodo che lo trova.. risolto.

Bravo. Sei forte allora!
Non preoccuparti solo di essere migliore dei tuoi contemporanei o dei tuoi predecessori. Cerca solo di essere migliore di te stesso.

http://teamend.altervista.org/chi-siamo

Offline Lorixx89

  • Professore Associato
  • *
  • Post: 641
  • FeedBack: +60/-14
    • Mostra profilo
Re: Homework 5
« Risposta #22 il: Gio 13 Gennaio, 17:16:31 - 2011 »
Rispondere così non era necessario. Non volevo mica vantami per una cosa del genere..
« Ultima modifica: Gio 13 Gennaio, 17:20:37 - 2011 da Lorixx89 »

Offline MrMars

  • Studente
  • *
  • Post: 9
  • FeedBack: +1/-4
    • Mostra profilo
    • ilsatyricon.wordpress.com
Re: Homework 5
« Risposta #23 il: Gio 13 Gennaio, 18:08:19 - 2011 »
Si scusa, la storia della m è stata una distrazione. A me una cosa che mi sta fuorviando è il fatto che i nodi non hanno riferimento al parent.

Edit: Va bhe è banale fare un metodo che lo trova.. risolto.

D'Amore a lezione ha specificato che non è buona norma avere riferimenti al parent, perché occupano spazio per una cosa che si ottiene (appunto) in due righe, o con una scansione "intelligente" dell'albero. Quindi c'è poco da stupirsi che non l'abbiano messo.

Mi aggiungo invece alle perplessità sul costo lineare: anche a me le soluzioni che vengono in mente sono o(n^2) o al "massimo" o(n log m) (massimo nel senso di migliore)...

Offline ikki

  • Studente
  • *
  • Post: 5
  • FeedBack: +0/-1
    • Mostra profilo
Re: Homework 5
« Risposta #24 il: Gio 13 Gennaio, 18:52:36 - 2011 »
100 Domande per il tutor:

Possiamo dotare la classe BSTDictionaryImpl di metodi pubblici che non sono definiti nell'interfaccia BSTDictionary?

Possiamo utilizzare tali metodi all'interno del metodo commonKeys(BSTDictionary d1, BSTDictionary d2) anche se ciò significherebbe ricorrere al casting esplicito?

Quale sarà la dimensione degli alberi che verranno utilizzati nei test?

Quale sarà il timeout scelto per i test?

Grazie 1111101000

Offline maggio

  • Studente
  • *
  • Post: 28
  • FeedBack: +0/-3
    • Mostra profilo
Re: Homework 5
« Risposta #25 il: Gio 13 Gennaio, 19:51:42 - 2011 »
mi associo ad alcune lamentele... cambiare le regole in corsa non mi sembra corretto.

Offline kupo

  • Studente
  • *
  • Post: 11
  • FeedBack: +1/-1
    • Mostra profilo
Re: Homework 5
« Risposta #26 il: Gio 13 Gennaio, 20:40:20 - 2011 »
piu` precisamente, se n e` la dimensione del primo dizionario, e m quella del secondo, il costo sarebbe O(nlogm)... cmq non penso che vada bene... a questo proposito, chiederei, se non e` troppo saperlo: per ottenere il costo computazionale richiesto, e` necessario che gli alberi siano degli AVL?

Si, il costo è O(nlogn) con il mio algoritmo... era proprio per questo che chiedevo! Nella traccia non c'è nessun riferimento esplicito (mi sta venendo il dubbio che la devo leggere di nuovo) a strutture dati particolari... e se non mi sbaglio anche gli AVL hanno la stessa complessità O(logn) per la ricerca!  ???

Se devo leggere tutti i nodi di un dizionario, beh penso che dovrò per forza scorrerli giusto? -> O(n)
Per far tornare i conti servirebbe un costo di ricerca O(1)... e qui io mi arrendo  :(


Una domanda per il professore:
nel caso si consegnasse un codice che passa gli eventuali test ma non rispetta il vincolo di costo... sarà considerato non valido?
Se è possibile... si potrebbe essere leggermente più morbidi visto che era un assignment non previsto... ::)

Offline gabry

  • Studente di Dottorato
  • ***
  • Post: 141
  • FeedBack: +21/-17
    • Mostra profilo
Re: Homework 5
« Risposta #27 il: Gio 13 Gennaio, 20:48:26 - 2011 »
Citazione
e se non mi sbaglio anche gli AVL hanno la stessa complessità O(logn) per la ricerca!

aspetta: i BST hanno un costo O(h) sulla ricerca, dove h e` l'altezza... ma dal momento che se va male h puo` anche coincidere con n, la ricerca puo` costare, nel caso peggiore, O(n)... c'e` da dire che perche` ti capiti il caso peggiore deve andarti di sfiga, oppure l'input deve essere fatto in maniera "particolare"... cmq con inserimenti random il valore atteso dell'altezza e` O(log n)... la svolta dal BST ordinario a quello AVL e` proprio che in un AVL h e` O(log n), e quindi la ricerca, assieme all'inserimento e la rimozione, e` a sua volta O(log n), anche nel caso peggiore...

ho una domanda scema: nel metodo removeHigh(int key), e` possibile che il parametro passato non appartenga all'albero? non e` una questione di correttezza dell'input quella che sto ponendo, e` solo per chiarezza... dovrebbe essere si`, giusto? anche perche` se no non c'e` modo di svuotare l'albero del tutto...
« Ultima modifica: Gio 13 Gennaio, 20:54:36 - 2011 da gabry »
"cerco un centro di gravita` permanente..."
informatico per caso
_

Offline Stefano Millozzi

  • Prof
  • Studente di Dottorato
  • ******
  • Post: 242
  • FeedBack: +29/-51
    • Mostra profilo
Re: Homework 5
« Risposta #28 il: Ven 14 Gennaio, 09:04:14 - 2011 »
Citazione
Possiamo dotare la classe BSTDictionaryImpl di metodi pubblici che non sono definiti nell'interfaccia BSTDictionary?
SI

Citazione
Possiamo utilizzare tali metodi all'interno del metodo commonKeys(BSTDictionary d1, BSTDictionary d2) anche se ciò significherebbe ricorrere al casting esplicito?
NO, al metodo commonKeys nei test potrebbe essere passato un albero implementato con classi differenti dalle vostre

Citazione
Quale sarà la dimensione degli alberi che verranno utilizzati nei test?

fino a qualche migliaio di nodi

Citazione
Quale sarà il timeout scelto per i test?
5000ms sul mio PC portatile

Offline Mcfan

  • Studente di Dottorato
  • ***
  • Post: 192
  • FeedBack: +12/-3
    • Mostra profilo
Re: Homework 5
« Risposta #29 il: Ven 14 Gennaio, 09:41:10 - 2011 »
Ci sono altre clausole non scritte nel regolamento che dobbiamo rispettare?!?
« Ultima modifica: Ven 14 Gennaio, 09:43:13 - 2011 da Mcfan »