0.1 Eksamenskartet — slik testes TDT4120

Eksamensformen (én firetimers hjelpemiddelfri kortsvarseksamen), temafrekvensene, sjangerkatalogen A–I og lesestrategien som styrer hele boka.

35 min

4 oppgaver

Eksamenskartetslik testes TDT4120

Din fremgang i kapitlet

0 / 4 oppgaver

Kapitlets plass i kurset

Brukes videre i

8.1Kortsvarssjangeren — å skrive presise, korte svar

Dette kapitlet er et kart, ikke pensum. Det viser deg hvordan TDT4120
faktisk testes, slik at du vet hva du skal bruke tiden på. Ingenting her krever
at du kan noe fra før.

Karakterskalaen er A–F, og hele karakteren settes av én skriftlig eksamen.
C er en god og helt vanlig karakter. Den som kan grunnoppgavene — riktige
tall på asymptotikk, riktig utført håndkjøring, standarddefinisjonene og riktig
retning på reduksjonsspørsmål — er trygt over bestått-terskelen. A skiller seg
ut på de åpne designoppgavene helt til slutt.

Eksamensformen i tre linjer:

- Fire timer, skriftlig, teller 100 % av karakteren.
- Rundt 20 korte frisvarsoppgaver som teller likt — ingen enkeltoppgave kan
redde eller ødelegge settet alene.
- Ingen hjelpemidler. Alt du skal bruke, må du ha i hodet.

Oppgavetypene har fått bokstaver A til I i denne boka, som en huskeliste:
A asymptotisk forenkling, B rekurrenser, C håndkjøring, D definisjoner,
E kjøretider, F «stemmer dette?», G reduksjoner og NP, H åpen
algoritmedesign og I essay (bare på korona-settene). Hver bokstav forklares på
nytt i klarspråk første gang den dukker opp i et kapittel, så du trenger ikke
lære dem utenat nå.

De vanligste feilene har fått numre #1 til #11. De er ikke skrivefeil, men
tankefeil som går igjen — for eksempel å tro at Build-Max-Heap bruker
$\Theta(n\lg n)$ tid når den bruker $\Theta(n)$ . Du finner hele registeret
lenger nede i kapitlet, og hver felle blir forklart der den kan ramme deg.

Om symbolene du møter senere: du trenger ikke forstå $T(n)=aT(n/b)+f(n)$ ,
$c_f(u,v)=c(u,v)-f(u,v)$ eller $A \le_p B$ ennå. De forklares der de brukes,
fra bunnen av. Det eneste symbolet det er verdt å ta med seg herfra, er
$\lg n$ , som i dette faget alltid betyr $\log_2 n$ — altså toerlogaritmen.

Hva dette kapitlet gir deg

TDT4120 har hatt en påfallende stabil eksamen i over et tiår. Det er en fordel
du kan utnytte: når mønsteret er stabilt, kan du forberede deg presist i stedet
for å lese alt like grundig.

Det er likevel én ting du ikke kan gjøre i dette faget, og som fungerer i
mange andre: du kan ikke droppe et tema og satse på at det ikke kommer.
Pensumbolkene er få og store, og de dukker opp igjen og igjen. Bredden er selve
eksamensformen. Denne boka er bygget for nettopp det — å dekke alt, men med
tyngden lagt der oppgavene faktisk kommer.

Nedenfor finner du eksamensformen, hvor ofte hvert tema har kommet, hvilke
oppgavetyper som finnes, hva løsningsforslagene premierer, og tre ferdige
leseplaner. Bruk 35 minutter her, så vet du hva de neste 60 timene skal gå
til.

Notasjons- og pseudokodeliste

Eksamensformen: fire timer, tjue oppgaver, ingen hjelpemidler

Vurderingen er én skriftlig skoleeksamen på fire timer som teller 100 % av
karakteren. Det er ingen midtsemesterprøve som teller inn.

