8.1 Kortsvarssjangeren — å skrive presise, korte svar

Selve eksamensdisiplinen: svar med det etterspurte og ikke mer, sikre grunnpoengene først, og budsjettér tiden over 20 likt vektede oppgaver.

45 min

9 oppgaver

Kortsvarssjangerenå skrive presisekorte svar

Din fremgang i kapitlet

0 / 9 oppgaver

Kapitlets plass i kurset

Bygger på

0.1Eksamenskartet — slik testes TDT4120

Dette kapitlet handler ikke om ett tema — det handler om hvordan du svarer på alle de andre.

Eksamen i TDT4120 er én skriftlig prøve på fire timer med hjelpemiddelkode E, som betyr at du ikke får ha med deg noe som helst: ingen bok, ingen formelark, ingen kalkulator. Settet består av om lag 20 kortsvarsoppgaver som teller like mye. Fire timer fordelt på 20 oppgaver gir 12 minutter per oppgave, og hver oppgave er verdt om lag 5 prosent av karakteren.

Oppgavetypene går igjen fra sett til sett, og denne boka gir dem merkelappene sjanger A til H. Merkelappene er våre, ikke NTNUs — de er en huskeliste, og hver enkelt blir skrevet ut i klarspråk der den innføres nedenfor. Et eksempel på hva de betyr: sjanger C er håndkjøring, altså at du utfører algoritmen steg for steg på papiret og oppgir bare sluttilstanden. Sjanger H — åpen algoritmedesign, der du skal finne på en algoritme selv — står i hvert ordinært sett som de siste 3 til 5 oppgavene.

Prioritet: høyeste prioritet — dette må sitte. Kapitlet gir ingen nye algoritmer, men det påvirker uttellingen på hver eneste oppgave du skriver.

Forkunnskaper

Dette kapitlet krever ingen ny teori, og det kan leses når som helst — gjerne tidlig, slik at du trener riktig form fra første oppgave.

Det bygger på eksamenskartet i kap. 0.1, som presenterer sjangerkatalogen og feilkatalogen. Sjangrene trenes hver for seg gjennom boka: asymptotisk forenkling i kap. 1.3, rekurrenser i kap. 1.6, håndkjøring i kap. 3.3 og kap. 4.5, reduksjoner og NP-argumenter i kap. 7.4, og åpen algoritmedesign i kap. 8.2.

Eksemplene nedenfor bruker kjøretidsfakta fra kap. 3.1, kap. 4.1 og kap. 6.2, men bare som materiale — poenget her er formen på svaret, ikke faget i svaret.

Notasjons- og pseudokodeliste

Hva eksamen faktisk ber om (~10 min)

Se for deg eksamenslokalet klokka 13.40. Du har sittet i førti minutter, og du er fremdeles på oppgave 3 — en åpen designoppgave der du har skissert to modeller, forkastet den ene og begynt å skrive ut et bevis for at den andre virker. Du er nok inne på riktig spor. Men du har brukt over tre oppgavebudsjetter på én oppgave som teller nøyaktig like mye som de 19 andre, og 17 av dem er urørte.

Det er dette kapitlet handler om: ikke hva du kan, men hva du rekker å vise at du kan, og i hvilken form.

Eksamenssettet er frisvar, ikke flervalg: det står ingen alternativer å velge mellom, du skriver svaret selv. Det gjør formen på svaret til din egen beslutning — og dermed til noe du kan trene på.

Kortsvarsoppgave

En oppgave som ber om ett bestemt svar — ett uttrykk, én sluttilstand, én presis setning eller én kort designskisse — og som teller like mye som hver av de andre oppgavene i settet. Svarformen er frisvar: du formulerer svaret selv, uten alternativer å velge mellom. Et sett har om lag 20 slike oppgaver på fire timer. Det gir 12 minutter per oppgave i snitt og om lag 5 prosent av karakteren per oppgave. Kravet er at svaret er presist og fullstendig for det som er spurt om — ikke at det er langt.

I settene fra 2015 til 2018 sto det svart på hvitt på oppgavearket: lange svar teller ikke positivt. Setningen sto trykt i seks terminer, og den er borte fra hvert sett fra august 2019.

Disiplinen forsvant likevel ikke — den flyttet inn i oppgaveteksten. Dagens oppgaver sier det direkte der de stiller spørsmålet: «du skal her kun svare med output fra algoritmen», «oppgi svaret i $\Theta$ -notasjon», «forklar kort». Og løsningsforslagene svarer i samme ånd. Den aller første fasiten i settet fra desember 2025 er ett eneste uttrykk, og det er hele svaret.

Og skulle du glemme begge deler, holder det strukturelle argumentet alene: 20 oppgaver teller likt på fire timer. Hvert minutt du bruker på en utledning ingen har bedt om, er et minutt du tar fra 19 andre oppgaver som teller like mye. Det argumentet trenger ingen kilde — det er ren aritmetikk.

