FAQ

Om det du lurer på ikke er besvart her, ta gjerne også en kikk på sidene om forelesninger, øvinger, pensum og eksamen.

Om øvingsopplegget

Hvis jeg har gjort øvingsopplegget før, må jeg gjøre det om igjen?

Nei, det trenger du ikke. Mer informasjon finner du på øvingssiden.

Programmet mitt fungerer lokalt men ikke når jeg laster opp!

Det er gode sjanser for at det er tilfeller du ikke har tatt høyde for. Testsettene på serveren er større og mer omfattende enn eksemplene.

Kan dere se på koden min?

Helst ikke. Ta den med til en studass – det er det de er der for.

Er det mulig å prøve seg på øvingene etter fristen har gått ut?

Ja, det er mulig. Vi har en «sandkasse» i INGInious, som er tilgengelig som et eget «fag». Her vil alle øvingene bli tilgjengeliggjort etter fristen har gått ut. Dette er for egen læring for dem som vil kikke mer på øvingene, og vil ikke kunne gi godkjenning for øvingen dersom den ikke allerede er bestått før fristen.

Om eksamen

Hva kan jeg spørre faglærer om under eksamen?

I praksis kan vi ikke svare på individuelle spørsmål. Hvis du mener vi bør gi en felles kunngjøring om noe, så gi gjerne beskjed om det; ellers kan du gi oss beskjed i etterkant, dersom det er noe du mener vi bør ta hensyn til under sensuren. Vi har også lagt ut mer info om dette.

Må jeg skrive kode eller pseudokode på eksamen?

Hovedpoenget er å forstå algoritmene i pensum, og å være i stand til å konstruere dine egne. Det er ikke like viktig å kunne gjengi dem ved hjelp av kode eller pseudokode i en eksamenssetting. Vi tillater stort sett at du beskriver algoritmer med det du måtte ønske av kode, pseudokode, formler, tekst eller figurer, så lenge det kommer klart frem hva du har ment.

Må jeg bruke matematisk notasjon på eksamen?

Nei. Hvis du har problemer med å få satt inn matematisk notasjon, kan du også bruke tekstlige beskrivelser som Theta(n) o.l.

Hvor langt bør jeg svare? Gir løsningsforslagene fullgode svar?

Ofte vil et kort svar være bedre enn et langt. Se gjerne gamle løsningsforslag for eksempler på hvor kort et fullgodt svar ofte kan være. Det er meningen at om man har svart det som står i løsningsforslaget, så skal man få full score. (Man kan naturligvis også få full score om man svarer noe annet.)

Er det lurt å skrive om ting som ikke er helt relevante?

Dersom du har flaks, og det viser seg at det likevel var relevant, så kanskje. Men normalt sett, nei. Irrelevante deler av svaret vil vanligvis ignoreres, men kan også trekke ned, spesielt om de inneholder noe som er galt.

Hvordan blir formatet på årets eksamen?

Det bruker vi vanligvis si ganske lite om i forkant. Gamle eksamensoppgaver gir et bilde av hvordan eksamen typisk har vært så langt, og kan nok gi en viss pekepinn, men når det gjelder nøyaktig antall oppgaver, typer oppgaver (som f.eks. multiple choice eller ikke), vekting e.l., så vil dere trolig ikke få opplyst det før eksamen.

Kan jeg legge ved håndtegninger på eksamen?

Dette vil det være opplyst om i eksamenssettet, men det er vanligvis ikke mulig.

Årets eksamen var helt annerledes enn tidligere!

Dette er en reaksjon vi typisk får fra noen av studentene nesten hvert år. Det kan delvis være fordi eksamen ikke følger en fast formel, men i hovedsak skyldes det nok at det å øve seg på gamle eksamensoppgaver i ro og mak, med lite press, god tid og tilgang til løsningsforslag, er noe helt annet enn å bli konfrontert med en oppgave du ikke har løsningen på, og som du må løse på begrenset tid under eksamen. Vi baserer eksamen først og fremst på læringsmålene i faget, så det er disse du bør fokusere på, heller enn gamle eksamener.

Må jeg pugge pseudokoden til alle algoritmene?

Tanken er at dere skal forstå algoritmene, hvordan de oppfører seg, trinn for trinn, og hvorfor de gir riktig svar. Om dere har forstått det, vil dere trolig kunne gjenkjenne fragmenter av pseudokoden med andre variabelnavn, eller kunne sette inn biter som mangler o.l., som har vært brukt som eksamensoppgaver, uten å måtte pugge all pseudokoden i detalj.

Må jeg kunne kjøretidene til alle algoritmene?

Ja, dette er et av de generelle læringsmålene som gjelder alle algoritmene i pensum. Men tanken er at dere skal forstå hvordan algoritmen oppfører seg, trinn for trinn, og hvordan kjøretiden er regnet ut ut fra dette. Om dere forstår det, så bør det ikke være stort ytterligere behov for pugging av kjøretider.