Settet består av rundt 20 korte frisvarsoppgaver som teller likt — i
praksis 5 % hver. «Frisvar» betyr at du skriver svaret selv; det er ingen
avkryssing. «Kort» betyr virkelig kort: ett tall, ett uttrykk, én sluttilstand,
én setning.

Hjelpemiddelkode E er NTNUs kode for «ingen trykte eller håndskrevne
hjelpemidler, og ingen kalkulator». Den har stått på alle de sju settene fra
desember 2022 til desember 2025. Konsekvensen er enkel og ubehagelig: kjøretider,
definisjoner og pseudokode må sitte i hodet. Denne boka er bygget for det — hvert
kapittel ender i en begrepsbank som blir til flashcards, og quizen er ren
gjenkalling.

Oppgavene stiger løst i vanskelighet gjennom settet, og de siste tre til fem
er åpne designoppgaver: «hvordan vil du gå fram for å løse dette problemet?».
Det er der toppkarakteren avgjøres.

Tallene over er hentet fra NTNUs emneside og fra eksamenssettene selv. Sjekk
emnesiden for ditt eget semester — vurderingsordning og hjelpemidler kan
endres.

Hjelpemiddelkode E

NTNUs kode for eksamen uten hjelpemidler : ingen bok, ingen formelark, ingen kalkulator. Den har vært gjeldende for TDT4120 på alle sju settene fra desember 2022 til desember 2025. Praktisk betydning: alt du skal bruke må kunnes utenat — de fem asymptotiske symbolene, masterteoremets tre tilfeller, kjøretidene til pensumalgoritmene og kravene hver av dem stiller. «Det kan jeg slå opp» er ikke en holdning som overlever dette faget.

Kortsvarsoppgave

En oppgave som besvares med det etterspurte og ikke mer: ett tall, ett uttrykk, én sluttilstand eller én presis setning. Du skriver svaret selv — det er ikke avkryssing. Rundt 20 slike oppgaver utgjør hele eksamen, og de teller likt. Derfor er tid brukt på overflødig utledning i én oppgave tid tatt fra de nitten andre. I settene fra 2015 til 2018 sto det til og med svart på hvitt på oppgavearket: lange svar teller ikke positivt.

Korona-settene (hjelpemiddelkode A)

De fem terminene fra august 2020 til august 2022 var hjemmeeksamener med alle hjelpemidler tillatt (hjelpemiddelkode A), delvis med bestått/ikke bestått, og med færre og bredere essayoppgaver. De er ikke representative for dagens eksamen og skal ikke brukes som mal for verken form eller tempo. Essaysjangeren derfra er nyttig som treningsverktøy for å forklare hvorfor noe virker, men ingen bør regne med å møte den.

Hva som faktisk kommer — tema for tema

Tallene under er telt i 17 eksamenssett fra august 2015 til august 2023, som
er gjennomgått tema for tema. Det er nevneren hver gang du ser en prosent i
denne boka.

Tema	Frekvens	Hvor i boka
Asymptotisk notasjon og forenkling	100 % (17 av 17)	Del 1
Sortering	100 % (17 av 17)	Del 2
NP-kompletthet og reduksjoner	100 % (17 av 17)	Del 7
Binære søketrær og hauger	94 % (16 av 17)	Del 3
Maksimal flyt	94 % (16 av 17)	Del 5
Dynamisk programmering	94 % (16 av 17)	Del 6
Traversering (`BFS`/`DFS`)	82 % (14 av 17)	Del 4
Minimale spenntrær	82 % (14 av 17)	Del 4
Korteste vei fra én kilde	76 % (13 av 17)	Del 4
Rekurrenser	76 % (13 av 17)	Del 1
Splitt og hersk	71 % (12 av 17)	Del 1
Alle-til-alle korteste vei	65 % (11 av 17)	Del 4
Grådige algoritmer	65 % (11 av 17)	Del 6
Utvelgelse (`Select`)	47 % (8 av 17)	Del 2
Hashing	41 % (7 av 17), voksende	Del 3
Topologisk sortering	41 % (7 av 17)	Del 4
Køer og stakker	29 % (5 av 17)	Del 3
Amortisert analyse og disjunkte mengder	29 % (5 av 17)	Del 3
Stabil matching (`Gale-Shapley`)	12 % (2 av 17), voksende	Del 6