Denne boka bruker gjerne to sider på å utlede hvorfor Build-Max-Heap er $\Theta(n)$ og ikke $\Theta(n\lg n)$ . Eksamenssvaret på det samme spørsmålet er ett uttrykk pluss én linje begrunnelse. Det er ingen selvmotsigelse.

I undervisningen skal metoden forklares helt ut — det er slik du får den til å sitte, og det er derfor teoridelen i hvert kapittel ser ut som den gjør. Kortsvarsdisiplinen gjelder svarene på eksamen, der jobben er en annen: å vise at du har ferdigheten, på minst mulig plass.

Sagt kort: du må forstå mye mer enn du skriver. Men du skal ikke skrive alt du forstår.

Kortsvarsdisiplinen

\Theta

NTNU publiserer offisielle løsningsforslag for TDT4120, og de finnes for hver eneste av de 45 terminene fra desember 2003 til desember 2025. Det gir deg et uvanlig godt bilde av hva et godkjent svar ser ut som.

Og her kommer den mest beroligende opplysningen faget har: løsningsforslagene sier selv at svarene deres bare er eksempler på svar som gir uttelling, og at mange beslektede svar godtas. Du behøver altså ikke treffe formuleringen. Du må treffe innholdet: riktig uttrykk, riktig sluttilstand, riktig hovedpoeng, riktig retning på reduksjonen.

Det betyr også at du ikke skal skrive langt for å «dekke deg inn» i tilfelle formuleringen din ikke er den rette. Presisjon dekker deg inn. Lengde gjør det ikke.

📝Oppgave 1

(Forbedre svaret — sjanger E, altså en oppgave som spør etter en kjøretid.) Oppgaven lyder: «Hva er kjøretiden til Build-Max-Heap på et array med $n$ elementer? Oppgi svaret i $\Theta$ -notasjon.»

Du har skrevet dette utkastet på kladdearket:

«Build-Max-Heap kaller Max-Heapify på alle nodene fra $\lfloor n/2 \rfloor$ og nedover til 1. Max-Heapify er $O(\lg n)$ fordi den siver ett element nedover treet, og treet har høyde $\lg n$ . Siden vi kaller den omtrent $n/2$ ganger, kan vi tenke oss at kjøretiden blir $n/2$ ganger $\lg n$ , altså $O(n\lg n)$ . Men det viser seg at dette er en for løs grense, for de fleste nodene ligger langt nede i treet og har liten høyde, så summen blir mindre.»

Skriv om til svaret oppgaven ber om.

Svarformen sjanger for sjanger (~12 min)

Hver oppgavetype har sin egen svarform. Å kjenne formen er halve jobben: da vet du når svaret er ferdig, og du slutter å skrive.

Sjanger	Hva oppgaven ber om	Svarform	Typisk lengde
A asymptotisk forenkling	forenkle et uttrykk til strammeste form	ett uttrykk	1 linje
B rekurrensløsning	løs $T(n) = aT(n/b) + f(n)$ med navngitt metode	metodens navn, svaret, og hvilket masterteorem-tilfelle	1–3 linjer
C håndkjøring	kjør algoritmen på gitte data	kun sluttilstanden, i det formatet oppgaven ber om	sluttilstanden alene
D definisjon	forklar et begrep med egne ord	én presis setning, hovedpoenget først	1–2 setninger
E kjøretid	oppgi kjøretiden til en algoritme eller operasjon	uttrykket, med $\Theta$ eller $O$ bevisst valgt	1 linje
F «stemmer dette?»	avgjør om en påstand holder	ja eller nei først, så én presis setning	2 linjer
G reduksjon og NP	argumentér om et problems vanskelighet	retningen, hva den beviser, og hva den ikke beviser	2–4 linjer
H åpen algoritmedesign	konstruér en algoritme for et nytt problem	fem ledd (se kortet nedenfor)	5–10 linjer

Det finnes også en sjanger I — nivådelt essay. Den dukket bare opp i de hjemmeeksamensbaserte settene under pandemien, er ikke representativ for dagens eksamen, og omtales bare i kap. 0.1. Regn ikke med den.
Kortene under er de åtte sjangrene i pugbar form.

Sjanger A — asymptotisk forenkling

\Theta(n^2)

Sjanger B — rekurrensløsning med navngitt metode

T(n) = aT(n/b) + f(n)

Sjanger C — håndkjøring

