Gå til innhold

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


HolgerL

Hvilket sted tilhører du?  

1 457 stemmer

  1. 1. Velg ett av alternativene

    • Dragvoll
      254
    • Gløshaugen
      1019
    • Annet
      202


Anbefalte innlegg

Skrevet

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.

Videoannonse
Annonse
Skrevet

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?

Skrevet

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?

Skrevet (endret)

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 av Lycantrophe
Skrevet

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.

Skrevet

nestedset.png

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.

Skrevet (endret)

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 av sindreij
Skrevet

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..

Opprett en konto eller logg inn for å kommentere

Du må være et medlem for å kunne skrive en kommentar

Opprett konto

Det er enkelt å melde seg inn for å starte en ny konto!

Start en konto

Logg inn

Har du allerede en konto? Logg inn her.

Logg inn nå
×
×
  • Opprett ny...