Les tabellen riktig. De seks øverste temaene har kommet på nesten hvert
eneste sett i grunnlaget. Det er ikke et tips om hva du bør prioritere — det er
en beskjed om at de kommer.
To rader fortjener et forbehold. Hashing står på 41 % samlet, men var med i
alle de tre settene fra 2022 og 2023. Stabil matching står på bare 2 av de
17 settene, men er verifisert til stede i 6 av de 7 settene med dagens
hjelpemiddelkode E (desember 2022 til august 2025), og manglet bare i desember
2025. Begge er på vei opp. Regn med at de kommer.
De fem nyeste settene i arkivet (desember 2023 til desember 2025) er lest for
form og eksamensordning, men ikke temaregistrert. De inngår altså ikke i
prosentene over.

📝Oppgave 1

(Innstegsoppgave.) Eksamen har rundt 20 oppgaver som teller likt, og varer i
fire timer.

a) Hvor mange minutter har du i snitt per oppgave?

b) Du står fast på én åpen designoppgave. Hvor lenge bør du maksimalt jobbe
med den før du går videre, og hvorfor?

c) Hva er den samlede verdien av de nitten andre oppgavene, målt mot den ene
du står fast på?

De ni oppgavetypene

Eksamen er frisvar, men oppgavene kommer i et lite antall gjenkjennelige
innpakninger. Denne boka gir dem bokstaver, slik at hvert kapittel kan si
presist hvilken type det trener. Bokstavene skrives alltid ut i klarspråk der de
brukes — du skal ikke pugge dem.

Kode	Oppgavetype	Hva svaret ditt skal være	Hvor ofte
A	asymptotisk forenkling og notasjon	ett strammeste uttrykk	100 % (17 av 17), ofte 2–3 oppgaver per sett
B	rekurrensløsning med navngitt metode	metodens navn + svaret på riktig form	76 % (13 av 17)
C	håndkjøring av en navngitt algoritme	kun sluttilstanden, i det formatet det spørres om	nær hvert sett; søketrær og hauger hyppigst
D	definisjon «med egne ord»	én presis setning, hovedpoenget først	flere per sett
E	kjøretidskunnskap og -sammenligning	uttrykket, med $\Theta$ eller $O$ bevisst valgt	innbakt i sortering (100 %) og korteste vei (76 %)
F	«stemmer dette?»	ja eller nei først, så én setning	41–76 % avhengig av tema
G	reduksjoner og NP-kompletthet	retningen + hva den beviser, og hva den ikke beviser	100 % (17 av 17)
H	åpen algoritmedesign	kort designskisse i fem faste ledd	hvert ordinært sett, de siste 3–5 oppgavene
I	nivådelt essay	lengre tekst	kun korona-settene — ikke representativt

De åtte første er de du skal trene. Sjanger I nevnes bare her, og bare fordi du
vil se den hvis du blar i settene fra 2020 til 2022.

Sjangerkortet — hele eksamen på én side

📝Oppgave 2

(Refleksjonsoppgave.) Se på frekvenstabellen over, og på prognosen for et
typisk sett.

a) Rangér disse fem temaene etter hvor mange oppgaver du forventer på neste
sett: alle-til-alle korteste vei, asymptotisk notasjon, stabil matching,
sortering, hashing.

b) Hvilke to av de fem ville du lest sist hvis du bare hadde tre dager
igjen?

Fem ting løsningsforslagene forteller oss

NTNU publiserer offisielle løsningsforslag til hver eneste eksamen i dette
faget. Det er uvanlig, og det er verdifullt: i stedet for å gjette på hva som
gir uttelling, kan vi lese det. Fem mønstre går igjen.