Oppgaven gir konkrete data og ber deg utføre en navngitt algoritme steg for steg. Underveis fører du en tavle på kladdearket, men det er ikke tavlen som skal leveres. Svarform: kun sluttilstanden, i akkurat det formatet oppgaven ber om — hele arrayet for en maks-haug, utskriften fra Inorder-Tree-Walk for et binært søketre, hele tabellen inkludert døde celler for en kø, kantene i tilleggsrekkefølge for Kruskal . Fellen: å levere hele sporet i stedet for sluttilstanden, eller å «reparere» inndata som ser feil ut i stedet for å kjøre mekanisk.

Sjanger D — definisjon med egne ord

Oppgaven ber deg forklare et begrep: spenntre, stabil sortering, restkapasitet, blokkerende par. Den ber ikke om en historie om begrepet. Svarform: én presis setning med hovedpoenget først, eventuelt én setning til med det avgrensende kravet. Fellen: å bygge opp mot poenget i stedet for å begynne med det. Rekker du bare én setning, skal den ene setningen være den som teller.

Sjanger E — kjøretidskunnskap

\Theta

Sjanger F — «stemmer dette?»

Oppgaven legger fram en påstand — ofte en som nesten stemmer — og ber deg avgjøre om den holder. Svarform: ja eller nei først, deretter én presis setning som sier hvorfor, helst med et konkret moteksempel når svaret er nei. Til sammen to linjer. Fellen: å drøfte i tre setninger og aldri konkludere. Et svar uten ja eller nei har ikke besvart oppgaven.

Sjanger G — reduksjon og NP-argument

X

Sjanger H — åpen algoritmedesign

Oppgaven beskriver et nytt problem i en hverdagslig innpakning og ber deg konstruere en algoritme. Dette er settets siste 3 til 5 oppgaver. Svarform — fem ledd, 5 til 10 linjer: (1) navngi det klassiske problemet innpakningen skjuler, (2) navngi paradigmet — grådig, dynamisk programmering, splitt og hersk, grafsøk, flyt eller stabil matching, (3) beskriv konstruksjonen (noder, kanter og kapasiteter, eller delproblem, rekurrens og grunntilfeller), (4) forklar hvordan du rekonstruerer selve løsningen, ikke bare verdien, og at det ikke øker den asymptotiske kjøretiden, (5) oppgi kjøretiden med alle symboler definert. Fellen: å stoppe etter ledd 3.

✏️Eksempel 1: Samme oppgave, tre utkast (sjanger F)

«Stemmer det at Dijkstra finner korteste vei i enhver rettet graf med reelle kantvekter? Begrunn kort.»

Tre utkast ligger på kladdearket. Hvilket av dem er svaret oppgaven ber om?

Utkast 1: «Dijkstra er en grådig algoritme som holder et sett av ferdigbehandlede noder og gjentatte ganger plukker den ubehandlede noden med minst $d$ -verdi fra en prioritetskø, og slakker alle kanter ut fra den. Med binærhaug er kjøretiden $O(E\lg V)$ . Algoritmen ligner på Prim, som bygger et minimalt spenntre.»

Utkast 2: «Det kommer an på grafen. I mange grafer virker den fint, men det finnes tilfeller der den ikke gjør det, særlig hvis vektene oppfører seg spesielt.»

Utkast 3: «Nei. Dijkstra krever ikke-negative kantvekter; med en negativ kant kan en node bli erklært ferdig før den korteste veien til den er funnet. Bellman-Ford tåler negative kanter og kjører på $\Theta(VE)$ .»

Utkast 3 er svaret.

Utkast 1 er faglig korrekt og fullstendig irrelevant: det forklarer hvordan Dijkstra virker, mens oppgaven spør om den alltid virker. Ingen del av utkastet svarer ja eller nei. Utkast 2 svarer heller ikke — «det kommer an på» er ingen konklusjon, og «hvis vektene oppfører seg spesielt» navngir ikke betingelsen.

Utkast 3 har sjanger F-formen: nei først, så én setning som navngir betingelsen som brytes, og et alternativ som ikke bryter den. To linjer, ferdig.

Legg merke til hva som gjør utkast 1 farlig: det ser grundig ut. Det inneholder mer riktig fagstoff enn utkast 3. Men oppgaven ba om en avgjørelse, og en avgjørelse står det ikke noe om.

📝Oppgave 2

(Forbedre svaret — sjanger D, definisjon med egne ord.) Oppgaven lyder: «Forklar med egne ord hva et minimalt spenntre er.»

Utkastet ditt:

«Spenntrær er et sentralt tema i grafteorien og brukes blant annet i nettverksplanlegging. Man kan finne dem med Prim eller Kruskal, som begge er grådige algoritmer, og Kruskal bruker Union-Find for å oppdage sykler. Et spenntre er et tre, og et tre er en sammenhengende graf uten sykler. Når grafen har vekter på kantene, kan vi lete etter det spenntreet som har lavest total vekt.»

Skriv om til svaret oppgaven ber om.

📝Oppgave 3

