•BFS (uvektet): O(|V| + |E|) -- korteste sti i antall kanter
•Dijkstra krever: ikke-negative kantvekter
•Reverser-triks: reverser kanter, kjor Dijkstra fra mal
Minimum spenntraer
•Prim: O((|V| + |E|) * log(|V|)) med binaer heap
•
Vanlige feil å unngå
Grafalgoritmer
•Glemme a markere noder som besokt i BFS/DFS, noe som gir uendelig lokke 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 a skille mellom back-edges og cross-edges.
Korteste vei-algoritmer
•Bruke Dijkstra pa grafer med negative vekter -- Dijkstra gir feil svar nar vekter er negative. Bruk Bellman-Ford.
•Glemme a sjekke om en dequeue-t node allerede har fatt kortere avstand (foreldet oppforing i prioritetskoen).
•Kjore Dijkstra fra alle mulige startnoder i stedet for a reversere grafen og kjore en gang fra malet.
•Forveksle Dijkstra-kjoretid: O((|V|+|E|) log |V|) med heap, IKKE O(|V|^2) (det er uten heap).
Minimum spenntraer
•Bruke MST-algoritmer pa 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.
•
Eksamenstips
Grafalgoritmer
•Nar oppgaven sier 'forst naermeste, deretter lenger ut' eller 'nivavis', er det BFS som gjelder (H2024: venner innen k ledd; invitasjoner i rekkefølge).
•Nar oppgaven spor 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).
•Nar oppgaven ber om a finne 'rundturer', 'sykler' eller om en rettet graf er sterkt sammenhengende: bruk sterkt sammenhengende komponenter (SCC), O(|V|+|E|). Returner komponentene med storrelse > 1.
•Vanlig modelleringsoppgave: 'er denne grafen et tre?' -- tell besokte noder i en BFS/DFS og sjekk om du moter en allerede besokt node (sykel).
•Oppgi alltid kjoretidskompleksiteten nar du bruker en grafalgoritme -- det gir ekstra poeng.
Korteste vei-algoritmer
•Nar oppgaven sier 'positive vekter' eller 'tidsbruk som positivt heltall', bruk Dijkstra.
•Nar du skal finne korteste vei til en node (ikke fra en node), reverser grafen forst.
•Oppgi alltid hvilken datastruktur prioritetskoen bruker -- det pavirker kjoretiden.
Minimum spenntraer
•Nar oppgaven sier 'koble sammen alle med lavest kostnad', tenk MST (H2023: Blindern-problemet).
•Eksamen spor ofte om Prims kjoretid -- husk O((|V|+|E|) log |V|) med heap.
•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
Forveksle Prim og Dijkstra -- begge bruker prioritetsko, men Prim sammenligner kantvekt, Dijkstra sammenligner total avstand.
•Glemme a nevne Union-Find nar du beskriver Kruskal.
Traer og binaere soketraer
•Tro at BST-egenskapen bare gjelder direkte barn -- den gjelder ALLE noder i venstre/hoyre undertre.
•Glemme at diameteren ikke nodvendigvis gar gjennom roten -- den kan ligge helt i et undertre.
•Forveksle hoyde og dybde: hoyde er avstand ned til dypeste lov, dybde er avstand opp til roten.
•Ikke handtere null-pekere i rekursive tre-algoritmer -- basistilfellet er alltid v == null.
Heaper og prioritetskoer
•Tro at en heap er sortert -- en heap garanterer bare at forelder <= barn (min-heap), ikke at venstre < hoyre.
•Forveksle heapify O(n) med n enkeltvise innsettinger O(n log n).
•Tro at man kan finne storste element i en min-heap i O(1) -- storste element kan vaere pa ethvert lovniva, sa det tar O(n).
•Glemme a balansere de to heapene i en medianko.
Hashing og hashtabeller
•Glemme a bruke modulo nar du gar forbi slutten av arrayet i linear probing.
•Tro at O(1)-oppslag er garantert -- det er bare forventet tid. Verste tilfelle er O(n).
•Glemme rehashing nar lastfaktoren blir for hoy -- det forer til darlig ytelse.
•Forveksle innsetting og oppslag i linear probing: innsetting stopper ved tom plass, oppslag stopper ved tom plass ELLER nar nokkelen 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 gjore 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 kjoretid nar du analyserer en ukjent algoritme -- vis tydelig verste og beste tilfelle.
Graadige algoritmer og Huffman-koding
•Tro at Huffman-treet er unikt -- det kan finnes flere gyldige Huffman-traer 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 a 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 sma n kan konstantfaktorer dominere.
•Forveksle O-notasjon (ovre grense) med eksakt kjoretid -- O(n^2) betyr 'maksimalt proporsjonalt med n^2', ikke noyaktig n^2.
•Glemme a inkludere |E| i kjoretiden 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 pa eksamen.
Beregnbarhet og NP-kompletthet
•Tro at P = NP eller P != NP er bevist -- begge er fortsatt apne sporsmal.
•Reduksjon i feil retning: for a 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 star for nondeterministic polynomial, og P er en delmengde av NP.
•Blande sammen uavgjorbarhet (umulig uansett) med NP-kompletthet (mulig, men antatt tregt).
•Etter MST er bygget, er korteste sti i treet unik og finnes med BFS/DFS i O(|V|).
Traer og binaere soketraer
•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 soketree-egenskapen).
•Nar du skriver trealgoritmer, returner alltid to verdier (f.eks. diameter OG hoyde) for a unnga dobbelt arbeid.
Heaper og prioritetskoer
•H2023 ba eksplisitt om heap-innsetting med pseudokode. Vis hele arrayet etter alle innsettinger.
•H2022 hadde 10 sant/usant-paastander om heaper -- ov pa alle typiske misforstaelser.
•Nar Dijkstra nevnes, oppgi at prioritetskoen er en binaer heap for a fa korrekt kjoretid.
Hashing og hashtabeller
•H2022 ba om a fylle ut en hashtabell med linear probing og skrive pseudokode. Vis hvert steg!
•H2024 testet forstaelse av Pythons nye ordbok-struktur. Forklar oppslag og innsetting med naturlig sprak.
•Husk at rehashing krever at ALLE elementer settes inn pa nytt -- du kan ikke bare kopiere arrayet.
Sorteringsalgoritmer
•H2024: 'stabilt sortere uten a kalle sorteringsalgoritmer' = implementer counting sort manuelt.
•H2023: ukjent algoritme presenteres og du ma analysere den. Identifiser likheter med kjente algoritmer.
•Nar oppgaven spor om 'det er umulig a sortere i O(n)', menes sammenligningsbasert -- svaret er sant for sammenligningsbasert, usant generelt.
Graadige algoritmer og Huffman-koding
•H2024 testet Huffman direkte. Tegn treet steg for steg og oppgi kodelengder.
•Nar oppgaven sier 'komprimering' eller 'variabel lengde-koding', tenk Huffman.
•Husk a beskrive at lovnodene inneholder symbolene -- det ble eksplisitt spurt om i H2024.
Kompleksitetsanalyse
•H2022 hadde en hel oppgave med kjoretider for grafalgoritmer. Lag en tabell og memorer den.
•Nar du skriver pseudokode, oppgi alltid kjoretiden -- det gir ekstra poeng og viser forstaelse.
•Les noye om det sporres om 'verste tilfelle' eller 'forventet' -- svaret kan vaere forskjellig (f.eks. quicksort).
Beregnbarhet og NP-kompletthet
•Sant/usant om P/NP gar igjen (H2019, H2021). Memorer de faste fellene: ingenting om P vs NP er bevist, men P er delmengde av NP.
•Nar du blir bedt om a vise at et problem er i NP: beskriv en polynomisk verifikator som tar et sertifikat (H2020: array av noder for hamiltonsk sykel).
•Nar du skal vise NP-kompletthet, reduser et KJENT NP-komplett problem TIL det nye problemet -- og husk a begrunne retningen.