0.1 Eksamenskartet — slik testes IN2010

Eksamensformen (digital firetimers hjelpemiddelfri tredeling i Inspera), antigjettings-skaleringen, poengtrappen, temafrekvensene, sjangerkatalogen A–L og lesestrategien som styrer hele boka.

35 min

4 oppgaver

Eksamenskartetslik testes IN2010

Din fremgang i kapitlet

0 / 4 oppgaver

Slik testes IN2010

IN2010 Algoritmer og datastrukturer handler om to ting: å velge riktig
datastruktur, og å skrive den algoritmen som løser oppgaven raskest mulig.
Eksamen tester nøyaktig det — men den gjør det på tre helt forskjellige måter
i løpet av de samme fire timene.

Du skal kunne fakta sikkert, uten å slå opp: hvor lang tid en operasjon
tar, hvilke sorteringer som er stabile, hva en heap kan og ikke kan gjøre.
Du skal kunne utføre en struktur for hånd: sette inn seks tall i en
hashtabell og skrive opp hele tabellen etterpå, feilfritt. Og du skal kunne
skrive en algoritme selv, i pseudokode, for et problem du ikke har sett
før — og oppgi hvor lang tid den bruker.

Den gode nyheten er at settet har sett nesten likt ut hvert år siden 2021.
Dette kapitlet viser deg hvordan det ser ut, hva som gir poeng, og i hvilken
rekkefølge du bør lese resten av boka. Det er verdt de 35 minuttene.

Tre praktiske ting før vi går inn i detaljene.

Karakterskalaen. Faget vurderes med bokstavkarakterer fra A til F, der
A er best og F betyr ikke bestått. Det finnes ingen deleksamen og ingen mappe:
én skriftlig eksamen avgjør hele karakteren. C er en god og vanlig
karakter — den betyr at du behersker faget. Boka er skrevet for å få deg
trygt gjennom og et hakk høyere, ikke for å jage plettfrihet.

Oppgavetypene har hver sin bokstav. Boka bruker tolv bokstaver, A til
L, som navn på de oppgavetypene som faktisk går igjen. Det er ikke offisielle
UiO-koder — det er bokas egen sortering, laget for at du skal kjenne igjen en
oppgave og huske oppskriften. Hver gang en bokstav brukes i et kapittel,
skrives den ut i klartekst første gang, slik: «sjanger E — håndkjøring, altså
at du utfører operasjonen steg for steg og oppgir sluttilstanden». Hele lista
står i sjangerkortet lenger nede i dette kapitlet.

Feilene har numre. Boka nummererer de tolv vanligste feilene, fra #1 til
#12. Nummeret er en snarvei, ikke en gåte: hver gang et nummer brukes,
står forklaringen i parentes rett ved, slik: «(#3 — down-heap uten å sjekke at
barnet finnes)». Hele registeret står samlet i dette kapitlet, med henvisning
til hvilken del av boka som forebygger hver feil.

Og en beroligende ting: hver algoritme forklares der den brukes. Du trenger
ikke huske en algoritme fra et tidligere kapittel for å komme videre — den
gjentas i kortform der den dukker opp igjen.

Notasjons- og pseudokodeliste

Eksamensformen

Vurderingen er én digital skoleeksamen på fire timer, som teller 100 prosent.

Den avholdes i Inspera, som er UiOs digitale eksamenssystem: du sitter på et
eksamenslokale med en maskin som er låst til eksamensverktøyet, og skriver
svarene rett inn i nettleseren.

Fire faste trekk du må planlegge etter:

- Ingen hjelpemidler. Ingen bok, ingen notater, ingen kalkulator, intet
oppslagsverk. Alt du skal bruke, må ligge i hodet.
- Ingen håndskrift. Også pseudokoden skrives inn i Inspera. Du kan ikke
laste opp et fotografert ark, og du kan ikke tegne et tre og levere bildet.
Dette er verdt å øve på: en algoritme du «ser for deg», må ut i tekst.
- Karakter A til F, og de obligatoriske innleveringene i emnet må være
godkjent for at du skal få gå opp. De gir ingen karakterpoeng i seg selv.
- Engelsk oversettelse følger alltid med settet, så et vanskelig norsk
begrep kan du kontrollere mot den engelske teksten.

De tre delene av settet

Settet har hatt samme tredeling hvert eneste år siden 2021:

Del av settet	Hva det er	Vekt
Oppvarmingen	«Hva er en algoritme?» og «Hva er en datastruktur?», maks fire setninger på hver. Det finnes ikke noe fasitsvar — alle rimelige svar gir full uttelling	2 poeng (faste gratispoeng)
Del 1	Mange små spørsmål som rettes automatisk: sant/usant om kjøretid, sortering, heap, hashing, grafer og litt kompleksitetsteori, pluss noen korte svar (ett tall, ett uttrykk) og små håndkjøringer	typisk 20–35 poeng
Del 2	Fem til sju større oppgaver à 8–12 poeng der du skal skrive pseudokode og resonnere. De stiger i vanskelighet, og de siste én til to er nesten alltid åpen grafmodellering	her avgjøres karakteren

At Del 1 er auto-rettet betyr at en maskin sammenligner svaret ditt med en
fasit. Det har to konsekvenser: du får ingen delpoeng for et nesten-riktig
svar, og formatet må være akkurat som oppgaven ber om. Del 2 leses derimot av
et menneske, og der er delpoeng regelen snarere enn unntaket.

Oppvarmingen er verdt et lite råd allerede nå: skriv noe. To poeng er to
poeng, og det eneste som ikke gir uttelling, er blankt eller noe direkte galt.

Antigjettings-skaleringen

Sant/usant-blokkene på Del 1 er skalert slik at ren gjetting i snitt gir
null. Det er dette boka kaller antigjettings-skalering, og det er den
mest særpregede mekanismen i faget.

Slik har det sett ut i de settene boka bygger på:

År	Skalering på sant/usant	Hva det betyr
2019	ett minuspoeng for feil eller ubesvart på et par flervalgspunkter	feil og blankt teller likt
2021	ett minuspoeng for feil eller ubesvart; summen kan ikke gå under null	feil og blankt teller likt
2023	$2 \cdot \max(n - 16,\ 0)$ , der $n$ er antall riktige av 32	16 riktige gir 0 poeng
2024	$2 \cdot \max(n - 11,\ 0)$ , der $n$ er antall riktige av 22	11 riktige gir 0 poeng

Les 2023-formelen sakte. Med 32 sant/usant-punkter vil en som kaster mynt og
kron treffe rundt 16 av dem — og 16 riktige gir nøyaktig null poeng.
Kunnskapen din begynner altså å telle først over halvparten. Med 24 sikre er du
på 16 poeng, med 30 sikre på 28.
Den andre halvdelen av regelen er like viktig: på de vanlige korte

svarene — der du skal skrive et uttrykk, et tall eller en kort liste — gjøres
det ingen forskjell på feil svar og blankt svar. Der taper du ingenting på
å skrive det beste du kommer på, og du kan bare tjene. La derfor aldri et kort
svar stå tomt.

Og for ordens skyld, siden mange tror det motsatte: i alle de skaleringene som
er dokumentert over, teller et feil kryss nøyaktig like mye som et blankt —
altså ingenting ekstra i minus. Skaleringen straffer deg ikke for å fylle ut;
den sørger for at du ikke kan bløffe deg til poeng. Poengsummen din på Del
1 blir omtrent nøyaktig så stor som mengden fakta du kan sikkert. Det er derfor

faktakapitlet kap. 1.4 har høyeste prioritet i hele boka.

📝Oppgave 1