(Forbedre svaret — sjanger C, håndkjøring.) Oppgaven lyder: «Sett inn nøklene 8, 3, 11, 1, 6 i denne rekkefølgen i et tomt binært søketre. Oppgi utskriften fra Inorder-Tree-Walk på det ferdige treet.»

Utkastet ditt:

«Først settes 8 inn som rot. Så kommer 3, som er mindre enn 8 og går til venstre. Så 11, som er større enn 8 og går til høyre. Så 1, som er mindre enn 8 og mindre enn 3, altså venstre barn av 3. Så 6, som er mindre enn 8 og større enn 3, altså høyre barn av 3. Treet er da bygget, og en Inorder-Tree-Walk besøker venstre deltre, så roten, så høyre deltre.»

Skriv om til svaret oppgaven ber om.

Hovedpoenget først — slik sikrer du delvis uttelling (~8 min)

Delvis uttelling betyr at et svar som er riktig så langt det rekker, gir poeng for den delen som er riktig, selv om svaret ikke er komplett. Du får altså ikke null for et halvferdig svar — du får uttelling for halvparten som står der.

Det har en direkte konsekvens for hvordan du bør ordne setningene dine: det viktigste skal stå først. Løsningsforslagene i faget viser gjennomgående samme mønster — hovedpoenget kommer i første setning, presiseringen i den andre. Skriver du motsatt vei, og tiden tar deg midt i svaret, har du levert oppvarmingen og ikke poenget.

Dette gjelder alle sjangrene, men slår hardest ut i tre av dem:

- Definisjon (sjanger D): kravet som gjør begrepet til nettopp det begrepet, kommer i første setning.
- «Stemmer dette?» (sjanger F): ja eller nei står helt først, før begrunnelsen.
- Åpen design (sjanger H): navnet på det klassiske problemet og paradigmet står før konstruksjonen. Rekker du ikke å skrive ut hele konstruksjonen, har du likevel vist at du kjente igjen problemet.

Delvis uttelling

Prinsippet om at et ufullstendig svar gir uttelling for de delene som er riktige, i stedet for null. Det betyr at rekkefølgen på setningene dine har betydning for karakteren. Praktisk regel: skriv hovedpoenget i første setning, presiseringen i den andre, og eventuelle eksempler til slutt. Blir du avbrutt av klokka, har du da mistet det minst viktige. Skriver du motsatt vei, mister du det viktigste.

✏️Eksempel 2: Samme innhold, to rekkefølger (sjanger D)

«Forklar hva det vil si at en sorteringsalgoritme er stabil.»

To svar inneholder nøyaktig det samme fagstoffet, men i motsatt rekkefølge.

Svar A: «Når vi sorterer, kan flere elementer ha samme nøkkel. Det er for eksempel tilfellet når vi sorterer en liste over ansatte etter avdeling, og flere jobber i samme avdeling. Da kan man spørre seg hva som skjer med rekkefølgen mellom dem. Noen algoritmer beholder den, andre gjør det ikke. De som beholder den, kaller vi stabile.»

Svar B: «En sorteringsalgoritme er stabil hvis elementer med lik nøkkel beholder sin innbyrdes rekkefølge fra inndata. Det er egenskapen radikssortering hviler på: den sorterer siffer for siffer og trenger at hvert delsorteringssteg ikke ødelegger arbeidet fra det forrige.»

Svar B er formen oppgaven ber om.

Begge svarene sier til slutt det samme. Forskjellen er hvor definisjonen står. I svar A kommer den i siste setning, etter tre setninger oppvarming — og den kommer indirekte («de som beholder den, kaller vi stabile»). I svar B står den i den første setningen, direkte, og den andre setningen legger til noe som viser at du vet hvorfor egenskapen betyr noe.

Svar B er dessuten kortere. Det er ingen tilfeldighet: når hovedpoenget står først, faller behovet for opptrapping bort av seg selv.

📝Oppgave 4

(Forbedre svaret — sjanger F.) Oppgaven lyder: «Stemmer det at 0-1-ryggsekkproblemet kan løses i polynomisk tid med dynamisk programmering, siden algoritmen kjører på $\Theta(nm)$ der $n$ er antall gjenstander og $m$ er kapasiteten? Begrunn kort.»

Utkastet ditt:

«Dynamisk programmering løser 0-1-ryggsekk ved å fylle en tabell med én rad per gjenstand og én kolonne per kapasitetsverdi fra 0 til $m$ . Hver celle regnes ut i konstant tid fra to celler i raden over, så samlet kjøretid er $\Theta(nm)$ . Det er et produkt av to tall fra inndata, og produkter av inndatastørrelser pleier å være polynomiske, så da må jo svaret være ja.»

Skriv om til svaret oppgaven ber om.

📝Oppgave 5