1. Presisjon slår lengde. I settene fra 2015 til 2018 sto det trykt på
oppgavearket at lange svar ikke teller positivt. Den formuleringen er borte fra
de nyere settene, men disiplinen står igjen — nå formulert i selve oppgavene:
«oppgi svaret i $\Theta$ -notasjon», «forklar kort», «du skal her kun svare med
utdataene fra algoritmen». Og fasitene svarer deretter. Ett av dem består i sin
helhet av uttrykket $\Theta(n)$ .

2. Svar bare på det du blir spurt om. «Oppgi utdataene» er ikke det samme
som «forklar algoritmen». «Oppgi hele tabellen» er ikke det samme som «oppgi den
logiske køen». Hver eneste løsning i denne boka markerer hva oppgaven faktisk
ber om når det er en felle der.

3. Delvis uttelling er regelen, ikke unntaket. Løsningsforslagene sier ting
som «her gis det 1 poeng» og «det gis uansett bare 4 av 5 poeng». En halvferdig
håndkjøringstabell er verdt langt mer enn en tom rute. Skriv hovedpoenget først
i definisjoner, så får du uttelling for det selv om resten halter.

4. Hver oppgave tester et navngitt læringsmål. Fra 2016 og framover oppgir
løsningsforslagene hvilket mål hver oppgave måler — «kunne løse rekurrenser med
masterteoremet», for eksempel. Et godt svar treffer nøyaktig den ferdigheten, og
ikke noe annet.

5. Fasiten er et eksempel, ikke en mal. Løsningsforslagene sier det selv:
svarene deres er eksempler på svar som gir uttelling, og mange beslektede svar
godtas — særlig på forklaringsoppgaver. Du trenger altså ikke treffe en bestemt
formulering. Du trenger å treffe poenget.

Arkivet inneholder oppgavesett og løsningsforslag — ikke noe eget dokument som
forklarer hvordan sensuren settes, og ingen offentlig karakterstatistikk. Alt
over kommer fra løsningsforslagene selv.

Delvis uttelling

At du får poeng for de riktige delene av et svar selv om helheten ikke er komplett. Løsningsforslagene i dette faget dokumenterer det flere ganger, med formuleringer som «her gis det 1 poeng» og «det gis uansett bare 4 av 5 poeng». To praktiske følger: en håndkjøringstabell med én feil rad er verdt mye mer enn en blank rute, og en definisjon bør åpne med hovedpoenget — det som gir mest uttelling — før betingelsene og nyansene.

Læringsmål (slik løsningsforslagene bruker begrepet)

Den ene ferdigheten en oppgave er laget for å måle. Fra 2016 og framover oppgir løsningsforslagene dette eksplisitt for hver oppgave, i formen «kunne løse rekurrenser med masterteoremet» eller «kunne definere restkapasitet». Det er en gave til den som forbereder seg: hvert svar bør treffe nøyaktig den ferdigheten oppgaven navngir, og ikke bruke plass på tilstøtende stoff. Denne bokas læringsmål er formulert i samme ånd.

Bredden som eksamensform

At faget ikke har én kjerneoppgave du kan satse på, men en kjernepensumliste der alle bolkene kommer igjen år etter år. I de 17 settene i grunnlaget har asymptotikk, sortering og NP-teori vært med i alle 17, og søketrær/hauger, maksimal flyt og dynamisk programmering i 16 av 17. Konsekvensen for lesingen er konkret: du kan ikke hoppe over en del og håpe. Du kan derimot lese en nivå 3-del kompakt.

Kortsvarssjangeren

Denne bokas navn på stilen eksamen krever: svar med det etterspurte — ett tall, ett uttrykk, én sluttilstand, én kort setning — uten overflødig utledning. Begrunnelsen er strukturell og gjelder uansett hvordan settet er formulert: 20 oppgaver teller likt på fire timer, så et halvsides resonnement på én oppgave er tid tatt fra nitten andre. Merk at dette gjelder svarene dine, ikke undervisningen: kapitlene i denne boka forklarer metodene fullt ut, fordi det er slik du lærer dem.

