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 er et kjerneemne ved Institutt for informatikk, UiO. Kurset dekker avanserte algoritmer og datastrukturer som bygger videre på IN1000/IN1010: grafalgoritmer, trestrukturer, hashing, sortering, grådige algoritmer, og kompleksitetsanalyse. Eksamen er en 4-timers skriftlig prove uten hjelpemidler, der du skriver pseudokode og resonnerer.

Eksamen følger et fast mønster med tre deler: (1) en kort oppvarming (2 poeng) der du forklarer hva en algoritme og en datastruktur er, (2) en flervalg/sant-usant-del med små oppgaver som rettes automatisk (ca. 22-32 poeng), og (3) større oppgaver der du skriver pseudokode og argumenterer for korrekthet og kjøretid (ca. 40-60 poeng). Totalt ca. 66-100 poeng.

Viktig om sant/usant-delen: poengene skaleres for gjetning. Hvis du svarer riktig på n av N påstander, får du typisk 2*max(n - N/2, 0) poeng. Gjetter du tilfeldig på alt, får du i snitt null poeng; svarer du riktig på alt, får du full uttelling. Du bør likevel svare på alt -- det er ingen ekstra straff for feil utover gjettekorreksjonen, og alt du faktisk vet teller positivt.

Viktige tips: Les oppgaveteksten svært nøye. Alle implementasjonsoppgaver skal besvares med pseudokode som er lett forstælig, entydig og presis -- en klar forklaring med naturlig språk kan gi like mye uttelling som tvetydig pseudokode. Lavere kjøretidskompleksitet gir mer poeng. Du kan anta at algoritmer og datastrukturer fra pensum er tilgjengelig, med mindre noe annet er spesifisert. Et gjennomgænde mønster er at oppgavene er innpakkede historier (DNT-rundtur, Blindern-tunneler, dependency hell, Whops!-oppgjor) der den egentlige jobben er å kjenne igjen hvilken pensumalgoritme som løser problemet.

Grafalgoritmer

Eksamensrelevant

Graftraversering med BFS og DFS, topologisk sortering, sterkt sammenhengende komponenter og syklusdeteksjon. Grunnlaget for nesten alle grafoppgaver på eksamen.

Oversikt

En graf G = (V, E) består av en mengde noder V og en mengde kanter E. Grafen kan være rettet (kanter har retning) eller urettet (kanter går begge veier). Grafer kan representeres som nabolister (et array av lister, en per node) eller som en nabomatrise (en V x V matrise). Nabolister er mest minneeffektivt for sparse grafer (få kanter), mens nabomatriser gir O(1)-oppslag for å sjekke om en kant finnes.

BFS (bredde-først-søk)

BFS utforsker grafen nivavis: først alle nabør på avstand 1, deretter avstand 2, osv. Algoritmen bruker en ko (FIFO) og en mengde med besøktenoder. BFS finner korteste sti i uvektede grafer (antall kanter). Kjøretid: O(|V| + |E|). På eksamen (H2024) ble BFS brukt til å finne venner innen k ledd -- en typisk anvendelse der du begrenser BFS til en gitt dybde.

DFS (dybde-først-søk)

DFS utforsker grafen ved å ga sa dypt som mulig for den snur. Algoritmen bruker en stakk (eksplisitt eller via rekursjon) og en mengde besøktenoder. DFS er grunnlaget for mange grafalgoritmer: syklusdeteksjon, topologisk sortering, og sterkt sammenhengende komponenter. Kjøretid: O(|V| + |E|).

Topologisk sortering

En topologisk sortering av en rettet asyklisk graf (DAG) er en lineær ordning av nodene slik at for hver kant (u, v) kommer u for v. Algoritmen bruker DFS eller en ko-basert tilnærming (Kahns algoritme). Topologisk sortering finnes kun for DAG-er. På eksamen (H2022) ble det spurt om kjøretiden til TopSort -- den er O(|V| + |E|).

Syklusdeteksjon

For å oppdage sykler i en rettet graf bruker vi DFS med tre farger: hvit (ubesøkt), gra (pabesøkt, på rekursjonsstakken), svært (ferdig). Hvis vi under DFS treffer en gra node, har vi funnet en sykel. På H2023 (Dependency hell) ble det eksplisitt bedt om å sjekke om en avhengighetsgraf inneholder sykliske avhengigheter.

Sterkt sammenhengende komponenter (SCC)

I en rettet graf er en sterkt sammenhengende komponent en maksimal mengde noder der det finnes en rettet sti begge veier mellom ethvert par. SCC finnes i O(|V| + |E|) med to DFS-gjennomloop (Kosarajus algoritme: DFS for å få ferdig-rekkefølge, reverser grafen, DFS i synkende ferdig-rekkefølge) eller med Tarjans algoritme. Dette er et yndlingsverktoy på eksamen for å finne rundturer/sykler: alle komponenter med mer enn en node utgjor en sykel. En graf der hver node inngår i hoyst en sykel kan håndteres ved å kjøre SCC og returnere alle komponenter av størrelse > 1. SCC brukes også til å sjekke om en rettet graf er sterkt sammenhengende (da er det nøyaktig en komponent som inneholder alle noder).

