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

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 på sal – 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 et arkiv av øvingene i INGInious, som er tilgengelig som et eget «fag». Her vil alle øvingene bli tilgjengeliggjort etter fristen har gått ut, med ubegrenset antall forsøk på både teori og praksis. 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.

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/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 tillager 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. Ofte vil et kort svar være bedre enn et langt, i slike sammenhenger. Se gjerne gamle løsningsforslag for eksempler på hvor kort et fullgodt svar ofte kan være.

Årets eksamen var helt annerledes enn tidligere!

Dette er en reaksjon vi typisk får fra noen av studentene nesten hvert år. Det skyldes nok delvis at 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.

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.

Lengre forklaringer

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

  • 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?

  • 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?

  • Hvordan lage arrays i Julia

    Hvordan lager man tabeller (arrays) i Julia? Den enkleste måten å gjøre det på er rett og slett å liste opp innholdet, akkurat som f.eks. i Python, det vil si [1, 2, 3]. For å lage en tom tabell, bruker man []. Men hva om du vil lage en tabell av en bestemt størrelse? Det er flere muligheter her, men du trenger trolig bare funksjonene beskrevet nedenfor.1

    1. For en litt grundigere oversikt, se avsnittet Construction and Initialization i dokumentasionen. 

  • Hvordan memoiserer jeg i Julia?

    Den enkleste implementasjonen av dynamisk programmering er kanskje memoisering. Om du klarer å lage en rekursiv løsning for problemet ditt, vil memoisering ofte gi deg en effektiv algoritme. Det kan enten være en fullgod løsning i seg selv, eller første skritt i retning av en bottom-up-løsning. Men hvordan kan man implementere memoisering i Julia?

  • 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$?

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

  • Eksamen 2017, oppg. 2c

    Her ble man bedt om å løse rekurrensen og svare med -notasjon. Det ligner jo forlokkende på den typen rekurrenser vi kan løse med masterteoremet – men dessverre passer den ikke helt! Om man brukte masterteoremet på rett måte, fikk man nesten full uttelling, men svaret blir like fullt ikke rett. Hvorfor ikke, og hvordan skal man løse oppgaven?

  • Kjøretid, Johnson

    Jeg lurer på om kjøretiden for Johnson når man bruker en binærhaug er . Eller er det og i så fall hvorfor kan man fjerne det første leddet?

  • Eksamen 2012, oppg. o

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

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

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

  • 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)$?
  • 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 , der er et multiplum av , og sortere den i 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?

  • Kapasitets- og flytøkning

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

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

  • 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? (hvor og er antallet elementer i de to sekvensene, eller ?

  • Baklengs flyt i 1. og 2. utgave

    I forrige utgave av læreboka tillot de antiparallelle kanter (dvs., både og ), men i den nyeste utgaven tillater de ikke dette (for å gjøre enkelte ting enklere). Det har også noe å si for definisjonen av flyt!

  • Variabelskifte

    Jeg sliter litt med er variabelskifte. For eksempel, rekurensen . Jeg begynner med å skifte ut . Da får man . Deretter leste jeg at man bør bytte ut . Dermed får man . Dette steget forstår jeg ikke, hvordan får man ved å bytte ut ?

  • 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?

  • Bellman–Ford og V–1

    Hvorfor er det nok å relaxe alle kanter ganger hver for å oppnå korteste vei i Bellman-Ford?

  • 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?

  • Asymptotisk notasjon og beste/verste tilfelle

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

  • 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?

  • 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?

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

  • Løkker i globalt skop i Julia

    I versjon 1.0 av Julia er det en særegenhet som man lett kan bli litt forvirret av, om man prøver å bruke løkker i det globale navnerommet (altså ikke inne i en funksjon). Følgende tilsynelatende opplagt korrekte kode fungerer nemlig ikke:

  • 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 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?