Typiske feil — de som koster mest på selve eksamensdagen

Dette er metafeilene: de som ikke handler om et enkelt tema, men om hvordan du
møter settet.

Å skrive langt. Et avsnitt med korrekt grunnidé slår ikke ett riktig
uttrykk. Det koster tid, og tid er den knappe ressursen når 20 oppgaver teller
likt.

Å satse på at et tema ikke kommer. Frekvenstabellen over gjør det umulig.
Seks temaer har vært med i 16 eller 17 av de 17 settene i grunnlaget.

Å øve på korona-settene som om de var vanlige. Settene fra august 2020 til
august 2022 var hjemmeeksamener med alle hjelpemidler og essayformat. De er ikke
representative for verken form eller tempo.

Å planlegge for å slå opp. Hjelpemiddelkode E betyr ingen hjelpemidler i det
hele tatt. Kjøretider og definisjoner må være pugget, ikke tilgjengelige.

Å la en rute stå tom. Delvis uttelling er dokumentert. Et halvferdig svar er
verdt noe; et blankt er verdt null.

Registeret over de elleve fellene

Disse elleve går igjen. De er nummerert én gang for hele boka, og hver av dem
blir forklart i klarspråk der den kan ramme deg — du trenger ikke huske numrene.

#	Fellen	Forklares i
#1	reversert reduksjonsretning: å redusere til et NP-komplett problem beviser ingenting om ditt eget problems vanskelighet	kap. 7.2, 7.4 og 8.2
#2	å blande søketre-egenskapen (venstre $\le$ rot $\le$ høyre) med haugegenskapen (forelder $\ge$ begge barn, ingen orden mellom søsken)	kap. 3.1, 3.2 og 3.3
#3	køfeil ved håndkjøring: bytte om `head` og `tail`, glemme at køen går rundt, eller oppgi bare den logiske køen i stedet for hele tabellen	kap. 3.5 og 3.3
#4	å oppgi en løs asymptotisk grense når en strammere finnes	kap. 1.1, kap. 1.2 og kap. 1.3
#5	feil masterteorem-tilfelle, særlig å glemme logaritmefaktoren	kap. 1.4 og kap. 1.6
#6	å påstå at det er gratis å rekonstruere selve løsningen fra en dynamisk programmering — det krever lagrede beslutninger, men øker ikke kjøretiden	kap. 6.1, 6.3 og 8.2
#7	å blande pseudopolynomisk og NP-hardt	kap. 5.2, 7.2 og 7.4
#8	å bruke `Dijkstra` på negative kantvekter	kap. 4.3 og 4.5
#9	feil kjøretidsfakta: `Build-Max-Heap` oppgitt som $\Theta(n\lg n)$ når den er $\Theta(n)$ , eller `Insertion-Sort` sitt beste tilfelle oppgitt som $\Omega(n\lg n)$ når det er $\Theta(n)$	kap. 2.1, kap. 3.1 og kap. 2.4
#10	å «reparere» en ugyldig struktur før du håndkjører på den — du skal utføre trinnene mekanisk	kap. 3.1 og 3.3
#11	å blande topologisk sortering med starttid — den bruker synkende ferdigtid	kap. 4.1 og 4.5

Fire av dem — #1, #2, #9 og #10 — er de løsningsforslagene fremhever oftest.

Hvordan et typisk sett ser ut

Ut fra de 17 settene i grunnlaget, og formen på de sju nyeste settene med
hjelpemiddelkode E, kan du regne med noe i nærheten av dette på rundt 20 likt
vektede oppgaver:

- 2–3 oppgaver på asymptotisk forenkling og notasjon (type A). De billigste
og sikreste poengene i hele settet.
- 1 rekurrens (type B), nesten alltid med krav om å navngi metoden.
- 2–3 kjøretidsspørsmål (type E), ofte om sortering.
- 1–2 håndkjøringer (type C): et binært søketre eller en haug, og gjerne én
graf- eller matrisealgoritme.
- 3–4 definisjoner (type D).
- 2–3 oppgaver om NP og reduksjoner (type G), der minst én handler om
retningen på reduksjonen.
- 3–5 åpne designoppgaver til slutt (type H), oftest med maksimal flyt eller
dynamisk programmering som verktøy, og muligens én om stabil matching.

Dette er en prognose bygget på mønsteret, ikke et løfte. Poenget er
proporsjonene: over halvparten av settet er korte, faktabaserte oppgaver du kan
gjøre nesten uten å tenke — hvis du har pugget. Resten avgjør toppen.

📝Oppgave 3

(Refleksjonsoppgave.) Du har lest prognosen over.

a) Anslå hvor mange av de rundt 20 oppgavene som kan besvares med ren
gjenkalling — altså et pugget faktum, uten regning eller design.

b) Hva sier svaret ditt om hvordan du bør bruke de siste tre dagene før
eksamen?

c) Hvorfor er det likevel ikke nok å pugge?

Det du må kunne utenat — og resten kan du utlede

Hele boka er anslått til 3 680 minutter, altså rundt 61 timer. Det tallet er
lesetid. Den som faktisk håndkjører algoritmene og skriver svarene selv, bør
legge på omtrent 50 % — og det er den som håndkjører som får uttelling.

Har du tre til fem dager igjen, ta dette, i rekkefølge:

1. Dette kapitlet (35 min) — så vet du hva du prioriterer bort.
2. Del 1, asymptotikk (kap. 1.1,
kap. 1.2 og drillen i
kap. 1.3, til sammen 175 min). Dette er 2–3 garanterte
oppgaver på hvert eneste sett, og det billigste stoffet i faget.
3. Del 2, sortering (kap. 2.1 og
kap. 2.2, 100 min) — kjøretidene og stabilitet. Alle
17 settene i grunnlaget har hatt sortering.
4. Reduksjonsretningen (kap. 7.2 og drillen i 7.4). NP-stoffet er på alle 17
settene, og retningen er det enkeltpunktet løsningsforslagene fremhever mest.
5. Håndkjøring av haug og binært søketre (kap. 3.3) — den sikreste
håndkjøringskandidaten, med 94 % (16 av de 17 settene).
6. Én øvingseksamen på tid (kap. 8.3), uten hjelpemidler.

Det er rundt 12 timer og dekker de tre 100 %-temaene pluss den sikreste
håndkjøringen. Alt annet er bonus i denne situasjonen.

Har du én dag igjen: flashcards og quiz fra Del 1, 2 og 7, pluss
oppslagskortet over. Ikke start på et nytt tema.

Ruten over et helt semester

Har du 10–12 uker og kan sette av 5–6 timer i uka, går hele boka inn med god
margin.

Uke	Innhold	Omtrent
1	Del 0 og Del 1 (asymptotikk) — de billige, garanterte poengene	6 t
2	Del 1 ferdig (rekurrenser) + prøvene til del 1	5 t
3	Del 2 (sortering og utvelgelse) + prøvene til del 2	6 t
4	Del 3 (hauger, søketrær, hashing)	5 t
5	Del 3 ferdig + prøvene til del 3. Håndkjør på papir.	5 t
6	Del 4 (grafalgoritmer)	6 t
7	Del 4 ferdig + prøvene til del 4	5 t
8	Del 5 (maksimal flyt) + prøvene til del 5	5 t
9	Del 6 (dynamisk programmering, grådighet, stabil matching)	6 t
10	Del 6 ferdig + prøvene til del 6	5 t
11	Del 7 (NP og reduksjoner) + prøvene til del 7	5 t
12	Del 8: kortsvarssjangeren, designdrillen, og de tre øvingseksamenene	8 t