(Forbedre svaret — sjanger B, rekurrens.) Oppgaven lyder: «Løs rekurrensen $T(n) = 2T(n/2) + n$ med en navngitt metode.»

Utkastet ditt:

«Vi kan tegne rekursjonstreet. På toppnivået gjør vi $n$ arbeid. På nivået under har vi to delproblemer av størrelse $n/2$ , som gir $n/2 + n/2 = n$ arbeid. På nivået under det har vi fire delproblemer av størrelse $n/4$ , som også gir $n$ arbeid. Slik fortsetter det nedover. Treet har mange nivåer, og hvert nivå koster $n$ , så totalen blir stor. Svaret blir noe i nærheten av $n$ ganger antall nivåer.»

Skriv om til svaret oppgaven ber om.

Tidsbudsjettet over fire timer (~8 min)

Regnestykket er kort: 240 minutter delt på 20 oppgaver er 12 minutter per oppgave, og hver oppgave er verdt 5 prosent. Setter du av et kvarter til gjennomlesing på slutten, blir snittet 11,25 minutter.

Det interessante er hva som skjer når du overskrider budsjettet på én oppgave:

Tid brukt på én oppgave	Andel av ett oppgavebudsjett	Igjen per oppgave for de 19 andre
12 min	1,00	12,0 min
20 min	1,67	11,6 min
30 min	2,50	11,1 min
40 min	3,33	10,5 min

Én overskridelse er billig. Det er ikke den som velter settet. Det som velter settet, er at overskridelsene kommer flere ganger, og at de kommer på de vanskeligste oppgavene — slik at du bruker mest tid der uttellingen er minst sannsynlig, og til slutt ikke rekker de siste oppgavene i det hele tatt.
Og siste oppgave er ikke en bonusoppgave. To ubesvarte oppgaver er 10 prosentpoeng av 100, uansett hvor de sto i settet.

Tidsbudsjettet på eksamen

Fordelingen av fire timer over om lag 20 likt vektede oppgaver: 12 minutter per oppgave i snitt, eller 11,25 minutter hvis du reserverer et kvarter til gjennomlesing. Budsjettet er et tak, ikke et mål. De fleste oppgavene i sjangrene A, D, E og F tar to til fem minutter når stoffet sitter, og den tiden du sparer der, er tiden designoppgavene i sjanger H skal ha. Regel: ingen oppgave får koste mer enn omtrent to budsjetter i første runde.

Å hoppe videre er ikke å gi opp. Gjør det i tre trinn, så koster det nesten ingenting å komme tilbake:

1. Skriv ned det du allerede vet. Selv på en designoppgave du ikke har løst: «Dette er et tilordningsproblem, og jeg vil modellere det som maks-flyt.» Det er ledd 1 og 2 av svaret, og de gir uttelling i seg selv.
2. Sett et merke i margen og noter i én linje hvor du står fast — «mangler kapasitetene på kantene inn mot sluket».
3. Gå videre, og kom tilbake når du har vært gjennom hele settet. Hjernen jobber videre på det i mellomtiden, og du kommer ofte tilbake med svaret ferdig.

Rekkefølgen på settet er ikke bindende. Er oppgave 4 en definisjon du kan, og oppgave 3 en designoppgave du ikke ser løsningen på, tar du oppgave 4 først. De teller like mye.

📝Oppgave 6

(Tidsbudsjett.) Et sett har 20 likt vektede oppgaver og fire timer. Du har brukt 2 timer og 10 minutter, og har besvart 11 oppgaver. Av de 9 som gjenstår, er 4 korte definisjons- og kjøretidsoppgaver du kjenner godt igjen, 3 er håndkjøringer, og 2 er åpne designoppgaver.

a) Hvor mange minutter har du igjen per gjenstående oppgave i snitt?

b) Foreslå en rekkefølge og en grov tidsfordeling for de 9 oppgavene, og begrunn den i én setning.

Å treffe læringsmålet oppgaven tester (~7 min)

Et læringsmål er en setning som sier hva du skal kunne etter et emne — for eksempel «kunne kjøretiden til de sentrale algoritmene, og forstå utregningen av dem». Fra rundt 2016 oppgir løsningsforslagene i TDT4120 hvilket læringsmål hver enkelt oppgave tester.

Det er nyttigere enn det høres ut. Læringsmålene bruker gjennomgående tre ulike verb, og hvert verb ber om sin egen svarform:

Verbet i læringsmålet	Hva oppgaven vil se	Hva som ikke hjelper
definere et begrep	den avgrensende egenskapen, i én setning	eksempler på hvor begrepet brukes
utføre en algoritme	sluttilstanden i riktig format	en forklaring av hvordan algoritmen virker
kjenne kjøretiden og forstå utregningen	uttrykket, og eventuelt den ene linjen som gir det	en gjennomgang av algoritmens oppbygning
bruke kjente algoritmer på nye problemer	modellering, konstruksjon, rekonstruksjon og kjøretid	en gjentakelse av hva algoritmen gjør

