IN2010 · UiO

Studieguide for IN2010 Algoritmer og datastrukturer

Komplett pensumoversikt for algoritmer og datastrukturer ved UiO — med forklaringer, sentrale begreper, eksamenstips og vanlige fallgruver. Eksamensoptimalisert basert på tidligere eksamener.

Introduksjon

IN2010 Algoritmer og datastrukturer har én skriftlig eksamen i desember: 4 timer i Inspera, uten hjelpemidler. Neste eksamen er 11. desember 2026 kl. 09.00. Guiden er bygd på de 8 IN2010-settene H2018–H2025 og sensorveiledningene til dem. Alle tall under er målt deloppgave for deloppgave. Prosentene er andel av de publiserte poengene i snitt over settene: sant/usant-delen i H2023–H2025 er ikke publisert og kan ikke fordeles på tema.

Hva eksamen faktisk tester

Fire temaer er med i alle 8 settene: grafalgoritmer (20,5 % av de publiserte poengene i snitt), sortering og binærsøk (13,0 %), binære søketrær (11,2 %) og hashing (9,7 %). Heaper og korteste vei er med i 7 av 8. Så følger sammenheng i grafer (SCC og separasjonsnoder), minimale spenntrær og Huffman-koding i 5 av 8, NP og AVL/rød-svart i 4 av 8. Hashing står i oppgaveteksten i 7 av 8 sett og er verktøyet i sensorens løsning i det åttende. Kjøretid er ikke et eget felt på eksamen. Du må oppgi den etter nesten hver algoritme du skriver.

Dynamisk programmering, nettverksflyt, strengmatching, union-find og Floyd–Warshall har 0 treff i alle 16 IN2010-filene (oppgavesett og sensorveiledninger). De er ikke med i guiden.

Slik er settet bygd (H2023–H2025)

Oppvarming, 2 p: forklar kort hva en algoritme og en datastruktur er. Alle rimelige svar gir full uttelling.
Del 1, 22–32 sant/usant: automatisk rettet og skalert med $2\cdot\max(n - N/2,\,0)$ , der $n$ er antall riktige av $N$ . Svarer du tilfeldig, blir snittet 0.
Del 2, 6–7 oppgaver à 10–15 p: skriv prosedyrer i pseudokode, kjør algoritmer for hånd, velg en kjent algoritme og oppgi kjøretid. Pseudokode var 44,7 % av de publiserte poengene i H2022–H2025.

Slik bruker du guiden

Hver seksjon starter med «Slik testes dette på eksamen» og har gjennomregnede eksempler i eksamensform. Alle tall i eksemplene er kontrollregnet med et program. Grafseksjonene øver også på det som skiller de nyeste settene fra de eldre: en lang historie der hver deloppgave skal kobles til riktig algoritme.

Grafalgoritmer

Eksamensrelevant

Grafalgoritmer er med i 8 av 8 IN2010-sett og er det største temaet (20,5 % av de publiserte poengene i snitt): modeller historien som graf, og løs den med BFS, DFS, komponenter, syklusdeteksjon eller (modifisert) topologisk sortering i lineær tid.

Oversikt

En graf $G = (V, E)$ har noder og kanter. Den kan være rettet eller urettet, vektet eller uvektet. Nesten alle grafoppgaver i IN2010 er en «historie» der du selv må se hvilken kjent algoritme som løser den: BFS, DFS, komponenter, syklusdeteksjon eller topologisk sortering.

Slik testes dette på eksamen. Grafalgoritmer er med i 8 av 8 IN2010-sett (H2018–H2025) og er det største temaet: 20,5 % av de publiserte poengene i snitt, 22,1 % i de fire nyeste. Traversering og sammenheng står i 7 av 8 sett med 54 poeng til sammen, der svaret er pseudokode (Java i H2018). Modellering som graf (hva er noder og kanter, rettet eller urettet) kom i 4 av 8 sett. Syklusdeteksjon kom i H2023 og H2025 (16 p), modifisert topologisk sortering i H2018 og H2021 (24 p), avkrysning av grafegenskaper i H2020 og H2022 (19 p) og komponenter i H2021 og H2022 (13 p).

