IN2010

Cheat Sheet

Formler, begreper og oppsummering

Algoritmer og datastrukturer

eksamenssett.no

Formler

Grafalgoritmer

•BFS: O(|V| + |E|), bruker ko, finner korteste sti i uvektede grafer
•DFS: O(|V| + |E|), bruker stakk/rekursjon, syklusdeteksjon
•Topologisk sortering: O(|V| + |E|), kun for DAG-er
•Dijkstra: O((|V|+|E|) log |V|) med heap, positive vekter
•Bellman-Ford: O(|V| * |E|), handterer negative vekter
•Prim: O((|V|+|E|) log |V|) med heap, MST
•Kruskal: O(|E| log |E|) med sortering + Union-Find, MST

Traer

•BST sok/innsetting: O(h), O(log n) for balansert
•AVL: hoydeforskjell <= 1, rotasjoner ved ubalanse
•Inorder-traversering av BST: sortert rekkefølge, O(n)
•LCA i BST: O(h) -- folg BST-egenskapen nedover
•Diameter: O(n) med kombinert hoyde/diameter-rekursjon

Heaper og prioritetskoer

•Insert: O(log n) -- bubble up
•RemoveMin/Max: O(log n) -- bubble down

Nøkkelformler per tema

Grafalgoritmer

•BFS kjoretid: O(|V| + |E|) -- bruker ko (FIFO)
•DFS kjoretid: O(|V| + |E|) -- bruker stakk/rekursjon
•TopSort kjoretid: O(|V| + |E|) -- kun for DAG-er
•Naboliste: O(|V| + |E|) plass, O(grad(v)) for a finne naboer
•Nabomatrise: O(|V|^2) plass, O(1) for a sjekke kant

Korteste vei-algoritmer

•Dijkstra: O((|V| + |E|) * log(|V|)) med binaer heap
•Bellman-Ford: O(|V| * |E|) -- handterer negative vekter
•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
•Kruskal: O(|E| * log(|E|)) med sortering + Union-Find
•MST har noyaktig |V| - 1 kanter
•

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).
•Nar oppgaven spor om sykliske avhengigheter eller om en graf er en DAG, bruk DFS med tre farger.
•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.
•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.
•

•Heapify: O(n) -- bygg heap fra array

•Array: barn = 2i+1, 2i+2; forelder = (i-1)/2

•Bucket queue: Insert O(1), RemoveMin O(N)

Hashing

•Hashfunksjon: h(k, N) = k mod N
•Linear probing: (h(k,N) + i) mod N
•Forventet oppslag/innsetting: O(1)
•Rehashing: O(n), nar lastfaktor blir for hoy

Sortering

•Mergesort: O(n log n), stabil, O(n) ekstra plass
•Quicksort: O(n log n) forventet, O(n^2) verste, in-place
•Heapsort: O(n log n), in-place, ikke stabil
•Counting sort: O(n + k), stabil
•Nedre grense (sammenligning): Omega(n log n)

Huffman-koding

•Bygg tre: O(n log n) med prioritetsko
•Slaa sammen de to laveste frekvensene i hvert steg
•Kodelengde = dybde av lovnode
•Prefikskode: ingen kode er prefiks av en annen

Cut-egenskap: billigste kant over et kutt er i MST

•Union-Find: O(alpha(n)) per operasjon (nesten O(1))

Traer og binaere soketraer

•BST-egenskap: venstre < rot < hoyre for alle noder
•BST sok/innsetting: O(h), der h er hoyden
•AVL: hoydeforskjell <= 1, rotasjoner for a balansere
•Balansert tre hoyde: O(log n)
•LCA i BST: O(h) -- gar nedover til x og y splitter

Heaper og prioritetskoer

•Heap innsetting: O(log n) -- bubble up
•Heap fjerning av min/maks: O(log n) -- bubble down
•Heapify (bygg heap fra array): O(n)
•Array-indeksering: barn = 2i+1, 2i+2; forelder = (i-1)/2

Hashing og hashtabeller

•Hashfunksjon: h(k, N) = k mod N (typisk eksempel)
•Linear probing: (h(k,N) + i) mod N for i = 0, 1, 2, ...
•Forventet oppslag: O(1) med god hashfunksjon og lav lastfaktor
•Rehashing: O(n) -- utvid tabell og sett inn alt pa nytt
•Lastfaktor alpha = n/N -- hold under ca. 0.75

Sorteringsalgoritmer

•Mergesort: O(n log n) alltid, stabil, ikke in-place
•Quicksort: O(n log n) forventet, O(n^2) verste, in-place, ikke stabil
•Heapsort: O(n log n) alltid, in-place, ikke stabil
•Counting sort: O(n + k), stabil, ikke in-place
•Nedre grense sammenligningssortering: Omega(n log n)

Graadige algoritmer og Huffman-koding

•Huffman: O(n log n) der n er antall symboler
•Hyppigere symbol = kortere kode = grunnere lovnode
•Huffman er graadig: slaa alltid sammen de to med lavest frekvens
•Lovnoder = symboler, interne noder = null-symbol

Kompleksitetsanalyse

•O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n)
•Nestet lokke: O(ytre * indre)
•Halvering i hvert steg: O(log n)
•Amortisert: gjennomsnittskostnad over mange operasjoner
•Grafalgoritmer: BFS/DFS/TopSort = O(|V|+|E|), Dijkstra/Prim = O((|V|+|E|)log|V|)

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.

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