Kolonnen til høyre er verdt et øyeblikk. Alt som står der, er faglig riktig stoff. Det er bare svar på et annet spørsmål enn det som ble stilt — og det er nettopp derfor det er så lett å skrive.

Læringsmål-treff

Å svare på nøyaktig den ferdigheten oppgaven tester, i stedet for å skrive alt du kan om temaet. Løsningsforslagene i faget oppgir fra rundt 2016 hvilket læringsmål hver oppgave hører til, og verbet i målet forteller deg svarformen. Praktisk regel: finn verbet i oppgaveteksten før du skriver. «Oppgi» og «hva er» vil ha ett uttrykk. «Utfør» og «kjør» vil ha en sluttilstand. «Forklar» og «hva vil det si» vil ha én presis setning. «Beskriv en algoritme som» vil ha de fem leddene i en designskisse.

✏️Eksempel 3: En designoppgave besvart i kortsvarsform (sjanger H)

«Et bibliotek skal fordele et antall lesesalsplasser mellom studenter. Hver student har oppgitt hvilke av lesesalene hun kan bruke, og hver lesesal har et gitt antall plasser. Beskriv en effektiv algoritme som finner en fordeling der flest mulig studenter får plass. Oppgi kjøretiden.»

Dette er settets nest siste oppgave. Du har 12 minutter.

Svaret, slik det leveres:

1. Dette er et tilordningsproblem med kapasiteter — et bipartitt matchingsproblem der den ene siden har kapasitet mer enn 1.
2. Paradigme: maksimal flyt.
3. Konstruksjonen: lag en kilde $s$ og et sluk $t$ . Én node per student, én node per lesesal. Kant fra $s$ til hver student med kapasitet 1. Kant fra student til lesesal med kapasitet 1 for hver lesesal studenten kan bruke. Kant fra hver lesesal til $t$ med kapasitet lik antall plasser på salen. Kjør Edmonds-Karp fra $s$ til $t$ .
4. Rekonstruksjon: fordelingen leses rett av flyten — student $u$ får sal $v$ nøyaktig når kanten $(u,v)$ fører én enhet flyt. Siden alle kapasitetene er heltall, gir heltallsteoremet at maks-flyten kan velges heltallig, så hver slik kant fører 0 eller 1 og fordelingen er entydig lesbar. Avlesningen går gjennom kantene én gang og koster $O(E)$ , som ikke øker den asymptotiske kjøretiden.
5. Kjøretid: $O(VE^2)$ med Edmonds-Karp, der $V$ er antall noder i flytnettet (studenter, saler og de to ekstra) og $E$ er antall kanter, altså summen av antall studenter, antall saler og antall student–sal-par.

Slik faller uttellingen. Ledd 1 og 2 er det som skiller «har ingenting» fra «er på riktig spor»: en besvarelse som bare sier «dette modelleres som maks-flyt med kilde og sluk» har allerede sikret en del av oppgaven. Ledd 3 er tyngdepunktet — det er der kapasitetene faktisk avgjør om modellen løser problemet, og en modell uten kapasitet 1 ut fra hver student ville latt én student få to saler. Ledd 4 er det leddet flest hopper over: oppgaven ber om en fordeling, ikke om et antall, og uten heltallsteoremet er det ikke opplagt at flyten i det hele tatt kan leses som en fordeling. Ledd 5 er billig når de fire første står.

Legg merke til hva som ikke står i svaret: ingen forklaring av hva et restnett er, ingen gjennomgang av hvordan Edmonds-Karp finner forøkende stier, intet bevis for maks-flyt/min-snitt-teoremet. Alt det er pensum, og ingenting av det ble spurt om.

📝Oppgave 7

(Forbedre svaret — sjanger G, reduksjon.) Oppgaven lyder: «En student vil vise at problemet $X$ er NP-hardt, og gir følgende argument: Jeg viser at $X$ kan reduseres i polynomisk tid til 3-CNF-SAT. Siden 3-CNF-SAT er NP-komplett, er $X$ dermed NP-hardt. Er argumentet gyldig? Begrunn kort.»

Utkastet ditt:

«Reduksjoner er en måte å sammenligne vanskelighetsgrad på. Hvis vi har en polynomisk reduksjon mellom to problemer, kan vi bruke en algoritme for det ene til å løse det andre, med bare polynomisk ekstraarbeid. 3-CNF-SAT er et av de mest brukte problemene å redusere fra, fordi det er NP-komplett, og det er ganske fleksibelt. Studenten har brukt 3-CNF-SAT, som er et fornuftig valg.»

Skriv om til svaret oppgaven ber om.

📝Oppgave 8