Annet

Kan jeg blæste i forelesningene?

Dette finner du mer informasjon om på siden om blæsting.

Hva heter … på norsk?

Vi har en egen side om temaet.

Nedenfor følger lengre forklaringer motivert av spørsmål som har blitt stilt, selv om de ikke nødvendigvis stilles så ofte. De legges her, siden de kan være nyttige for andre enn spørsmålsstilleren. Flere av spørsmålene kommer fra poster på vår tidligere forumløsning. Du finner flere slike forklaringer i vårt nåværende forum.

Asymptotisk notasjon

• Aritmetikk med asymptotisk notasjon

  Aritmetiske uttrykk med asymptotisk notasjon kan være enkle, når alle leddene bruker samme operator, som f.eks.: $O(n) + O(n^2) = O(n + n^2) = O(n^2)$ Men hva skjer når man blander forskjellige operatorer?

• Asymptotisk notasjon og beste/verste tilfelle

  Jeg er litt forvirret. Jeg trodde \(\Theta\) var worst-case kjøretid, men boken bruker plutselig \(O\). I tillegg bruker den \(\Theta\) for average kjøretid. Var ikke \(O\) gjennomsnittlig kjøretid? Og \(\Theta\) worst-case? I tillegg sier boken at noe krever minne \(\Theta(n)\); hvorfor bruker de \(\Theta\) for minne også?

• Asymptotisk notasjon: lg eller log?

  I læreboka brukes $\lg n$ som forkortelse på $\log_2 n$, mens $\log n$ ikke har noe spesifisert grunntall. Grunntallet utgjør bare en konstantfaktor, så hvorfor ikke bare bruke $\log n$ i asymptotisk notasjon? Grunnen til at vi i øvinger og lysark o.l. gjerne bruker $\lg n$ er at det er dette læreboka gjør, ganske konsekvent.

• Kjøretid med flere parametre

  Når vi diskuterer kjøretid, har vi vanligvis én parameter – problemstørrelsen. Men enkelte ganger, som for grafalgoritmer, så har vi plutselig to parametre. Hvordan skal vi egentlig tolke det?

• Kjøretid som funksjon av hva?

  Vi oppgir vanligvis kjøretid som en funksjon av en «inputstørrelse». For å sitere læreboka (i delkapittel 2.2, Analyzing algorithms):

• Likhet og asymptotisk notasjon

  Er det riktig å skrive $f(n)=O(n^2)$? Er ikke $O(n^2)$ en mengde? Burde det ikke være $f\in O(n^2)$?

Dynamisk programmering

• Delproblemer eller delinstanser?

  Hvorfor står «delinstans» oppført i ordlista som oversettelse av «subproblem»?