Legg de tre øvingseksamenene på tre ulike helger, ikke i siste uke. Hver av
dem tar fire timer, og de er bygget for å tas på tid. Poenget med dem er ikke
bare å sjekke hva du kan — det er å øve på å fordele fire timer over 20
oppgaver.

Det er en helt legitim måte å bruke denne boka på, og den fungerer bedre i dette
faget enn i de fleste andre — fordi svarene er så korte at du kan formulere dem i
hodet.

Ruten er: les oppgaven, formuler svaret i én setning eller ett uttrykk i hodet, og
les så fasiten som om du var den som skulle rette den. Spør hvert eneste sted:
hva er det minste svaret som ville fått full uttelling her? Det trener nøyaktig
den disiplinen eksamen belønner.

Men to ting kan ikke leses. Håndkjør minst én haug og ett binært søketre på
papir, og gjennomfør minst én øvingseksamen på tid, uten hjelpemidler. Fire
timer med 20 oppgaver er også en tempoferdighet, og den finnes ikke i lesingen.

Hvor tallene i denne boka kommer fra

Prioriteringene i denne boka bygger på NTNUs eget eksamensarkiv for TDT4120.
NTNU publiserer offisielle løsningsforslag til hver eneste eksamen i dette
faget — arkivet vårt har 45 eksamensterminer fra desember 2003 til desember
2025, og alle 45 har fasit. Det er uvanlig godt, og det er grunnen til at vi kan
si noe presist om hva som faktisk gir uttelling i stedet for å gjette.

Frekvenstallene du møter i kapitlene («100 %», «94 %») er telt i de 17
settene fra august 2015 til august 2023 som er gjennomgått tema for tema — det
er nevneren hver gang. De fem nyeste settene, fra desember 2023 til desember
2025, er lest for form og eksamensordning, men ikke temaregistrert, så de inngår
ikke i prosentene.

Arkivet har ingen sensorveiledninger — det vi vet om hva som premieres,
kommer fra løsningsforslagene selv, som fra 2016 og framover oppgir hvilket
læringsmål hver oppgave tester. Løsningsforslagene sier dessuten selv at svarene
deres bare er eksempler på svar som gir uttelling, og at mange beslektede svar
godtas.

Forbehold: settene fra 2020 til august 2022 var hjemmeeksamener med alle
hjelpemidler og en annen oppgaveform. De er ikke representative, og det sier vi
hver gang de nevnes. Alle oppgaver, tall, grafer, navn og løsningsforslag i
denne boka er nyskrevet av oss.

Pensumlitteraturen er Cormen, Leiserson, Rivest og Stein, Introduction to
Algorithms — kjent som CLRS. Det er grunnen til at algoritmene i denne boka
heter Merge-Sort og Build-Max-Heap og ikke noe annet, og til at arrayene
indekseres fra 1 og ikke fra 0: oppgavene og fasitene bruker den notasjonen, og
forventer at du kjenner den igjen.

Denne boka er laget av Skolesaga. Den er ikke utgitt av eller tilknyttet NTNU,
og den kan ikke love deg noe bestemt eksamensresultat.

📝Oppgave 4

(Refleksjonsoppgave.) Du leser i en fasit at et svar «gir 4 av 5 poeng» fordi
hovedpoenget mangler, selv om alt som står er riktig.

a) Hva sier det om hvordan du bør bygge opp en definisjonsoppgave?

b) Du rekker ikke å fullføre en håndkjøring. Hva leverer du?

c) Du er usikker på om svaret ditt treffer den formuleringen fasiten bruker.
Bør du skrive flere alternative formuleringer for sikkerhets skyld?

Begrepsbank

Begrepsbanken er flashcard- og repetisjonsstoff — den gjentar det du nettopp har
lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet gjelder
kjernestoffet.

Temafrekvens