(Forbedre svaret — sjanger H, åpen design.) Oppgaven lyder: «En strømleverandør skal dele en lang kabel i biter. For hver mulig bitlengde er det oppgitt hva biten selges for. Beskriv en effektiv algoritme som finner den oppdelingen som gir høyest samlet salgsverdi. Oppgi kjøretiden.»

Utkastet ditt:

«Dette er et optimeringsproblem. Vi kan bruke dynamisk programmering, som er en teknikk der man løser små delproblemer først og setter sammen svarene, i motsetning til splitt og hersk, der delproblemene ikke overlapper. Vi lager en tabell og fyller den ut nedenfra og opp. Til slutt står den beste verdien i den siste cellen. Kjøretiden blir kvadratisk.»

Skriv om til det femleddede designsvaret.

📝Oppgave 9

(Forbedre svaret — sjanger A og E i kombinasjon.) Oppgaven lyder: «En algoritme sorterer først $n$ heltall i området fra 0 til $n^2$ med Counting-Sort, og kjører deretter et binærsøk $n$ ganger på det sorterte arrayet. Oppgi samlet kjøretid i $\Theta$ -notasjon, som ett strammest mulig uttrykk.»

Utkastet ditt:

«Counting-Sort er $\Theta(n+k)$ der $k$ er størrelsen på verdiområdet, og den er stabil, som er nyttig i radikssortering. Binærsøk er $O(\lg n)$ per søk fordi søkeområdet halveres hver gang. Vi gjør $n$ søk, så det blir $O(n\lg n)$ til sammen. Samlet får vi $\Theta(n+k) + O(n\lg n)$ , og siden begge leddene er med, kan vi si at kjøretiden er $O(n + k + n\lg n)$ .»

Skriv om til svaret oppgaven ber om.

Typiske feil

De fire feilene under er formfeil: de koster uttelling selv når fagstoffet i svaret er riktig.

- Å skrive langt i stedet for presist. Et langt svar gir ingen ekstra uttelling, og det koster minutter du trenger på de andre oppgavene. Verre: jo mer du skriver, desto større er sjansen for at noe av det er galt, og et galt tillegg trekker.
- Å svare på mer enn det etterspurte. Å forklare hvordan Dijkstra virker når oppgaven spør om den alltid virker, er å besvare et annet spørsmål. Sjekk verbet i oppgaveteksten før du skriver.
- Å utelate hovedpoenget i en definisjon. Bygger du opp mot poenget og blir avbrutt, står oppvarmingen igjen alene. Hovedpoenget først, alltid.
- Å henge fast på én oppgave. Ingen oppgave er verdt mer enn de andre. Skriv ned det du vet, sett et merke i margen, gå videre.

To innholdsfeller viser seg særlig tydelig i korte svar, fordi det ikke er noe rundt dem å gjemme seg bak:

- Felle #4 — løs asymptotisk grense der en strammere finnes. $O(n^2)$ er sant om en algoritme som er $\Theta(n)$ , og likevel utilstrekkelig. Er grensen tett, skriv $\Theta$ .
- Felle #6 — å påstå at rekonstruksjon fra en dynamisk programmering er trivielt gratis. Den koster ingen ekstra asymptotisk kjøretid, men den krever at beslutningene ble lagret underveis, og den setningen må stå i svaret.

Faget bruker skalaen A til F, og hele karakteren avgjøres av denne ene fire timers eksamenen.

C er en god og vanlig karakter. Den nås av den som har grunnferdighetene på plass: riktige kjøretidsfakta, riktig håndkjøring, standarddefinisjonene formulert presist, og riktig retning på reduksjonsspørsmål. Det er ikke et minimum man så vidt klarer — det er en solid besvarelse.

Skal du høyere, er det ikke fordi det er noe galt med en C-besvarelse. Det er fordi det står igjen en meny av oppgraderinger, og du kan plukke fra den i den rekkefølgen du vil:

- komplette svar på de åpne designoppgavene, med alle fem leddene og ikke bare de tre første;
- riktig retning på reduksjonen, hver gang, og en setning om hva reduksjonen ikke beviser;
- rekonstruksjon av selve løsningen i DP-oppgaver, ikke bare optimalverdien;
- finessene: heltallsteoremet i flytmodellering, kravet om korteste forøkende sti i Edmonds-Karp, og skillet mellom pseudopolynomisk og polynomisk.

Fire punkter. Det er hele gapet, og hvert av dem kan trenes hver for seg.

Kjøretidsfakta som skal kunne stå alene i et svar

Sjanger E-oppgaver ber om ett uttrykk. Da må uttrykket sitte, og det må sitte sammen med kravet eller egenskapen som hører til — det er ofte den ene linjen begrunnelse oppgaven ber om i tillegg.