(Innstegsoppgave — les av formelen i tabellen over.) En sant/usant-blokk har 32
punkter og skaleres med $2 \cdot \max(n - 16,\ 0)$ , der $n$ er antall riktige.

a) Hvor mange må du ha riktige før du tjener ditt første poeng?
b) Hvor mange poeng får du med 24 riktige?
c) Hva sier dette om å svare på en sant/usant-blokk der du er helt blank?

Poengtrappen: lavere kjøretid er mer poeng

Den andre store mekanismen ligger på Del 2, og den er skrevet rett ut i
sensorveiledningene år etter år: «lavere kjøretidskompleksitet er mer
poenggivende.»

En poengtrapp betyr at samme oppgave har flere riktige svar med ulik
uttelling. Et typisk mønster ser slik ut:

Løsningen din	Uttelling på oppgaven
$O(n)$ — den beste kjente	full pott
$O(n \log n)$ — riktig, men tregere	et godt stykke mindre
$O(n^2)$ — den naive	minst, men ikke null

Legg merke til den siste linja: en treg løsning som virker, gir fortsatt poeng.
Det betyr at du aldri skal levere blankt på en Del 2-oppgave. Skriv den
naive løsningen, si at den er

O(n^2)

, og fortsett.
Men det betyr også det motsatte: å finne det raskere svaret er ikke pynt, det

er poeng. Hele boka er bygd rundt spørsmålet «kan dette gjøres raskere?», og
kap. 1.1 til kap. 1.4 gir deg
apparatet til å svare på det.

📝Oppgave 2

(Refleksjon over poengtrappen.) En Del 2-oppgave er verdt 8 poeng og har den
vanlige trappen: den beste løsningen er $O(n)$ , en mellomløsning er
$O(n \log n)$ , og den naive er $O(n^2)$ .

Du har 25 minutter igjen og to oppgaver du ikke har rørt. Du ser med én gang
den naive $O(n^2)$ -løsningen på denne, og aner at det finnes noe bedre, men vet
ikke hva.

a) Hva gjør du de neste fem minuttene?
b) Hva ville det kostet deg å hoppe over oppgaven helt?

Håndkjøring er en egen ferdighet

Et sted mellom fakta og pseudokode ligger den ferdigheten som overrasker flest:
håndkjøring. Det betyr at du utfører en algoritme steg for steg på papir —
eller i hodet — og oppgir hvordan strukturen ser ut når du er ferdig.

Typiske oppdrag: sett inn seks tall i en min-heap og skriv opp arrayet; sett
inn fem nøkler i en hashtabell med lineær probing og skriv opp hele
tabellen; sett inn i et AVL-tre og oppgi hvor mange rotasjoner det tok.

Det er verdt å si tydelig: å kunne algoritmen er ikke det samme som å kunne
utføre den. De fleste som mister poeng her, vet utmerket godt hva en heap er.
De bommer på ett steg midt i, og fordi oppgaven bare spør etter sluttilstanden,
er hele svaret galt. Derfor har boka egne drillkapitler for nettopp dette, og
derfor er hver eneste sporingstabell i boka regnet ut av et program som
faktisk utfører algoritmen — ikke skrevet fra hukommelsen.

Hva som faktisk kommer

Tabellen under er telt i eksamensarkivet: for hvert tema står det i hvor mange
av de sju settene temaet dukket opp i minst én oppgave.