Hvor stor andel av eksamenssettene i grunnlaget et tema har vært med i. I denne boka er nevneren alltid 17 sett, fra august 2015 til august 2023 — de settene som er gjennomgått tema for tema. Tallet forteller deg hvor sikkert et tema kommer, ikke hvor mange poeng det er verdt. Asymptotikk står på 100 % (17 av 17) og gir typisk 2-3 oppgaver; stabil matching står på 12 % (2 av 17) og gir typisk én, når den først kommer.

Håndkjøring

Å utføre en navngitt algoritme for hånd, steg for steg, på et lite eksempel — og oppgi sluttilstanden. Det er oppgavetype C, og den forekommer på nær hvert sett; binære søketrær og hauger er de hyppigste strukturene, med 94 % (16 av de 17 settene i grunnlaget). To regler gjelder alltid. Du utfører trinnene mekanisk, også når input bryter strukturens egenskaper — du reparerer ikke først. Og du leverer bare det som etterspørres, i det formatet oppgaven ber om: hele arrayet, hele tabellen, eller ett tall.

Åpen designoppgave

Oppgavetype H: «hvordan vil du gå fram for å løse dette problemet?». De siste tre til fem oppgavene på et ordinært sett er av denne typen, og det er der toppkarakteren avgjøres. Et fullstendig svar har fem ledd: navngi det klassiske problemet, navngi paradigmet (grådig, dynamisk programmering, splitt og hersk, grafsøk, flyt), beskriv konstruksjonen, forklar hvordan du rekonstruerer selve løsningen — ikke bare verdien — og oppgi kjøretiden. Mangler ett ledd, mangler svaret et poeng.

Reduksjonsretning

A \le_p B

Gjenganger

Et tema eller en oppgavetype som kommer igjen på nesten hvert sett, slik at det er trygt å regne med at den dukker opp. I TDT4120 er gjengangerne uvanlig mange og uvanlig tydelige: seks temaer har vært med i 16 eller 17 av de 17 settene i grunnlaget. Det er derfor denne boka bruker frekvens til å styre omfanget på hvert kapittel, ikke til å velge bort noe.

Robust sensur

At en tvilsom oppgave håndteres til kandidatens fordel. Det er dokumentert to ganger i løsningsforslagene til dette faget: én rekurrens ble tatt ut av sensur fordi den falt utenfor pensumvarianten av masterteoremet, og én skrivefeil i en pseudokodelinje ble det tatt hensyn til under sensuren. Det er beroligende å vite. Det er ikke noe å planlegge etter — du kan ikke vite på forhånd hvilken oppgave det eventuelt gjelder.

Frisvar

At du formulerer svaret selv, i stedet for å krysse av blant ferdige alternativer. Hele TDT4120-eksamen er frisvar. Det er verdt å merke seg når du bruker quizen i denne boka: quizen er flervalg fordi den er laget for rask gjenkalling, mens eksamen krever at du produserer uttrykket, definisjonen eller sluttilstanden selv. Presisjonen trenes derfor i oppgavene og drillkapitlene, ikke i quizen.

CLRS

\lg n

De tre temaene som alltid kommer

Asymptotisk notasjon, sortering og NP-kompletthet med reduksjoner. Alle tre står på 100 % (17 av de 17 settene i grunnlaget). De er også de tre billigste å sikre seg, fordi de i stor grad testes med korte faktaspørsmål og definisjoner. Er du presset på tid, er dette rekkefølgen: disse tre først, deretter håndkjøring av haug og binært søketre.

De tre designtemaene

Maksimal flyt, dynamisk programmering og håndkjøring av datastrukturer — alle tre på 94 % (16 av de 17 settene i grunnlaget). Maksimal flyt og dynamisk programmering er verktøyene de åpne designoppgavene oftest ber om, og det er der karakteren skilles i toppen. De to har hvert sitt drillkapittel, og den tverrgående designdrillen i Del 8 kombinerer dem.

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.