Algoritme	Beste	Verste	Forventet	Krav/egenskap
`Merge-Sort`	$\Theta(n\lg n)$	$\Theta(n\lg n)$	$\Theta(n\lg n)$	stabil, men ikke på stedet
`Heapsort`	$\Theta(n\lg n)$	$\Theta(n\lg n)$	$\Theta(n\lg n)$	på stedet, ustabil
`Counting-Sort`	$\Theta(n+k)$	$\Theta(n+k)$	$\Theta(n+k)$	stabil; krever heltall i området $0$ til $k$
`Build-Max-Heap`	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$	ikke $\Theta(n\lg n)$ — nesten alle noder har liten høyde
`Randomized-Select`	$\Theta(n)$	$\Theta(n^2)$	$\Theta(n)$	forventningen er over algoritmens egne tilfeldige valg
`Select` (median av medianer)	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$	lineær også i verste tilfelle
Hashing med kjeding	$\Theta(1)$	$\Theta(n)$	$\Theta(1+\alpha)$	$\alpha$ er lastfaktoren, altså elementer per kurv
`BFS`	$\Theta(V+E)$	$\Theta(V+E)$	$\Theta(V+E)$	gir færrest kanter, ikke minst vekt
`Dijkstra` (binærhaug)	$O(E\lg V)$	$O(E\lg V)$	$O(E\lg V)$	krever ikke-negative kantvekter
`Bellman-Ford`	$\Theta(VE)$	$\Theta(VE)$	$\Theta(VE)$	tåler negative kanter, oppdager negative sykler
`Floyd-Warshall`	$\Theta(V^3)$	$\Theta(V^3)$	$\Theta(V^3)$	alle-til-alle korteste vei
`Edmonds-Karp`	$O(VE^2)$	$O(VE^2)$	$O(VE^2)$	krever korteste forøkende sti
`Ford-Fulkerson`	—	avhenger av kapasitetenes størrelse	—	pseudopolynomisk
`Huffman`	$O(n\lg n)$	$O(n\lg n)$	$O(n\lg n)$	gir en optimal prefikskode
`Gale-Shapley`	$O(n^2)$	$O(n^2)$	$O(n^2)$	terminerer alltid, gir alltid en stabil matching, frier-optimal
LCS med DP	$\Theta(nm)$	$\Theta(nm)$	$\Theta(nm)$	$n$ og $m$ er lengdene på de to sekvensene
0-1-`Knapsack` med DP	$\Theta(nm)$	$\Theta(nm)$	$\Theta(nm)$	pseudopolynomisk — $m$ er en tallverdi, ikke et antall

Begrepsbank

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

Hjelpemiddelkode E

NTNUs kode for eksamen uten noen hjelpemidler i det hele tatt : ingen bok, ingen egne notater, ingen formelsamling, ingen kalkulator. Konsekvensen for lesingen din er direkte: kjøretidstabellen, definisjonene og masterteoremets tre tilfeller må sitte i hodet. «Det kan jeg slå opp» er ikke en tilgjengelig strategi på denne eksamen.

Strammeste asymptotiske uttrykk

\Theta

Sluttilstand som svarform

Det ferdige resultatet av en håndkjøring, levert i det formatet oppgaven navngir — og ingenting av sporet som førte fram til det. Formatene som går igjen: maks-haug oppgis som hele arrayet med indeks fra 1; binært søketre som utskriften fra Inorder-Tree-Walk; FIFO-kø som hele tabellen inkludert de døde cellene, pluss head og tail; Kruskal som kantene i den rekkefølgen de ble lagt til; maks-flyt som flytverdien, og et min-snitt i tillegg når begge er spurt om; Huffman som kodelengden per tegn; Gale-Shapley som den ferdige matchingen, med angivelse av hvilken orientering som ble kjørt.

Repetisjonsoppgaver

Kort oppsummert

- Settet er om lag 20 likt vektede kortsvarsoppgaver på fire timer: 12 minutter per oppgave, om lag 5 prosent hver.
- Kortsvarsdisiplinen gjelder svarene, ikke læringen. Du må forstå mye mer enn du skriver — men ikke skrive alt du forstår.
- Hver sjanger har sin form. Ett uttrykk (A, E), metode og tilfelle (B), sluttilstand (C), én presis setning (D), ja eller nei først (F), retning og konsekvens (G), fem ledd (H).
- Hovedpoenget først. Delvis uttelling belønner rekkefølgen din.
- Finn verbet i oppgaveteksten før du skriver. «Oppgi», «utfør», «forklar» og «beskriv en algoritme som» ber om fire forskjellige svar.
- Ingen oppgave er verdt mer enn de andre. Skriv ned det du vet, sett et merke i margen, gå videre.

Neste kapittel, kap. 8.2, tar den sjangeren som er vanskeligst å levere kort og fullstendig samtidig: de åpne designoppgavene.

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.