Representasjon og modellering

Naboliste: for hver node en liste over naboene. Plass $O(|V| + |E|)$ , og å gå gjennom alle naboer tar tid proporsjonal med graden. Standardvalget.
Nabomatrise: $|V| \times |V|$ -tabell. Oppslag «finnes kanten $(u, v)$ ?» i $O(1)$ , men plass $O(|V|^2)$ , og en traversering blir $O(|V|^2)$ .
Når en historie skal gjøres om til en graf, svar på tre ting: hva nodene er, hva en kant betyr, og om grafen er rettet (relasjonen går én vei: «bruker», «lenker til», «krever») og vektet (kostnad, tid, avstand).
Urettet betyr at man alltid kan gå samme kant tilbake. Sammenhengende betyr at det finnes en sti mellom hvert par av noder.

Traversering

BFS bruker en kø og besøker nodene lag for lag. I en uvektet graf gir den korteste avstand (antall kanter). Brukes når noe skal skje «først venner, så venners venner» (H2024 4c).
DFS bruker rekursjon eller en stakk og går så dypt som mulig før den snur. Grunnlaget for syklussjekk, komponenter og SCC.
Begge er $O(|V| + |E|)$ når alle noder besøkes (DFSFull). Fra én startnode besøkes bare det som kan nås.
Til dybde $k$ : BFS stopper å legge naboer i køen når avstanden er $k$ . H2024 4b trakk 3 poeng om $k$ ble ignorert.
Komponenter: kjør DFS fra hver ubesøkte node; hvert kall gir én komponent. Summer eller sjekk noe per komponent (H2021 12). Det som ikke nås fra en mengde startnoder, finnes ved DFS fra alle startnodene og så en gjennomgang av $V$ (H2022 8).
2-fargelegging: BFS eller DFS som gir naboen motsatt farge. Møter du en nabo med samme farge, er det umulig. Det skjer nøyaktig når grafen har en sykel av odde lengde.

Eksempel 1: BFS og DFS for hånd

En urettet graf har kantene A–B, A–C, B–D, C–D, C–E, D–F, E–F, F–G og G–H. Naboene besøkes i alfabetisk rekkefølge. Kjør BFS og DFS fra A, og finn hvem som ligger innen $k = 2$ ledd fra A.

Urettet graf med åtte noder A til H og kantene A–B, A–C, B–D, C–D, C–E, D–F, E–F, F–G og G–H. Nodene står i lag fra venstre mot høyre etter BFS-avstand fra A, med d = avstand under hver node: A (0), B og C (1), D og E (2), F (3), G (4) og H (5). B, C, D og E er uthevet som nodene innen to ledd fra A.

Tatt ut av køen	Nye noder (avstand)	Kø etterpå
A	B = 1, C = 1	B, C
B	D = 2	C, D
C	E = 2	D, E
D	F = 3	E, F
E	–	F
F	G = 4	G
G	H = 5	H

BFS setter avstanden idet noden legges i køen. D oppdages fra B, så C finner ingen ny vei til D.
DFS fra A går til B, så til D (Bs eneste ubesøkte nabo), så til C (Ds første ubesøkte nabo), E, F, G og H.
Innen 2 ledd er nodene med BFS-avstand 1 eller 2.

Svar: BFS: A, B, C, D, E, F, G, H. DFS: A, B, D, C, E, F, G, H. Innen 2 ledd: B, C, D og E.

Sykler