Grafegenskaper

Du bør kjenne til sentrale begreper: grad (antall kanter til en node), inngrad/utgrad (i rettede grafer), sammenhengende (det finnes sti mellom alle par av noder), sterkt sammenhengende (rettet sti begge veier), DAG (rettet asyklisk graf), tre (sammenhengende asyklisk graf), 2-fargbar/bipartitt (nodene kan deles i to mengder uten kant innad), isomorfi (to grafer har samme struktur). Et tilbakevendende spørsmål er om en graf er et tre: en sammenhengende urettet graf med n noder er et tre hvis og bare hvis den har nøyaktig n-1 kanter og er asyklisk -- dette kan sjekkes med en enkelt BFS/DFS som teller besøkte noder og oppdager kanter tilbake til allerede besøkte noder.

Eksempel 1: BFS med dybdegrense (H2024-stil)

Procedure BFS_k(G, s, k):
  queue = ny ko
  visited = ny mengde
  queue.enqueue((s, 0))
  visited.add(s)
  result = []
  while queue er ikke tom:
    (v, depth) = queue.dequeue()
    if depth > k: break
    result.append(v)
    for each nabo u av v i G:
      if u ikke i visited:
        visited.add(u)
        queue.enqueue((u, depth + 1))
  return result

Eksempel 2: Syklusdeteksjon med DFS (H2023-stil)

Procedure HasCycle(G):
  color = ny ordbok (alle noder -> WHITE)
  for each node v i G:
    if color[v] == WHITE:
      if DFS_Visit(G, v, color):
        return true
  return false

Procedure DFS_Visit(G, v, color):
  color[v] = GRAY
  for each nabo u av v:
    if color[u] == GRAY:
      return true  // Sykel funnet!
    if color[u] == WHITE:
      if DFS_Visit(G, u, color):
        return true
  color[v] = BLACK
  return false

Eksempel 3: Finn alle rundturer med SCC (rettet graf)

// Finn alle sykler/rundturer i en rettet graf:
// en rundtur er en sterkt sammenhengende komponent
// med mer enn en node.
Procedure FinnRundturer(G):
  komponenter = SterktSammenhengendeKomponenter(G)
  rundturer = ny mengde
  for each komp i komponenter:
    if |komp| > 1:
      rundturer.add(komp)
  return rundturer
// Kjoretid: O(|V| + |E|) -- SCC dominerer
// (Kosaraju: to DFS-pass + en grafreversering)

Nøkkelformler

•BFS kjøretid: O(|V| + |E|) -- bruker kø (FIFO)
•DFS kjøretid: O(|V| + |E|) -- bruker stakk/rekursjon
•TopSort kjøretid: O(|V| + |E|) -- kun for DAG-er
•SCC (Kosaraju/Tarjan): O(|V| + |E|) -- finner sykler/rundturer
•Tre-sjekk: sammenhengende + n-1 kanter + asyklisk
•Naboliste: O(|V| + |E|) plass, O(grad(v)) for å finne naboer
•Nabomatrise: O(|V|^2) plass, O(1) for å sjekke kant

Vanlige feil

⚠️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.

Eksamenstips

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

Laster...

Laster…

Introduksjon

Procedure BFS_k(G, s, k): queue = ny ko visited = ny mengde queue.enqueue((s, 0)) visited.add(s) result = [] while queue er ikke tom: (v, depth) = queue.dequeue() if depth > k: break result.append(v) for each nabo u av v i G: if u ikke i visited: visited.add(u) queue.enqueue((u, depth + 1)) return result

Procedure HasCycle(G): color = ny ordbok (alle noder -> WHITE) for each node v i G: if color[v] == WHITE: if DFS_Visit(G, v, color): return true return false Procedure DFS_Visit(G, v, color): color[v] = GRAY for each nabo u av v: if color[u] == GRAY: return true // Sykel funnet! if color[u] == WHITE: if DFS_Visit(G, u, color): return true color[v] = BLACK return false

// Finn alle sykler/rundturer i en rettet graf: // en rundtur er en sterkt sammenhengende komponent // med mer enn en node. Procedure FinnRundturer(G): komponenter = SterktSammenhengendeKomponenter(G) rundturer = ny mengde for each komp i komponenter: if |komp| > 1: rundturer.add(komp) return rundturer // Kjoretid: O(|V| + |E|) -- SCC dominerer // (Kosaraju: to DFS-pass + en grafreversering)