Holgers lille NTNU-tråd | *Se første post for spørsmål om hybel*

[TWA]

Det er så og si alltid faglærer. Kanskje jobben blir dyttet over på stipendiater iblant.

I de store grunnfagene er det som regel vit.ass-er/stipendiater.

[dTd]

yAy, studweb er nede og jeg får ikke sjekket hvor jeg har eksamen i morgen... Får bare håpe på at det er på spektrum slik som det to andre... Mener det stod det når jeg sjekka sist eksamen, men kan hende jeg blingsa og så på den første...

 

Evt andre steder man kan finne det ut?

[Tosha0007]

Her

[dTd]

Takker!

Da slipper jeg å bekymre meg for å ende opp på feil lokale ihvertfall

[Matsemann]

Da var første 60 kroners eksamen overstått.

[voident]

Da var første 60 kroners eksamen overstått.

 

Med bestått?

[bkak]

Da var første 60 kroners eksamen overstått.

Hørte algdat skulle være på Dragvoll i dag ja.

[haarod]

Hvordan gikk det? Litt usikker på effektiviteten til algoritmene mine

[Matsemann]

Fikk ikke noe vettugt svar på 3c, men fikk til 3b i lineær tid og samme med 3a. Litt usikker på om mitt svar i 3a virker i alle tilfeller, men tror den gjør det.

[kloffsk]

Hva var 3c?

[Lycantrophe]

Max-flyt.

[sindreij]

Fikk ikke noe vettugt svar på 3c, men fikk til 3b i lineær tid og samme med 3a. Litt usikker på om mitt svar i 3a virker i alle tilfeller, men tror den gjør det.

Hvordan fikk du til 3b i linær tid?

[Lycantrophe]

Traverser treet og dytt inn i hash (O(n) for traversingen, O(1) for innsetting). O(1) for å hente ut.

Endret 14. desember 2011 av Lycantrophe

[sindreij]

Kom så langt, spørsmålet er hva du dytter inn i hashen. Dytter du inn alle foreldrene, er det lg(n) foreldre, og du får O(n lg(n))

[Lycantrophe]

Du lagrer barnet som key og parent som value. Så henter du ut parent og slår opp på nytt til du har enten roten eller den du leter etter. Alle oppslag skjer i konstant tid.

Endret 14. desember 2011 av Lycantrophe

[sindreij]

Du lagrer barnet som key og parent som value. Så henter du ut parent og slår opp på nytt til du har enten roten eller den du leter etter. Alle oppslag skjer i konstant tid.

Ja, men det blir (i snitt) lg n oppslag. lg n oppslag i konstant tid = O(lg n). Altså blir det O(n) for å lage tabellen og O(lg n) for å sjekke om en er etterkommer, og ikke O(1) som oppgaven spurte etter.

[Matsemann]

Dfs, der man setter venstre verdi på vei ned, høyre på vei opp. Lagrer i tabell for konstant oppslag.

Ser at e har 5 og 6 som ligger i mellom 2 og 9 ergo er det en etterfølger.

 

Vet ikke hvordan du gjorde hashgreiene, men andre brukte hash og fikk tregere enn n.

[Lycantrophe]

Oh, den var sweet. Sikkert riktig.

[sindreij]

Dfs, der man setter venstre verdi på vei ned, høyre på vei opp. Lagrer i tabell for konstant oppslag.

Ser at e har 5 og 6 som ligger i mellom 2 og 9 ergo er det en etterfølger.

 

Vet ikke hvordan du gjorde hashgreiene, men andre brukte hash og fikk tregere enn n.

Genialt, nå kommer jeg til å irritere meg i lang tid over at jeg ikke kom på det.... Hadde en slags sånn løsning på tunga (men bare ett tall pr node), men den virket ikke. Såvidt jeg vet er det ikke mulig å gjøre hash i linær tid, å samtidig få konstant oppslag av etterkommer (min løsning brukte hashing, men O(n*lg(n)) for å generere og O(1) for å slå opp, med en todimensjonal hash-tabell.

Endret 14. desember 2011 av sindreij

[haarod]

Jeg brukte også DFS i den, men jeg skrev ikke at man skulle lagre verdiene i en hash-tabell kun at man enkelt kunne sjekke om start- og sluttid var henholdsvis høyere og mindre. Dessuten så er vel hash-tabeller O(n) i worst-case, på samme måte som lenkede lister.

 

På 3c brukte jeg en slags bipartitt-matching graf med en ekstra node mellom skuespillere og scener, men om det fungerer er jeg ikke helt sikker på.

 

I oppgave 3a brukte jeg Floyd-Warshall som er O(n³) noe som vel ikke er helt optimalt men..