Urettet: DFS som møter en allerede besøkt node som ikke er forelderen, har funnet en sykel. Uten foreldresjekken svarer algoritmen «sykel» på enhver kant (H2025 3a: −2 p). Alternativ: grafen er syklusfri hvis og bare hvis $|E| = |V| - c$ , der $c$ er antall komponenter.
Rettet: kjør topologisk sortering. Blir færre enn $|V|$ noder behandlet, finnes en sykel. Alternativ: DFS med tre farger (ubesøkt, under behandling, ferdig); en kant til en node under behandling er en sykel. Å sjekke om noden ligger på stakken med lineært søk gir $O(|V|(|V|+|E|))$ og maks 3 poeng (H2023 7a).

Eksempel 2: Har en urettet graf en sykel?

Skriv en prosedyre som avgjør om en urettet graf $G = (V, E)$ har en sykel, og oppgi kjøretiden.

Procedure HarSykel(G)
  besøkt ← tom mengde
  for s in V do
    if s ∉ besøkt then
      if DFSSykel(G, s, null, besøkt) then
        return true
  return false

Procedure DFSSykel(G, u, p, besøkt)
  legg u til besøkt
  for (u, v) in E do
    if v = p then
      continue            // kanten vi kom fra
    if v ∈ besøkt then
      return true
    if DFSSykel(G, v, u, besøkt) then
      return true
  return false

Den ytre løkken starter et nytt søk i hver komponent, så en sykel i en komponent som ikke henger sammen med den første, blir også funnet.
I Eksempel 1-grafen går DFS A, B, D, C og ser fra C naboen A, som er besøkt og ikke forelder (forelderen er D). Sykelen A–B–D–C–A er funnet.
Kontroll med tellingen: grafen har $|E| = 9$ og $|V| - c = 8 - 1 = 7$ , altså sykler.
Testet (kjørt): 20 000 tilfeldige grafer, prosedyren og kriteriet $|E| = |V| - c$ ga samme svar hver gang.
Hver node legges til besøkt én gang, og hver kant ses høyst to ganger.

Svar: HarSykel over, med kjøretid $O(|V| + |E|)$ .

Topologisk sortering

En topologisk ordning av en DAG lister $u$ før $v$ for hver kant $(u, v)$ . Kahns algoritme: legg alle noder med inngrad 0 i en beholder, ta ut én om gangen, skriv den ut og senk inngraden til naboene; den som når 0, legges inn. Kjøretid $O(|V| + |E|)$ . Beholderen kan være stakk, kø eller heap. Med en min-heap ordnet etter en nøkkel (tidsstempel, navn) får du den ordningen som tar minste nøkkel først uten å bryte kantene, i $O((|V| + |E|) \log |V|)$ . Det var løsningen i H2021 13.

Eksempel 3: Er den topologiske rekkefølgen entydig?

En rettet graf har nodene P, Q, R, S, T og U og kantene P→Q, P→R, Q→S, R→S, S→T, T→U og R→U. (a) Gi en algoritme i lineær tid som avgjør om grafen har nøyaktig én topologisk rekkefølge. (b) Kjør den på grafen. (c) Hvilken ene kant kan legges til slik at rekkefølgen blir entydig?

Rettet graf med seks noder P, Q, R, S, T og U. Pilene er P til Q, P til R, Q til S, R til S, S til T, T til U og R til U. Ved hver node står startinngraden: P 0, Q 1, R 1, S 2, T 1, U 2. En stiplet pil fra Q til R viser kanten som legges til i deloppgave c.

Procedure EntydigTopologisk(G)
  for v in V do
    inn[v] ← inngraden til v
  Q ← kø med alle v der inn[v] = 0
  entydig ← true
  antall ← 0
  while Q ikke er tom do
    if |Q| > 1 then
      entydig ← false
    u ← dequeue(Q)
    antall ← antall + 1
    for (u, v) in E do
      inn[v] ← inn[v] − 1
      if inn[v] = 0 then
        enqueue(Q, v)
  if antall < |V| then
    return "sykel: ingen topologisk rekkefølge"
  return entydig

Uttak	Køen før uttaket	Merknad
1	P	én kandidat
2	Q, R	to kandidater: ikke entydig
3	R
4	S
5	T
6	U