Tema	Sett	Andel
Kjøretidsanalyse fra kode, og asymptotisk notasjon	7 av 7	100 %
Kjøretids- og teorifakta (sant/usant)	7 av 7	100 %
Sortering: stabilitet, in-place, invarianter, lineær sortering	7 av 7	100 %
Hashing og lukket hashing (lineær probing)	7 av 7	100 %
Grafrepresentasjon og traversering (bredde- og dybdeførst)	7 av 7	100 %
Korteste vei og avstander	7 av 7	100 %
Binære søketrær og tre-rekursjon	6 av 7	86 %
Heap og prioritetskø	6 av 7	86 %
Topologisk sortering og sykeldeteksjon	5 av 7	71 %
Huffman-koding	4–5 av 7	ca. 64 %
Kompleksitetsteori (P og NP)	4 av 7	57 %, fallende
Minimale spenntrær	4 av 7	57 %
Drøft to strategier	4 av 7	57 %, stigende
Sterkt sammenhengende komponenter og komponentgraf	3 av 7	43 %
Balanserte trær (AVL og rød-svart)	3 av 7	43 %
Design av abstrakt datatype	3 av 7	43 %, stigende
Binærsøk og søk i sortert data	3 av 7	43 %

Seks temaer er altså i praksis garantert. Det er der leseplanen din begynner.
Like nyttig er det som ikke kommer. Dynamisk programmering, maks-flyt,
masterteoremet og rekurrensligninger, alle-til-alle korteste vei og stabil
matching er ikke IN2010-pensum. Møter du dem i en generisk algoritmebok,
kan du med god samvittighet la dem ligge. Kjøretid regnes ut i dette faget ved
å telle løkker, ikke ved masterteorem.

Hvor tallene kommer fra

Frekvenstallene i denne boka er telt i UiO-arkivet for IN2010 høst 2018 til
høst 2024: sju oppgavesett med tilhørende offisielle sensorveiledninger.
En sensorveiledning er dokumentet sensorene får utlevert; her inneholder de
løsningsforslag med eksplisitt poengfordeling, og de er hovedkilden til alt
boka sier om hva som gir uttelling.

I tillegg er de tre settene fra forgjengeremnet INF2220 (2015 til 2017) med
løsningsforslag skummet for formhistorikk — de krevde Java og alle
hjelpemidler, og speiler ikke dagens eksamen. Høsten 2020 var eksamen
hjemmeeksamen med alle hjelpemidler på grunn av korona, og er markert særskilt;
den er en fin oppgavebank, men ikke representativ for formen. Prosentene over
gjelder de sju IN2010-settene. Et nytt sett kan endre bildet.

Om innholdet i boka: alle oppgaver, tall, grafer og historier er
nyskrevne. Modellbesvarelsene er skrevet for denne boka — de er ikke ekte
studentbesvarelser, og de er ikke hentet fra en sensorveiledning.
Sensorveiledningene fra en offentlig utdanningsinstitusjon er fritt
tilgjengelige, og analysen bygger lovlig på dem, men ingen oppgavetekst og
intet løsningsforslag er gjengitt ordrett. Boka er heller ikke offisiell eller
tilknyttet UiO, og den lover ingen bestemt karakter.

Sensors seks metaregler

Sensorveiledningene gjentar de samme seks reglene nesten ordrett hvert år. Lær
dem — de er gratis poeng for den som følger dem.

1. Les oppgaveteksten svært nøye. Dette er det mest gjentatte rådet. Svar
på nøyaktig det som spørres om, ikke på det du helst ville blitt spurt om.
2. Oppgi kjøretiden, og la den matche algoritmen du faktisk skrev. Det
trekkes for manglende kjøretid, for feil kjøretid, og for å bruke $n$ uten å
si hva $n$ er. « $n$ er antall noder i grafen» er nok — men det må stå.
3. Lavere kjøretid gir mer poeng. Poengtrappen over.
4. En klar forklaring på vanlig norsk kan gi like mye som pseudokode.
Kravet er at svaret er lett forståelig, entydig og presist — ikke at
syntaksen er pen. Motsatt: en setning sensor ikke forstår etter to
gjennomlesninger, blir ignorert.
5. Oppgi antagelsene dine om representasjon. Du bestemmer selv om grafen er
gitt som nabolister eller nabomatrise, og du kan anta at en node har de
feltene du trenger — men du må skrive hva du antar.
6. Delvis uttelling er regelen. Poengene er fordelt per delmoment, og
hovedmomentet — hvilken algoritme du velger og grunnideen bak — kommer
først. Skriv derfor grunnideen i klartekst før du går løs på detaljene.