• LCS

  Jeg sliter litt med LCS. Jobber en seg bakover eller framover? Ut ifra notatene fra forelesningen forstod jeg det slik at vi sammenligner de to siste elementene. Om de er ulike, kutter vi av en av dem fra en av sekvensene, og sammenligner så på nytt (og gjentar inntil vi finner to like). Men når vi da har funnet to like, går vi til de nest siste elementene i begge sekvensene?

  Og hva er kjøretiden? \(O(m + n)\) (hvor \(m\) og \(n\) er antallet elementer i de to sekvensene, eller \(O(mn)\)?

Eksamensoppgaver

• Eksamen 2012, oppg. o

  Oppgave o i eksamen 2012 ber deg dele en heltallstabell \(A\) i (sammenhengende, ikke-tomme, ikke-overlappende) segmenter, så hvert segment summerer til et av tallene i en annen heltallstabell \(B\). Løsningsforslaget gir en forklaring (i tillegg til pseudokode), men den er kanskje litt knapp for enkelte.

• Eksamen 2014, oppg. 2e

  I løsningsforslaget står det at man skal redusere fra $B$ til $A$. Hvorfor blir det ikke omvendt? Om man vet at $B$ har polynomisk kjøretid og så reduserer fra $A$ til $B$ i polynomisk tid, vet man ikke da at $A$ også har polynomisk kjøretid?

• Eksamen 2017, oppg. 2c

  Her ble man bedt om å løse rekurrensen \(T(n)=T(n/3)+\lg n\) og svare med \(\Theta\)-notasjon. Den kan lett løses med masterteoremet slik det er i pensum nå, men ikke slik det var den gang! Om man brukte det mer begrensede masterteoremet på rett måte, fikk man nesten full uttelling, men svaret blir like fullt ikke rett. Hvorfor ikke, og hvordan skulle man ha løst oppgaven?

• Kapasitets- og flytøkning

  Oppgave 10 i kont 2015 sier: Hvis vi øker kapasiteten til hver enkelt kant i et flytnettverk med \(k\), vil verdien til den maksimale flyten alltid øke med et multiplum av \(k\)? Begrunn svaret kort.

  Hva kan være et eksempel på at dette ikke vil gå?

• Kont 2007, oppg. 3b

  Jeg har tenkt at vi har et flytnettverk med kanter mellom du to noder i hver sin gruppe dersom de misliker hverandre. Jeg skjønner hvordan jeg finner maksimalflyt, men ikke hvordan dette forteller meg hvilke noder (om dette er mennesker) jeg kan eller ikke kan ta med meg i ostesmaksgruppen?

• Kont 2013, oppg. 13

  Skjønner ikke hvordan man klarer å se at $F(n) = T(n) - T(n-1) = 2^{n-1}$.

• Kont 2014, oppg. 10

  I LF til oppgave 10 står det «Sett inn hver ridder på første lovlige plass, etter tur», hvor første lovlige plass er at du setter den over en du har slått.

  Dette vil først gi (1) sort, (2) rød, fordi sort slo rød. Men når grønn da skal settes inn vil da den første lovlige plassen være øverst fordi grønn slo sort, så listen blir (1) grønn, (2) sort (3) rød. Hvordan kan dette være en lovlig ranking? Rød har jo slått grønn?

• Kont 2014, oppg. 9

  «Din venn Lurvik har funnet opp en algoritme. Algoritmen hans kan ta inn en sekvens av lengde \(n\), der \(n\) er et multiplum av \(k\), og sortere den i \(k\) segmenter av lik lengde, slik at elementene i et gitt segment ikke nødvendigvis er sortert seg imellom, men alle elementer i ethvert segment er større enn eller like store som elementene i alle segmenter til venstre, og mindre eller like elementene i alle segmenter til høyre. Gi en nedre grense for kjøretiden til algoritmen. Forklar kort.»

  Er det mulig å få en mer detaljert forklaring (enn LF) på hvordan man finner kjøretiden her?

• Kont 2015, oppg. 15

  To ord er anagrammer av hverandre dersom de består av de samme tegnene, men i forskjellig rekkefølge. Hvert tegn må forekomme like mange ganger, og vi regner et ord som et anagram av seg selv. Anta at du har oppgitt en tekst, og et start-ord A og et slutt-ord B. Du ønsker å konstruere en sekvens med ord som starter med A og som slutter med B, med følgende krav: Hvis to ord X og Y står ved siden av hverandre i denne sekvensen, skal et anagram for X være brukt i samme setning som et anagram for Y. Beskriv svært kort en algoritme som avgjør om en slik sekvens eksisterer.

• Kont 2017, oppg. 3

  Burde ikke det siste elementet være 7 i oppgave 3, her? Mulig jeg har misforstått noe, men jeg skjønner ikke hvor den siste toeren kommer fra.

Grafer

• Grafisomorfi

  Satt og tenkte litt på problemet med å sjekke at to grafer er isomorfe. La oss bare anta at de har lik lengde og slikt, sånn at man ikke jobber med slike special cases. Ideelt så burde man sortere nodene i riktig rekkefølge i forhold til hverandre også bare sjekke om kantstrukturen er identisk (eller om nabomatrisene deres er identiske), men akkurat denne sorteringen av noder virker ikke helt triviell eller polynomisk for meg. Har noen et hint eller et innspill?

Grådighet

• Huffman-kode for ett tegn

  Hva er høyden på huffmantrær med ett tegn, si a – blir det 0, med a som øverste node, eller vil man ha en node med a som barn og høyde 1?

Korteste vei

• Bellman–Ford og V–1

  Hvorfor er det nok å relaxe alle kanter \(V\mkern-2mu-1\) ganger hver for å oppnå korteste vei i Bellman-Ford?

• DAG-SP og DP

  Er det noen som har mulighet til å forklare litt utdypende om hvorfor det er en kobling mellom DAG-SP og dynamisk programmering?

• Hvorfor er korteste vei uten sykler NP-hardt?

  I oppgave e fra høsteksamen 2012 står det: «I læreboka … argumenteres det for at det er meningsløst å tillate negative sykler i korteste veier. Hvis vi begrenser oss til å kun lete etter korteste veier uten sykler (såkalte simple paths), hvorfor er det likevel problematisk om grafen vår inneholder negative sykler (som kan nås fra startnoden)?»

• Kjøretid, Johnson

  Jeg lurer på om kjøretiden for Johnson når man bruker en binærhaug er \(O(V^2\lg V + VE\lg V)\). Eller er det \(O(VE\lg V)\) og i så fall hvorfor kan man fjerne det første leddet?

Maksflyt

• Baklengs flyt i 1. og 2. utgave

  I tidligere utgaver av læreboka tillot de antiparallelle kanter (dvs., både \((u,v)\in E\) og \((v,u)\in E\)), men i de nyeste utgavene tillater de ikke dette (for å gjøre enkelte ting enklere). Det har også noe å si for definisjonen av flyt!

• Hvorfor har Edmonds–Karp kjøretid O(VE²)?

  Ford-Fulkerson har kjøretid $O(E|f^*|)$, der $|f^*|$ er maks flyt. Dette fordi man potensielt kan øke flyten $E$ ganger. Samme logikk for Edmonds-Karp. Potensielt kan flyten øke $E$ ganger, men hvorfor $O(VE^2)$? Om den bruker BFS, så har vel den kjøretid $O(V+E)$, som totalt gir $O(VE+E^2)$?

Minimale spenntrær

• Bokas versjon av Prim

  I boka sin implementasjon av MST-Prim legges ingen elementer til i mengden $A$, så jeg skjønner ikke hvordan spenntreet blir returnert. Er det siden MST-Prim hele tiden vedlikeholder ett enkelt tre? Hvorfor kan man ikke bare ha et enkele if-utsagn der $A = A \cup \{(u,u.p)\}$ hvis $\textit{parent}\neq\,$nil etter Dequeue fra $Q$?

• Hauger i Prims algoritme

  Når man implementerer Prims algoritme kan det være lurt å hente ut den billigste kanten fra alle nodene du har tilgjengelig. Dette har jeg løst ved å legge alle kantene til alle tilgjengelige noder i en heap, og vil da hente ut den billigste kanten fra heapen hver gang. Men, hvordan kan jeg holde kontroll på hvor den kanten kommer fra når heapen automatisk sorterer alle kantene?

• Hvorfor Prim fremfor Kruskal?

  I en tett (dense) graf, altså en graf med veldig mange kanter, vil man i Dijkstra gå over til en enklere datastruktur, og bruke en usortert liste som prioritetskø. Men for minimale spenntrær vil man da gjerne foretrekke Prim, som bruker vanskeligere datastrukturer enn Kruskal. Hvorfor?

NPC

• Faktorisering og NPC

  Om man sjekker en løsning i polynomisk tid, f.eks tre-farging av en graf, men det viser seg at løsningen ikke er entydig etter å sjekke alle mulige løsninger (eksponentiell kjøretid), putter man dette bare i NP da?

  Og er det riktig å konkludere med at RSA-problemet er i NP? Å faktorisere har slik jeg forstår det polynomisk kjøretid, og for å sjekke om kvotienten videre er et primtall ble bevist i 2002 har polynomisk kjøretid (PRIMES). Det siste er vel kanskje overflødig da RSA mer eller mindre antar kun to distinkte faktorer.

• Hva er egentlig verifikasjon?

  Intuitivt virker det jo enkelt å si at en verifikasjonsalgoritme «sjekker svaret», og at vi kan verifisere løsningene til problemer i NP. Men om man ser litt mer formelt på det, ser det plutselig litt snodigere ut. Hvordan fungerer egentlig verifikasjon?

• Hvorfor redusere fra A til B?

  Hvis man skal sammenligne hvor vanskelige to problemer A og B er, hvorfor vil man redusere fra A til B? Problemstillingen dukker opp i ulike forkledninger i flere eksamensoppgaver,¹ og viser seg å være vanskelig for mange å få helt grepet på.

  1. For eksempel ↩

• P, NP, NPC, NPH og reduksjoner

  Dette er det tydeligvis flere som har problemer med, så jeg tenkte jeg skulle prøve meg på en ny oppsummering/felles forklaring.

• Reduksjoner, ordning og kompletthet

  Det kan være mye å ta inn over seg når man skal forstå det konseptuelle maskineriet rundt NP-kompletthet. For enkelte kan det kanskje være nyttig å se på ideen om kompletthet isolert, separat fra begreper som reduksjoner eller polynomisk kjøretid. Én måte å gjøre det på er å se på relasjonen «kan reduseres til», som er en såkalt preordning – en generalisering av både delvise ordninger og ekvivalensrelasjoner. Hva NP-kompletthet er, og hvorfor P = NP dersom det finnes en reduksjon fra NPC til P, er ting det fint går an å forstå kun ved å se på denne preordningen.

Rekurrenser

• Masterteorem-oppgave

  Jeg prøver å løse rekurrensen $T(n) = 16T(n/4) + n!$ med masterteoremet. Dette gir jo $a = 16$, $b = 4$ og $\log_b(a) = 2$. Men når $f(n)=n!$, hvordan kan jeg finne ut om det er av tilfelle 1, 2 eller 3? Dersom det hadde stått f.eks. $n^2$, så har vi $c = 2$ og det ville vært tilfelle 2. Hva gjør jeg når det er fakultet involvert i $f(n)$?