Dette er Kahns algoritme med én ekstra test. Ligger to noder i køen samtidig, har ingen av dem en sti til den andre. Da kan de tas i begge rekkefølger, og det finnes minst to topologiske rekkefølger.
Har køen alltid høyst én node, er hvert valg tvunget, og rekkefølgen er entydig. Det er det samme som at hvert par av naboer i rekkefølgen har en kant mellom seg.
Kjøring: etter P faller både Q og R til inngrad 0. Algoritmen returnerer false. Kontroll (kjørt): grafen har nøyaktig 2 topologiske rekkefølger, P, Q, R, S, T, U og P, R, Q, S, T, U.
For c) må Q og R bindes sammen. Med Q→R (stiplet) har R inngrad 2 og kommer først inn i køen etter Q. Kontroll (kjørt): av alle mulige enkeltkanter er det bare Q→R og R→Q som gir én rekkefølge.
Kjøretid: hver node settes inn og tas ut én gang, og hver kant senker én inngrad én gang. Testen $|Q| > 1$ er $O(1)$ .

Svar: Rekkefølgen er ikke entydig (Q og R kan byttes). Kanten Q→R (eller R→Q) gjør den entydig. Kjøretid $O(|V| + |E|)$ .

Grafegenskaper (avkrysning)

Tre: urettet, sammenhengende og uten sykler, altså $|E| = |V| - 1$ . Fjern én kant: ikke sammenhengende. Legg til én kant: én sykel.
DAG: rettet uten sykler. Å gjøre en graf til DAG krever å fjerne kanter, aldri å legge til.
Enkel graf: ingen løkker og ingen parallelle kanter. En enkel urettet graf kan ha $|V|(|V|-1)/2$ kanter, så « $n$ noder gir høyst $n$ kanter» er usant (H2022 2j).

Nøkkelformler

•BFS og DFS over hele grafen: $O(|V| + |E|)$
•Naboliste: plass $O(|V| + |E|)$ ; nabomatrise: $O(|V|^2)$
•Urettet graf uten sykler $\iff |E| = |V| - c$ ( $c$ = antall komponenter)
•Tre: sammenhengende og $|E| = |V| - 1$
•Topologisk sortering (Kahn): $O(|V| + |E|)$ ; med heap på en nøkkel: $O((|V| + |E|) \log |V|)$

Vanlige feil

⚠️Å glemme foreldresjekken i syklussøk i urettet graf, slik at hver kant gir «sykel». H2025 3a trakk 2 poeng.
⚠️Å kjøre et nytt søk fra hver node når ett søk (eller DFSFull) holder. H2023 7a og H2025 3a ga maks 3 poeng for $O(|V|(|V|+|E|))$ , og H2022 8 trakk 2 poeng over $O(|V|+|E|)$ .
⚠️Å ignorere grensen $k$ i en «innen $k$ ledd»-oppgave. H2024 4b trakk 3 poeng.
⚠️Å bruke vanlig topologisk sortering når oppgaven krever en ekstra orden (tidsstempel, semester). H2021 13 ga maks 5 poeng uten modifikasjonen, H2018 12 maks 9 av 14.
⚠️Å bare starte søket i én node når grafen kan ha flere komponenter.

Eksamenstips

💡Start grafoppgaver med å si hva nodene og kantene er, og om grafen er rettet og vektet.
💡Skriv hvilken kjent algoritme du bruker og hva den returnerer, så modifikasjonen. Sensor gir poeng for idéen først.
💡«Lag for lag», «først venner, så venners venner»: BFS. «Kan nås fra», «komponent», «sykel»: DFS.
💡Rettet sykel: tell behandlede noder i Kahns algoritme og sammenlign med $|V|$ .
💡Oppgi kjøretiden i $|V|$ og $|E|$ , ikke i en udefinert $n$ .

Laster...

Laster…