Sjangerkortet: de tolv oppgavetypene på én side

Dette er kortet du bør kunne før du går inn i eksamenslokalet. Hver linje er én
oppgavetype, med oppskriften i én setning.

Kode	Oppgavetypen	Oppskrift i én setning	Typisk vekt	Vanligste tabbe
A	Oppvarming	Forklar «algoritme» og «datastruktur» med egne ord, maks fire setninger	2 p, hvert sett	å la den stå blank
B	Kjøretid fra kode	Tell løkkene: nøsting ganges, sekvens legges sammen, halvering gir en $\log$ -faktor	100 % av settene	å telle en konstant indre løkke som $O(n)$
C	Kjøretids- og teorifakta	Sant eller usant, avgjort på faktakunnskap	100 %	å gjette i en skalert blokk
D	Sorteringsegenskaper	Stabil? På stedet? Hva er garantert etter $i$ runder?	100 %	å blande hvilken sortering som plasserer hva
E	Håndkjøring	Utfør operasjonene og oppgi kun sluttilstanden i riktig format	minst 1 per sett, 2 p	å levere treet når det ble spurt om arrayet
F	Matriseavkryssing	Koble egenskap til algoritme rad for rad	4 av 7 sett, 2 p	å bruke samme algoritme i alle rader
G	Tre-algoritme i pseudokode	Skriv en rekursiv prosedyre som beskjærer det den ikke trenger å besøke	86 %	full traversering der beskjæring var mulig
H	Grafalgoritme i pseudokode	Gjenkjenn problemet, kall en pensumalgoritme, oppgi kjøretiden	2–3 per sett	å kjøre algoritmen én gang per startnode
I	Hashing eller søk i pseudokode	Bruk hashtabell eller sortert struktur og få kjøretiden ned	ca. 7 av 7	å gå utenfor tabellen fordi rest-regningen mangler
J	Design av datatype	Kombiner to kjente strukturer, forklar hver operasjon, oppgi kjøretid	3 av 7, stigende	å foreslå én struktur der to trengs
K	Drøft to strategier	Sammenlign kjøretid i verste og forventet tilfelle, og minnebruk; konkludér	4 av 7, stigende	å drøfte uten å definere $n$
L	Kompleksitetsteori	Faktaspørsmål om P og NP, verifikator og reduksjonsretning	4 av 7, fallende	å redusere feil vei

De første seks (A til F) hører hjemme på oppvarmingen og Del 1; de seks siste
(G til L) er Del 2, bortsett fra L, som dukker opp begge steder.

Feilregisteret: de tolv feilene som koster mest

Boka bruker disse numrene gjennomgående. Du trenger ikke pugge dem — de
forklares hver gang de nevnes — men det er nyttig å se dem samlet én gang.

#	Feilen	Forebygges i
#1	Å traversere alt når du kunne hoppet over det meste — for eksempel å gå gjennom hele treet når bare et intervall var etterspurt, eller å kjøre søket én gang per startnode i stedet for én gang totalt	Del 4, Del 5, Del 6 og Del 8
#2	Kvadratisk løsning der en lineær fantes — å regne høyden på nytt i hver node i stedet for å regne den én gang på vei opp	Del 4 og Del 8
#3	Å flytte et element nedover i en heap uten å sjekke om barnet i det hele tatt finnes	Del 4
#4	Å påstå at binærsøk gir deg posisjonen, når den varianten du har lært bare svarer ja eller nei — den må endres først	Del 3
#5	Å bruke en lineær sortering på elementer du bare vet er sammenlignbare; de krever et kjent og begrenset verdiområde	Del 2 og Del 3
#6	Å blande kjøretiden for et søk fra én node med kjøretiden for et søk som dekker hele grafen	Del 5
#7	Å glemme den siste kanten i noe sirkulært — den som lukker runden fra siste tilbake til første	Del 3 og Del 7
#8	Å snu retningen i en reduksjon, og dermed bevise ingenting	Del 7
#9	Å blande søketre-ordenen (venstre mindre, høyre større) med heap-ordenen (forelder mindre enn begge barn)	Del 4
#10	Å bruke $n$ i en drøfting uten å si hva $n$ teller, eller å drøfte uten å nevne kjøretid i det hele tatt	Del 7 og Del 8
#11	Å la en hashtabell-søking gå utenfor tabellen, eller å legge inn en nøkkel to ganger i stedet for å overskrive	Del 3
#12	Å skrive så langt og uklart at sensor ikke forstår algoritmen etter to gjennomlesninger	Del 5 og Del 8

