•NP: ja-instans kan VERIFISERES i polynomtid med sertifikat
•P er delmengde av NP (P subset NP)
•NP-komplett: i NP OG alle NP-problemer reduseres til det
•Vis B NP-komplett: reduser kjent A til B (A <=p B)
•NP-komplette fra pensum: Hamilton, TSP, vertex cover, subset sum, clique
Vanlige feil å unngå
Grafalgoritmer
•Glemme å markere noder som besøkt i BFS/DFS, noe som gir uendelig løkke i grafer med sykler.
•Forveksle BFS og DFS: BFS bruker ko og finner korteste sti i uvektede grafer, DFS bruker stakk og er grunnlag for syklusdeteksjon.
•Tro at topologisk sortering finnes for alle grafer -- den finnes kun for rettede asykliske grafer (DAG-er).
•Bruke DFS uten farger (kun visited-mengde) for syklusdeteksjon i rettede grafer -- du trenger tre tilstander for å skille mellom back-edges og cross-edges.
Korteste vei-algoritmer
•Bruke Dijkstra på grafer med negative vekter -- Dijkstra gir feil svar når vekter er negative. Bruk Bellman-Ford.
•Glemme å sjekke om en dequeue-t node allerede har fått kortere avstand (foreldet oppføring i prioritetskøn).
•Kjøre Dijkstra fra alle mulige startnoder i stedet for å reversere grafen og kjøre en gang fra målet.
•Forveksle Dijkstra-kjøretid: O((|V|+|E|) log |V|) med heap, IKKE O(|V|^2) (det er uten heap).
Minimum spenntrær
•Bruke MST-algoritmer på rettede grafer -- Prim og Kruskal er for urettede grafer.
•Glemme at MST ikke gir korteste sti mellom to noder -- MST minimerer total kantvekt, ikke enkeltavstander.
•Forveksle Prim og Dijkstra -- begge bruker prioritetskø, men Prim sammenligner kantvekt, Dijkstra sammenligner total avstand.
•Glemme å nevne Union-Find når du beskriver Kruskal.
Trær og binære søketrær
•Tro at BST-egenskapen bare gjelder direkte barn -- den gjelder ALLE noder i venstre/høyre undertre.
•Glemme at diameteren ikke nødvendigvis går gjennom roten -- den kan ligge helt i et undertre.
•Forveksle høyde og dybde: høyde er avstand ned til dypeste lov, dybde er avstand opp til roten.
•Ikke håndtere null-pekere i rekursive tre-algoritmer -- basistilfellet er alltid v == null.
Heaper og prioritetskør
•Tro at en heap er sortert -- en heap garanterer bare at forelder <= barn (min-heap), ikke at venstre < høyre.
•Forveksle heapify O(n) med n enkeltvise innsettinger O(n log n).
•Tro at man kan finne største element i en min-heap i O(1) -- største element kan være på ethvert lovniva, sa det tar O(n).
•Glemme å balansere de to heapene i en medianko.
Hashing og hashtabeller
•Glemme å bruke modulo når du går forbi slutten av arrayet i lineær probing.
•Tro at O(1)-oppslag er garantert -- det er bare forventet tid. Verste tilfelle er O(n).
•Glemme rehashing når lastfaktoren blir for høy -- det fører til dårlig ytelse.
•Forveksle innsetting og oppslag i lineær probing: innsetting stopper ved tom plass, oppslag stopper ved tom plass ELLER når nøkkelen er funnet.
Sorteringsalgoritmer
•Tro at O(n log n) er den absolutte nedre grensen for sortering -- den gjelder kun sammenligningsbasert sortering. Counting/radix sort kan gjøre O(n).
•Forveksle stabil og in-place. Stabil = like elementer beholder rekkefølge. In-place = O(1) ekstra minne.
•Glemme at counting sort krever at verdiomradet k er begrenset -- ellers er O(n+k) ikke bedre enn O(n log n).
•Ikke begrunne kjøretid når du analyserer en ukjent algoritme -- vis tydelig verste og beste tilfelle.
Grådige algoritmer og Huffman-koding
•Tro at Huffman-treet er unikt -- det kan finnes flere gyldige Huffman-trær med samme optimale kodelengder.
•Forveksle kodelengde med frekvens -- kodelengden er dybden i treet, ikke frekvensen.
•Glemme at Huffman-koding er en prefikskode -- det er hele poenget med å bruke et tre.
•Bygge treet ovenfra og ned i stedet for nedenfra og opp -- Huffman bygger alltid fra lovene.
Kompleksitetsanalyse
•Tro at O(n) alltid er raskere enn O(n log n) for alle n -- for små n kan konstantfaktorer dominere.
•Forveksle O-notasjon (øvre grense) med eksakt kjøretid -- O(n^2) betyr 'maksimalt proporsjonalt med n^2', ikke nøyaktig n^2.
•Glemme å inkludere |E| i kjøretiden for grafalgoritmer -- BFS er O(|V|+|E|), ikke bare O(|V|).
•Tro at 'best case' er relevant for O-notasjon -- O-notasjon brukes typisk for verste tilfelle på eksamen.
Beregnbarhet og NP-kompletthet
•Tro at P = NP eller P != NP er bevist -- begge er fortsatt åpne spørsmål.
•Reduksjon i feil retning: for å vise at B er NP-komplett reduserer du kjent A TIL B, ikke B til A.
•Forveksle a LOSE (P) med a VERIFISERE (NP) -- NP handler om verifisering av et gitt sertifikat.
•Tro at NP betyr 'ikke-polynomisk' -- NP står for nondeterministic polynomial, og P er en delmengde av NP.
•Blande sammen uavgjorbarhet (umulig uansett) med NP-kompletthet (mulig, men antatt tregt).
Eksamenstips
Grafalgoritmer
•Når oppgaven sier 'først nærmeste, deretter lenger ut' eller 'nivavis', er det BFS som gjelder (H2024: venner innen k ledd; invitasjoner i rekkefølge).
•Når oppgaven spør om sykliske avhengigheter eller om en graf er en DAG, bruk DFS med tre farger ELLER topologisk sortering (Kahns algoritme oppdager sykler hvis ikke alle noder kan prosesseres).
•Når oppgaven ber om å finne 'rundturer', 'sykler' eller om en rettet graf er sterkt sammenhengende: bruk sterkt sammenhengende komponenter (SCC), O(|V|+|E|). Returner komponentene med størrelse > 1.
•Vanlig modelleringsoppgave: 'er denne grafen et tre?' -- tell besøkte noder i en BFS/DFS og sjekk om du møter en allerede besøkt node (sykel).
•Oppgi alltid kjøretidskompleksiteten når du bruker en grafalgoritme -- det gir ekstra poeng.
Korteste vei-algoritmer
•Når oppgaven sier 'positive vekter' eller 'tidsbruk som positivt heltall', bruk Dijkstra.
•Når du skal finne korteste vei til en node (ikke fra en node), reverser grafen først.
•Oppgi alltid hvilken datastruktur prioritetskøn bruker -- det påvirker kjøretiden.
Minimum spenntrær
•Når oppgaven sier 'koble sammen alle med lavest kostnad', tenk MST (H2023: Blindern-problemet).
•Eksamen spør ofte om Prims kjøretid -- husk O((|V|+|E|) log |V|) med heap.
•Etter MST er bygget, er korteste sti i treet unik og finnes med BFS/DFS i O(|V|).
Trær og binære søketrær
•AVL-rotasjoner ble testet i H2022. Ovelsesoppgave: sett inn tallene i rekkefølge og tegn treet etter hver innsetting.
•LCA er en gjenganger (H2024). Husk to varianter: generelt tre (bruk parent-peker) og BST (bruk søketre-egenskapen).
•Når du skriver trealgoritmer, returner alltid to verdier (f.eks. diameter OG høyde) for å unngå dobbelt arbeid.
Heaper og prioritetskør
•H2023 ba eksplisitt om heap-innsetting med pseudokode. Vis hele arrayet etter alle innsettinger.
•H2022 hadde 10 sant/usant-påstander om heaper -- ov på alle typiske misforstælser.
•Når Dijkstra nevnes, oppgi at prioritetskøn er en binær heap for å få korrekt kjøretid.
Hashing og hashtabeller
•H2022 ba om å fylle ut en hashtabell med lineær probing og skrive pseudokode. Vis hvert steg!
•H2024 testet forståelse av Pythons nye ordbok-struktur. Forklar oppslag og innsetting med naturlig språk.
•Husk at rehashing krever at ALLE elementer settes inn på nytt -- du kan ikke bare kopiere arrayet.
Sorteringsalgoritmer
•H2024: 'stabilt sortere uten å kalle sorteringsalgoritmer' = implementer counting sort manuelt.
•H2023: ukjent algoritme presenteres og du må analysere den. Identifiser likheter med kjente algoritmer.
•Når oppgaven spør om 'det er umulig å sortere i O(n)', menes sammenligningsbasert -- svaret er sant for sammenligningsbasert, usant generelt.
Grådige algoritmer og Huffman-koding
•H2024 testet Huffman direkte. Tegn treet steg for steg og oppgi kodelengder.
•Når oppgaven sier 'komprimering' eller 'variabel lengde-koding', tenk Huffman.
•Husk å beskrive at lovnodene inneholder symbolene -- det ble eksplisitt spurt om i H2024.
Kompleksitetsanalyse
•H2022 hadde en hel oppgave med kjøretider for grafalgoritmer. Lag en tabell og memorer den.
•Når du skriver pseudokode, oppgi alltid kjøretiden -- det gir ekstra poeng og viser forståelse.
•Les nøye om det sporres om 'verste tilfelle' eller 'forventet' -- svaret kan være forskjellig (f.eks. quicksort).
Beregnbarhet og NP-kompletthet
•Sant/usant om P/NP går igjen (H2019, H2021). Memorer de faste fellene: ingenting om P vs NP er bevist, men P er delmengde av NP.
•Når du blir bedt om å vise at et problem er i NP: beskriv en polynomisk verifikator som tar et sertifikat (H2020: array av noder for hamiltonsk sykel).
•Når du skal vise NP-kompletthet, reduser et KJENT NP-komplett problem TIL det nye problemet -- og husk å begrunne retningen.