Komplett pensumoversikt for algoritmer og datastrukturer ved UiO — med forklaringer, sentrale begreper, eksamenstips og vanlige fallgruver. Eksamensoptimalisert basert på tidligere eksamener.
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.
Graftraversering med BFS og DFS, topologisk sortering, sterkt sammenhengende komponenter og syklusdeteksjon. Grunnlaget for nesten alle grafoppgaver på eksamen.
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 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 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|).
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|).
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.
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).
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.
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 resultProcedure 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)Nøkkelformler
Vanlige feil
Eksamenstips
Laster...