Typiske feil — de som gjøres før du har rørt en algoritme

Dette kapitlet handler om form, og feilene her er formfeil. De koster like mye
som en gal kjøretid.

- Å gjette seg gjennom en skalert sant/usant-blokk. Skaleringen er nettopp
konstruert for at det ikke skal virke: en blokk besvart med myntkast lander
rundt null — på 2023-formelen gir ren gjetting i snitt 2,2 poeng av 32 mulige. Tida er bedre brukt på de faktaene du kan gjøre sikre.
- Å la et kort svar stå blankt. På de vanlige korte svarene teller blankt
akkurat som feil. Skriv det beste du har.
- Å velge en tregere algoritme enn nødvendig på Del 2. Det er ikke en liten
stilfeil — poengtrappen er skrevet inn i rettingen.
- Å tro at gamle sett viser dagens form. Settene fra forgjengeremnet
INF2220 krevde Java og tillot alle hjelpemidler, og hjemmeeksamenen i 2020
hadde alle hjelpemidler. Bruk dem som oppgavebank, ikke som mal.
- Å skrive lang, uklar pseudokode. Sensorveiledningene sier det rett ut: en
setning som ikke er forståelig etter to gjennomlesninger, blir ignorert. Kort
og entydig slår langt og imponerende.
- Å hoppe over oppvarmingen fordi den «bare» er to poeng. To poeng er
omtrent en hel håndkjøringsoppgave, og her er alle rimelige svar riktige.

📝Oppgave 3

(Prioritering.) Du har fem kvelder igjen til eksamen og rekker fem temaer. Under
står sju kandidater med andelen sett de har dukket opp i.

Sortering (100 %), sterkt sammenhengende komponenter (43 %), hashing med
lineær probing (100 %), Huffman-koding (64 %), kjøretid fra kode (100 %),
balanserte trær (43 %), heap-håndkjøring (86 %).

a) Hvilke fem velger du, og hvorfor?
b) Hvorfor er ikke andelen alene nok til å bestemme rekkefølgen?

📝Oppgave 4

(Kildekritikk.) En medstudent har lastet ned et sett fra forgjengeremnet
INF2220 fra 2016 og et IN2010-sett fra høsten 2020, og øver på begge som om de
var vanlige eksamenssett.

a) Hva er problemet med hvert av dem?
b) Hva kan de likevel brukes til?

Hele boka er 42 kapitler: 2 570 minutter med kapittelstoff pluss 785 minutter
prøver, til sammen 3 355 minutter, altså rundt 56 timer. Av dette er 720
minutter de tre firetimers øvingseksamenene.

Anslagene er lesetid. Den som faktisk håndkjører på papir og skriver
pseudokoden selv, bør regne omtrent halvannen gang så lang tid. Det er
brukt tid, ikke bortkastet tid: det er nettopp den treningen eksamen måler.

Hurtigruta — fire til fem dager. Hvis du er sent ute, les i denne
rekkefølgen og hopp over begrepsbankene:

Dag	Innhold	Ca.
1	Dette kapitlet, så hele Del 1 (asymptotikk, løkketelling, faktabanken)	4 t
2	Del 2 (sortering) og Del 3 (hashing, med håndkjøringsdrillen)	5 t
3	Del 4 (søketre, heap og håndkjøringsdrillen) og starten av Del 5 (grafer)	5 t
4	Resten av Del 5, Del 6 (korteste vei) og strategidrillen i Del 8	4 t
5	Én øvingseksamen på tid, uten oppslag, og gjennomgang av det du bommet på	5 t

Deltidsruta — 10 til 12 uker à rundt fem timer. Én del i uka, prøvene til
delen samme uke mens stoffet er ferskt, og de tre øvingseksamenene fordelt på
tre ulike kvelder i de siste tre ukene. Ikke stable dem til slutt: hele
poenget er at du rekker å lære av sett nummer én før du tar sett nummer to.
Og en advarsel som er viktigere her enn i de fleste fag: det er fristende å
lese mye og skrive lite. Det virker ikke i IN2010. Eksamen er hjelpemiddelfri

og krever at du håndkjører strukturer på papir og skriver pseudokode uten
å kunne slå opp. Minst én av øvingseksamenene skal tas på tid, uten en eneste
oppslagsbok, før eksamensdagen.

Det du må kunne uten oppslag

Hva du kan vente deg på neste sett

Ut fra de sju settene er dette et rimelig anslag for et vanlig sett:

Oppvarming: to poeng for å forklare «algoritme» og «datastruktur».

Del 1: én til to oppgaver der du leser kjøretiden ut av kode; to til tre
punkter om sorteringsegenskaper og kjøretidsfakta; én til to håndkjøringer, mest
sannsynlig en heap og en hashtabell, muligens et AVL-tre eller Huffman-koder;
en avkryssingsmatrise om korteste vei; og noen faktapunkter om grafer.

Del 2: to til tre grafalgoritmer i pseudokode, der minst én handler om
komponenter, topologisk sortering, minimalt spenntre eller korteste vei; én
tre-algoritme; én oppgave om hashing eller søk; muligens én designoppgave og én
drøfting. Kompleksitetsteori kan dukke opp på Del 1, eller være helt fraværende.

De siste én til to oppgavene er nesten alltid åpen grafmodellering — en
historie som skal oversettes til en graf og en pensumalgoritme. Det er der
toppkarakterene skilles, og det er derfor boka bruker en hel del på grafer og
et helt drillkapittel på å velge den algoritmen som gir lavest kjøretid.

Leseplanen for resten av boka

Boka har ni deler. Her er de, med tidsanslag og hvilken prioritet de har.

Del	Innhold	Minutter	Prioritet
0	Eksamenskartet (dette kapitlet)	35	les først
1	Asymptotisk analyse og kjøretidsfakta	340	må sitte
2	Sortering og stabilitet	340	må sitte
3	Hashing og søk	345	må sitte
4	Trær: søketrær, balanserte trær og heap	415	må sitte (håndkjøring)
5	Grafer: representasjon, traversering og komponenter	415	må sitte
6	Korteste vei, spenntrær og grådighet	395	bør kunne
7	Datastruktur-design, drøfting og kompleksitetsteori	260	bør kjenne til
8	Eksamenstrening, med tre komplette øvingssett	810	de siste ukene

Rekkefølgen er ikke tilfeldig: hver del bruker den forrige. Kjøretidsapparatet
i Del 1 trengs for hvert eneste svar senere, heapen i Del 4 brukes både av
Huffman og av Prim i Del 6, og grafgrunnlaget i Del 5 er forutsetningen for
hele Del 6.
De tre siste delene er ikke mindre viktige, men de er differensierende
snarere enn garanterte: Del 6 og Del 7 er der du henter de siste poengene når
bunnen sitter. Sitter ikke bunnen, gir Del 1 til Del 5 mer igjen per time.
Neste steg er kap. 1.1, som gir deg selve språket:
hva

O(n \log n)

egentlig betyr, og hva det ikke betyr.

Begrepene du trenger for å lese resten

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

Digital skoleeksamen i Inspera

Eksamensformen i IN2010: fire timer på et eksamenslokale, med svarene skrevet rett inn i UiOs digitale eksamenssystem. Teller 100 prosent, karakter A til F. Også pseudokode skrives inn som tekst — ingenting kan lastes opp håndskrevet.

Hjelpemiddelfri eksamen

At ingen bok, ingen notater og intet oppslagsverk er tillatt. Konsekvensen for lesingen: kjøretider, sorteringsegenskaper og indeksformler må pugges, fordi de ikke kan slås opp underveis.

Oppvarmingen

De to faste innledningsspørsmålene «Hva er en algoritme?» og «Hva er en datastruktur?», maks fire setninger på hver. Verdt 2 poeng, og det finnes ikke noe fasitsvar: alle rimelige svar gir full uttelling. Tapes bare ved å svare blankt eller direkte galt.

Del 1 — den auto-rettede delen

Mange små spørsmål som rettes av maskin: sant/usant, korte uttrykk og små håndkjøringer. Typisk 20 til 35 poeng. Ingen delpoeng og ingen skjønn — svaret er riktig eller galt, og formatet må være som oppgaven ber om.

Del 2 — pseudokode og resonnement

Fem til sju større oppgaver à 8 til 12 poeng der du skal skrive algoritmen selv og begrunne den. Rettes av et menneske, med delpoeng per delmoment. Her avgjøres karakteren, og de siste oppgavene er nesten alltid åpen grafmodellering.

Antigjettings-skalering

2 \cdot \max(n - 16,\ 0)

Poengtrappen

O(n)

Delvis uttelling

At poengene på en Del 2-oppgave er fordelt per delmoment, med algoritmevalget og grunnideen som det tyngste momentet. Praktisk konsekvens: skriv grunnideen i klartekst først, detaljene etterpå.

Sensorveiledning

Dokumentet sensorene får utlevert sammen med settet. I IN2010 inneholder de løsningsforslag med eksplisitt poengfordeling per delmoment, og de er hovedkilden til alt denne boka sier om hva som gir uttelling. Sju stykker foreligger, ett for hvert sett fra 2018 til 2024.

Håndkjøring

Å utføre en algoritme steg for steg for hånd og oppgi hvordan strukturen ser ut til slutt — for eksempel hele hashtabellen eller hele heap-arrayet. Egen ferdighet, egen oppgavetype, minst én per sett, typisk 2 poeng. Å kunne algoritmen er ikke det samme som å kunne utføre den.

Pseudokode i IN2010

Bokas og fagets kodespråk: generisk, selvforklarende kode med et Procedure -hode og linjer for Input: og Output:, skrevet med navn som RemoveMin og DFSVisit . Verken Java, Python eller en bestemt læreboks navnekonvensjon. Arrayindeksering starter på 0.

Kjøretid som matcher algoritmen

n

Antagelser om representasjon

De forutsetningene du selv velger og skriver ned: at grafen er gitt som nabolister, at en node har feltene v.left og v.right, at heapen ligger i et array. Sensor binder seg ikke til én representasjon, men krever at du oppgir hvilken du bruker.

Sjangerkatalogen A til L

Bokas navn på de tolv oppgavetypene som går igjen: A oppvarming, B kjøretid fra kode, C kjøretidsfakta, D sorteringsegenskaper, E håndkjøring, F matriseavkryssing, G tre-algoritme, H grafalgoritme, I hashing og søk, J datatypedesign, K drøfting, L kompleksitetsteori. A til F hører til oppvarmingen og Del 1, G til L til Del 2.

Repetisjon — kapitlet i ti setninger

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 Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.