8.1 DRILL — Del 2-strategi: velg lavest kjøretid (poengtrappen) og skriv presis pseudokode

Den tverrgående Del 2-drillen: for hver oppgave, finn den **lavest mulige** kjøretiden (poengtrappen O(n) > O(n log n) > O(n²)) og skriv svaret som pseudokode ELLER klar naturlig-språk-forklaring som gir full uttelling.

90 min

20 oppgaver

DRILLDel 2-strategivelg lavest kjøretid (poengtrappen)skriv presis pseudokode

Din fremgang i kapitlet

0 / 20 oppgaver

Kapitlets plass i kurset

Bygger på

7.3NP-kompletthet — og hva som IKKE er IN2010-pensum

Brukes videre i

8.2Øvingseksamen 1 — bredt ordinært sett (epoke 3)

Dette er den siste drillen før øvingseksamenene, og den trener én eneste
ferdighet: å finne den raskeste lovlige løsningen på en Del 2-oppgave, og
skrive den ned slik at sensor kan lese den.

Sensorveiledningene sier det samme hvert år: lavere kjøretidskompleksitet er
mer poenggivende. Ofte står trappen skrevet rett ut i veiledningen — en
$O(n)$ -løsning gir full pott på en oppgave, $O(n \log n)$ noe mindre og $O(n^2)$
minst. Det er samme oppgave, samme riktige svar, og likevel forskjellig
uttelling. Å velge algoritme er derfor ikke en stilsak. Det er poeng.

Drillen går på tvers av sjangrene i Del 2:

- sjanger G — tre-algoritme i pseudokode, altså at du skriver en prosedyre
som arbeider på et binærtre og oppgir kjøretiden. Kommer i 6 av 7 sett.
- sjanger H — grafalgoritme i pseudokode, altså at du gjenkjenner det
klassiske grafproblemet i en innpakning og kaller pensumalgoritmen. Kommer i
hvert eneste sett, som regel to eller tre ganger.
- sjanger I — hashing og søk i pseudokode, altså at du velger mellom
hashtabell, sortering og binærsøk. Kommer i alle 7 sett.
- sjanger J — ADT-design, altså at du setter sammen kjente strukturer til en
ny. Kommer i 3 av 7 sett, og andelen stiger.

Prioritet: høyeste. Dette er A- og B-differensieringen i faget. En kandidat
som leverer riktige, men trege løsninger på alle Del 2-oppgavene, lander i
midtsjiktet — og C er en god og vanlig karakter. Men veien derfra og opp går
gjennom nøyaktig denne drillen.

Slik er kapitlet lagt opp: løsningsoppskriften, ett gjennomkjørt
eksamenscase der samme problem løses på tre kjøretidsnivåer med margnotater om
poeng, ett eksempel på en besvarelse skrevet helt uten pseudokode, tolv oppgaver
på eksamensnivå og til slutt en kald bank på åtte oppgaver uten hint.

Om tidsanslaget: de 90 minuttene dekker oppskriften, de to eksemplene og de
tolv oppgavene — omtrent 15 minutter på teorien og seks per oppgave. Den kalde
banken kommer i tillegg, og bør regnes som en egen økt på rundt en time,
siden oppgavene der skal tas på tid uten hint. Det er også et naturlig
pausepunkt etter oppgave 6. Som ellers i boka er anslaget lesetid: skriver du
pseudokoden ut for hånd, skal du regne omtrent halvannen gang så lang tid.

Sist du var her — forkunnskaper i kortform

Denne drillen bruker hele boka, men den hviler på fem resultater. De står ferdig
oppfrisket her, slik at du slipper å bla.

1. Vekstordningen. Denne rekkefølgen er hele poengtrappen i én linje:

$1 < \log n < n < n\log n < n^2 < n^3 < 2^n < n!$

Jo lenger til venstre du kommer med et korrekt svar, jo mer uttelling. Se
kap. 1.1.

2. De fire verktøyene som gjør kvadratisk til lineært.

Verktøy	Gjør	Kjøretid	Kapittel
hash-set / hashmap	medlemskap og telling uten sortering	$O(1)$ forventet per oppslag	kap. 3.2
beskjæring i et søketre	hopper over subtrær som ikke kan inneholde svaret	$O(h + \text{antall treff})$	kap. 4.2
én dybde-først-traversering som returnerer noe	samler informasjon nedenfra i stedet for å regne på nytt per node	$O(n)$	kap. 4.2
forbehandling (sortér eller merk én gang)	flytter arbeid ut av løkken over spørsmålene	$O(n\log n)$ én gang, deretter $O(\log n)$ per spørsmål	kap. 3.4

3. Grafkjøretidene, som må sitte hjelpemiddelfritt. Bredde-først-søk,
dybde-først-søk over hele grafen, topologisk sortering og sterkt sammenhengende
komponenter er alle

O(|V| + |E|)

. Dijkstra og Prim med binær prioritetskø er

O((|V| + |E|)\log|V|)

. Bellman-Ford er

O(|V| \cdot |E|)

. Se
kap. 6.2.

4. Heapen. Insert og RemoveMin er $O(\log n)$ , og det å bygge en heap av
et helt array er $O(n)$ — ikke $O(n \log n)$ . Se
kap. 4.4.
5. Svarformen sensor faktisk krever. Fire ledd, i denne rekkefølgen: navngi
problemet, oppgi antagelser om representasjon, gi algoritmen, oppgi kjøretiden

som matcher den. Se kap. 5.5.

Notasjons- og pseudokodeliste

📜Løsningsoppskriften — fem steg og en trapp

Enhver Del 2-oppgave kan angripes i samme rekkefølge. Steg 1 til 3 tar deg til
en løsning; steg 4 er det som skiller midtsjiktet fra toppsjiktet.

Steg 1 — skriv ned den naive løsningen først, på kladd. Den du kommer på
med én gang: to nøstede løkker, en full traversering, en algoritme kjørt én gang
per spørsmål. Den er nesten alltid riktig, og den er nesten alltid for treg. Men
den forteller deg hva problemet er, og den er verdt poeng hvis du ikke rekker
mer.

Steg 2 — navngi problemet. «Dette er å finne hvem som kan nås fra hvem i en
rettet graf.» «Dette er å slå opp mange ganger i den samme mengden.» «Dette er å
finne de $k$ største.» Navnet peker på verktøyet.

Steg 3 — still spørsmålet: kan dette gjøres raskere? Gå gjennom de fem faste
grepene:

Ser du dette i den naive løsningen?	Grepet	Gevinst
en indre løkke som leter etter et element	hash-set eller hashmap	$O(n^2) \to O(n)$ forventet
en full traversering av et søketre	beskjæring: hopp over subtrær som ikke kan inneholde svaret	$O(n) \to O(h + \text{treff})$
en høyde- eller sum-beregning gjentatt per node	én dybde-først-traversering som returnerer verdien nedenfra	$O(n^2) \to O(n)$
samme algoritme kjørt én gang per kilde eller per spørsmål	forbehandling: kjør den én gang, eventuelt på den reverserte grafen	$O(k \cdot T) \to O(T)$
«finn de $k$ beste» løst ved å sortere alt	min-heap med plass til bare $k$	$O(n \log n) \to O(n \log k)$

Steg 4 — skriv svaret i fire ledd. Dette er sensors faktiske krav, og mangler
ett av leddene, trekkes det:
1. Navngi problemet.
2. Oppgi antagelser om representasjon — nabolister eller nabomatrise, hvilke
felt en node har (v.left, v.right, v.x), om arrayet er sortert.
3. Algoritmen — presis pseudokode eller en klar forklaring i naturlig

språk. Begge gir full uttelling. Kravet er at svaret er entydig og lett å
forstå, ikke at det ser ut som kode.

4. Kjøretiden som matcher algoritmen du faktisk ga, med $n$ (eller $|V|$ og
$|E|$ ) definert — pluss én setning om hvorfor dette er lavest mulig.
Steg 5 — kontrollregn. Les din egen pseudokode og tell løkkene på nytt. Den
vanligste feilen i toppsjiktet er ikke feil algoritme, men riktig algoritme med
feil kjøretid oppgitt under.
Poengtrappen, som ligger under alt sammen: på samme oppgave gir den raskeste
korrekte løsningen full pott, mellomløsningen noe mindre og den naive minst — men
ikke null. Derfor er rekkefølgen på eksamen alltid: skriv den naive hvis du

ikke ser noe bedre, og bruk resten av tiden på å lete etter grepet.

✏️Eksempel 1: Samme oppgave på tre kjøretidsnivåer, med sensor-margnotater

En værtjeneste har lagret $n$ målte lufttrykk i et usortert array A, og
vil vite om to av målingene skiller seg med nøyaktig $x$ enheter. Bare ja
eller nei skal besvares.

Oppgaven er verdt 10 poeng, og sensorveiledningen oppgir trappen: $O(n)$ gir 10,
$O(n \log n)$ gir 6, $O(n^2)$ gir 3.

Løs oppgaven på alle tre nivåene, og oppgi hva som skiller dem.

Bruk A = 8, 3, 14, 1, 11, 6 og $x = 7$ som kontrollsett.

Navngi problemet. Dette er et søk etter et par med gitt differanse i en
usortert mengde. Det er samme familie som «finnes det to like?» og «finnes det to
som summerer til

x

?», og de tre løses med de samme tre verktøyene.

Antagelser om representasjon. A er et array med $n$ tall, indeksert fra 0.
$n$ er antall målinger. Tallene kan gjentas.

---

Nivå 3 — den naive løsningen, $O(n^2)$ , 3 poeng

Procedure FinnesDifferanseNaiv(A, x)
  Input:  array A med n tall (indeks fra 0), tallet x
  Output: true hvis to elementer skiller seg med x, ellers false
  n = A.length
  for i = 0 to n-1:
      for j = i+1 to n-1:
          if |A[i] - A[j]| == x:
              return true
  return false
  Kjoeretid: O(n^2)

Løkketellingen: den ytre løkken går $n$ ganger, den indre høyst $n$ ganger, og
kroppen er konstant. Det gir $O(n^2)$ .

Sensors margnotat: dette er en korrekt løsning, og den gir 3 av 10. Den
taper ikke poeng på å være feil — den taper poeng på å være treg. Lever den
alltid framfor blankt.

---

Nivå 2 — sortér først, $O(n \log n)$ , 6 poeng

Sorterer du arrayet, blir det mulig å bruke to pekere som begge bare går
framover:

Procedure FinnesDifferanseSortert(A, x)
  Input:  array A med n tall, tallet x
  Output: true hvis to elementer skiller seg med x, ellers false
  Sorter(A)                       // flettesortering, O(n log n)
  i = 0
  j = 1
  while j < A.length:
      d = A[j] - A[i]
      if d == x:
          return true
      if d < x:
          j = j + 1               // for liten differanse: flytt den hoeye opp
      else:
          i = i + 1               // for stor differanse: flytt den lave opp
      if i == j:
          j = j + 1
  return false
  Kjoeretid: O(n log n) for sorteringen, O(n) for skanningen  =  O(n log n)

På kontrollsettet blir det sorterte arrayet 1, 3, 6, 8, 11, 14, og pekerne går
slik: $(1, 3)$ gir differanse 2, $(1, 6)$ gir 5, $(1, 8)$ gir 7 — treff.

Sensors margnotat: riktig, raskere, 6 av 10. Merk at sorteringen er det
dyreste leddet: skanningen alene er $O(n)$ . Det er et signal om at hele
sorteringen kan være unødvendig.

---

Nivå 1 — hash-set, $O(n)$ forventet, 10 poeng

Sorteringen var bare et middel for å kunne slå opp raskt. Et hash-set gir
oppslag direkte:

Procedure FinnesDifferanse(A, x)
  Input:  array A med n tall, tallet x
  Output: true hvis to elementer skiller seg med x, ellers false
  S = tomt hash-set
  for hver a i A:
      if Inneholder(S, a - x) or Inneholder(S, a + x):
          return true
      LeggTil(S, a)
  return false
  Kjoeretid: O(n) forventet, O(n^2) verste (hvis alt kolliderer)

Grunnideen i én setning: når du leser tallet a, er den eneste partneren som
kan gi differanse $x$ enten a - x eller a + x — og begge kan slås opp
direkte i settet av alt du har sett før.

Sporing på kontrollsettet:

Steg	Leser `a`	`a - 7` i settet?	`a + 7` i settet?	Settet før steget
1	8	nei	nei	{tomt}
2	3	nei	nei	{8}
3	14	nei	nei	{3, 8}
4	1	nei	ja	{3, 8, 14}

Svaret er ja: 8 og 1 skiller seg med 7. Algoritmen stanser etter fire av seks
elementer.
Sensors margnotat: 10 av 10. To ting løftet svaret hit. For det første er
kjøretiden oppgitt som forventet

O(n)

med det verste tilfellet nevnt —
hashing er ikke

O(1)

garantert, og det å skrive

O(1)

uten forbeholdet

koster. For det andre er $n$ definert eksplisitt som antall målinger.
Hva som skiller nivåene, i én setning hver: nivå 3 leter etter partneren ved

å se på alle andre; nivå 2 gjør leting billig ved å ordne dataene; nivå 1
oppdager at bare to kandidater kan være partner, og slår dem opp direkte.

📝Oppgave 1

(Innstegsoppgave — regn på trappen.) En Del 2-oppgave er verdt 10 poeng, og
sensorveiledningen oppgir trappen: $O(n)$ gir 10 poeng, $O(n \log n)$ gir 6, og
$O(n^2)$ gir 3.

Et sett har fem slike oppgaver med samme trapp.

a) Hva får en kandidat som leverer den naive $O(n^2)$ -løsningen på alle fem?
b) Hva får en kandidat som leverer $O(n \log n)$ på alle fem?
c) Hva får en kandidat som leverer $O(n)$ på tre av dem og blankt på de to
siste?
d) Hva sier sammenligningen av a) og c) om hvordan du bør bruke tiden
i eksamenslokalet?

Naiv-til-optimal-katalogen (~10 min)

Under står de ni parene som har dukket opp i settene boka bygger på. Venstre
kolonne er det du kommer på først; høyre kolonne er det som gir full pott. Lær
parene som par — det er raskere enn å gjenoppdage dem under tidspress.

Problemet	Naivt	Raskt	Grepet
finnes det to like i et usortert array?	$O(n^2)$ dobbel løkke	$O(n)$ forventet	hash-set
skriv ut verdiene i et søketre mellom $a$ og $b$	$O(n)$ full traversering	$O(h + \text{treff})$	beskjæring
hvor lang er den lengste stien i et binærtre?	$O(n^2)$ høyde regnet per node	$O(n)$	én traversering som returnerer høyden
er dette et gyldig binært søketre?	$O(n^2)$ minste og største hentet per node	$O(n)$	send ned et lovlig intervall
hvilket av $k$ utgangspunkt er nærmest målet?	$O(k \cdot (\lvert V \rvert+\lvert E \rvert)\log\lvert V \rvert)$	$O((\lvert V \rvert+\lvert E \rvert)\log\lvert V \rvert)$	én Dijkstra i den reverserte grafen
hvor mange sammenhengende deler har grafen?	$O(\lvert V \rvert \cdot (\lvert V \rvert+\lvert E \rvert))$ traversering fra hver node	$O(\lvert V \rvert + \lvert E \rvert)$	én dybde-først over alle komponenter
finnes det en lovlig rekkefølge under avhengigheter?	$O(n!)$ prøv alle rekkefølger	$O(\lvert V \rvert + \lvert E \rvert)$	topologisk sortering
hva er de $k$ største av $n$ tall?	$O(n \log n)$ sortér alt	$O(n \log k)$	min-heap med plass til $k$
$m$ spørsmål mot det samme datasettet	$O(n \cdot m)$	$O(n\log n + m\log n)$	forbehandling: sortér én gang

Legg merke til det siste paret. Det er det minst kjente, og det er det som
oftest skiller en 8-poengsbesvarelse fra en 12-poengs: når oppgaven har både
data og spørsmål, skal arbeidet flyttes ut av spørsmålsløkken.

✏️Eksempel 2: En besvarelse helt uten pseudokode — som gir full uttelling

En hjemmetjeneste har seks utrykningsbiler som står parkert på hver sin adresse
i et veinett. Veiene er enveiskjørte, og hver vei har en kjøretid i minutter.
Det kommer inn et oppdrag på en bestemt adresse $t$ .

Skriv en algoritme som finner hvilken bil som når fram raskest, og oppgi
kjøretiden. Oppgaven er verdt 10 poeng.

Besvar oppgaven uten å skrive én linje pseudokode.

Sensorveiledningene sier det rett ut: en klar forklaring i naturlig språk kan gi
like mye som — eller mer enn — rotete pseudokode. Kravet er at svaret er «lett
forståelig, entydig og presist», ikke at det ser ut som kode. Under står en
besvarelse som oppfyller kravet. Den er skrevet for denne boka, ikke hentet
fra noe reelt sett.

---

Problemet. Dette er korteste vei fra én kilde i en rettet, vektet graf med
ikke-negative vekter — men med flere mulige startpunkt og ett mål, som er
speilbildet av det Dijkstra løser.

Antagelser om representasjon. Veinettet er en rettet graf $G = (V, E)$
gitt som nabolister. Hvert veistykke (u, v) har en vekt w(u, v) som er
kjøretiden i minutter, og alle vektene er positive. Nodene er veikryss og
adresser. $U$ er mengden av de seks bil-adressene, og $t$ er oppdragsadressen.
Jeg lar $|V|$ være antall kryss og $|E|$ antall veistykker.

Algoritmen. Jeg snur alle veiene, slik at hvert veistykke peker motsatt
vei av det det gjør i virkeligheten. I den snudde grafen kjører jeg Dijkstra
én gang, med oppdragsadressen $t$ som utgangspunkt. Resultatet er en
avstandstabell som for hver node oppgir korteste kjøretid fra den noden fram
til $t$ i det virkelige veinettet — for en vei fra $v$ til $t$ i virkeligheten
er nøyaktig en vei fra $t$ til $v$ i den snudde grafen, og den har samme
lengde. Til slutt leser jeg av de seks tallene som hører til bil-adressene, og
velger den minste. Det er den raskeste bilen, og tallet er kjøretiden dens.

Kjøretid. Å snu grafen koster $O(|V| + |E|)$ , siden hver kant flyttes én
gang. Dijkstra med binær prioritetskø er $O((|V| + |E|)\log|V|)$ , og avlesningen
til slutt er $O(|U|)$ , altså konstant her. Totalt blir det
$O((|V| + |E|)\log|V|)$ .

Hvorfor dette er lavest mulig. Den nærliggende løsningen er å kjøre
Dijkstra fra hver av de seks bilene og sammenligne. Det gir seks kjøringer,
altså $O(|U| \cdot (|V| + |E|)\log|V|)$ . Snuingen koster mindre enn én
Dijkstra-kjøring, så én kjøring i den snudde grafen er strengt raskere så
snart det er mer enn én bil.

---

Hvorfor dette gir full pott: alle fire leddene er der. Problemet er navngitt,
antagelsene er oppgitt, algoritmen er beskrevet så presist at den kan
implementeres direkte, og kjøretiden er regnet ut ledd for ledd og satt opp mot
alternativet. Ordet «Dijkstra» gjør resten av jobben — det er en pensumalgoritme,
og du skal ikke skrive den ut på nytt.

Og en advarsel som hører til: naturlig språk gir bare full uttelling når det
er entydig. «Jeg snur grafen og kjører Dijkstra» uten å si fra hvor, uten
antagelser og uten kjøretid, er ikke en besvarelse — det er en overskrift.
Sensorveiledningene formulerer terskelen slik: en setning man ikke forstår etter
to gjennomlesninger, blir ignorert (felle #12 — uklar eller for lang
pseudokode).

📝Oppgave 2

Sjanger B og valg av…

Under står en prosedyre en kandidat leverte på
Del 2.

Procedure TellUnike(A)
  Input:  array A med n tall, indeks fra 0
  Output: antall forskjellige verdier i A
  n = A.length
  antall = 0
  for i = 0 to n-1:
      ny = true
      for j = 0 to i-1:
          if A[j] == A[i]:
              ny = false
      if ny:
          antall = antall + 1
  return antall

a) Oppgi kjøretiden ved løkketelling.
b) Hvilket av grepene i løsningsoppskriften passer her?
c) Hvilken kjøretid gir grepet?

📝Oppgave 3

Eksamensnivå, sjanger G

Et binært søketre er bygget ved å sette
inn 50, 30, 70, 20, 40, 60, 80, 35 og 45 i denne rekkefølgen.

En kandidat skal telle hvor mange verdier i treet som er mindre enn et gitt tall
$x$ , og leverer dette:

Procedure TellMindreNaiv(v, x)
  Input:  rotnoden v i et binaert soeketre, tallet x
  Output: antall verdier i treet som er mindre enn x
  if v == null:
      return 0
  eget = 0
  if v.x < x:
      eget = 1
  return eget + TellMindreNaiv(v.left, x) + TellMindreNaiv(v.right, x)

a) Hva er kjøretiden til denne, og hvor mange noder besøker den for
$x = 38$ ?
b) Skriv en raskere prosedyre. Oppgi antagelser og kjøretid.
c) Hvor mange noder besøker din prosedyre for $x = 38$ , og hva er svaret?

📝Oppgave 4

Eksamensnivå, sjanger G

En kandidat skal finne hvor mange noder i et
binærtre som har like høye subtrær — altså noder der venstre og høyre subtre
har nøyaktig samme høyde. Kandidaten leverer:

Procedure TellBalanserteNaiv(v)
  Input:  rotnoden v i et binaert tre
  Output: antall noder med like hoeye subtraer
  if v == null:
      return 0
  eget = 0
  if Hoeyde(v.left) == Hoeyde(v.right):
      eget = 1
  return eget + TellBalanserteNaiv(v.left) + TellBalanserteNaiv(v.right)

Hoeyde(v) er den vanlige rekursive høydeberegningen, som besøker hele
subtreet.

a) Hva er kjøretiden, og hvorfor?
b) Skriv en $O(n)$ -løsning.
c) Hva ville de to løsningene fått på en oppgave med trappen 8 poeng for
$O(n)$ og 4 for $O(n^2)$ ?

📝Oppgave 5

Eksamensnivå, sjanger I

Et arkiv har to
usorterte lister: A med $n$ arkivnumre som er digitalisert, og B med $m$
arkivnumre som er etterspurt. Du skal finne hvor mange numre som står i begge
listene.

a) Skriv den naive løsningen og oppgi kjøretiden.
b) Skriv den raskeste løsningen du kjenner. Oppgi antagelser og kjøretid.
c) En medstudent foreslår å sortere begge listene med radix sort først, fordi
arkivnumre er tall, og deretter flette dem. Er det lov?

📝Oppgave 6

Eksamensnivå, sjanger I

Et sortert array A med $n$ måleverdier skal
brukes til å svare på $m$ spørsmål av formen «finnes verdien $x$ ?».

En kandidat leverer en lineær skann per spørsmål, og skriver: «Jeg bruker
binærsøk, som returnerer indeksen til $x$ i $O(\log n)$ .»

a) Hva er kjøretiden for den løsningen kandidaten faktisk leverte?
b) Hva er kjøretiden for den kandidaten sier at hun bruker?
c) Hva er galt med formuleringen om binærsøk, og hvordan skal den skrives?

Du har nå vært gjennom de tre grepene som gjør noe kvadratisk til noe lineært:
hash-settet, beskjæringen og den ene traverseringen som returnerer verdien
nedenfra.

De seks neste oppgavene handler om grafer, forbehandling og om å skrive svaret
slik at det gir uttelling. Ta gjerne en pause her — kapitlet er bygget for to
økter, og den kalde banken til slutt er en tredje.

📝Oppgave 7

Eksamensnivå, sjanger H

Et kraftselskap har fem
beredskapslagre plassert rundt i et enveiskjørt veinett med kjøretider på hvert
veistykke. Når det meldes en feil på en bestemt trafo, skal systemet finne
hvilket lager som er nærmest trafoen.

En kandidat foreslår: «Kjør Dijkstra fra hvert av de fem lagrene, og se hvem som
får lavest avstand til trafoen.»

a) Hva er kjøretiden for kandidatens forslag?
b) Beskriv en raskere løsning. Oppgi antagelser og kjøretid.
c) Hvorfor virker den raskere løsningen?
d) Feilen kan komme på hvilken som helst trafo, og det er tusenvis av dem.
Endrer det svaret?

📝Oppgave 8

Eksamensnivå, sjanger H

Et sosialt nettverk er en urettet graf der nodene er
brukere og kantene er vennskap. Systemet skal svare på mange spørsmål av formen
«henger bruker $u$ og bruker $v$ sammen gjennom en kjede av venner?». Grafen
endrer seg ikke mellom spørsmålene.

En kandidat foreslår: «For hvert spørsmål kjører jeg et bredde-først-søk fra $u$
og ser om jeg treffer $v$ .»

a) Hva koster kandidatens forslag for $m$ spørsmål?
b) Skriv en raskere løsning. Oppgi antagelser og kjøretid.
c) Hvilket av grepene i løsningsoppskriften er dette?

📝Oppgave 9

Eksamensnivå, sjanger H

Et byggeprosjekt har $n$ arbeidsoppgaver. Noen
oppgaver må gjøres før andre, og kravene er gitt som en rettet graf: en kant fra
$X$ til $Y$ betyr at $X$ må være ferdig før $Y$ kan begynne.

En kandidat skriver: «Jeg prøver alle mulige rekkefølger av de $n$ oppgavene, og
sjekker for hver rekkefølge om alle kravene er oppfylt. Finner jeg en som
holder, skriver jeg den ut; ellers melder jeg at det er umulig.»

a) Hva er kjøretiden for kandidatens forslag?
b) Skriv den raskeste løsningen. Oppgi antagelser og kjøretid.
c) Hva skal algoritmen svare når det ikke finnes noen lovlig rekkefølge, og
hvordan oppdager den det?

📝Oppgave 10

Eksamensnivå, sjanger J

En strømmetjeneste registrerer $n$
avspillinger i døgnet og skal hver morgen finne de $k$ mest spilte låtene,
der $k$ er lite (typisk 10) og $n$ er stort (typisk mange millioner).

En kandidat foreslår å sortere hele lista og ta de $k$ siste.

a) Hva er kjøretiden for kandidatens forslag?
b) Beskriv en raskere løsning, og oppgi kjøretid og minnebruk.
c) Kjør din løsning for hånd på A = 12, 45, 7, 33, 21, 58, 9, 40 med
$k = 3$ , og oppgi innholdet i strukturen etter hvert steg.
d) Når lønner kandidatens forslag seg likevel?

📝Oppgave 11

Eksamensnivå, sjanger K

En kandidat har fått denne
oppgaven:

En nettbutikk skal telle hvor mange ganger hver varekode forekommer i
salgsloggen. Sammenlign (a) et hashmap fra varekode til antall og (b) et
tellearray indeksert på varekode. Drøft kjøretid og minne, og konkludér.

Kandidaten svarer:

«Hashmap er raskest fordi oppslag er $O(1)$ . Tellearrayet blir kjempestort
hvis det er mange varekoder. Jeg velger hashmap.»

a) Hvilke tre trekk gir denne besvarelsen?
b) Skriv en besvarelse som gir full uttelling.

📝Oppgave 12

Eksamensnivå, hele Del…

En kommune har en logg med $n$ hendelser.
Hver hendelse har et tidspunkt (et heltall) og er lagret usortert. Loggen
endres ikke.

Innbyggerne stiller $m$ spørsmål av formen «hvor mange hendelser skjedde før
tidspunkt $t$ ?».

a) Skriv den naive løsningen og oppgi kjøretiden.
b) Skriv den raskeste løsningen du kjenner. Oppgi antagelser og kjøretid.
c) For hvilke verdier av $m$ lønner det seg å forbehandle?
d) Sett opp poengtrappen for oppgaven slik du tror sensor ville gjort det,
og begrunn rekkefølgen.

Typiske feil

Fem feil koster poeng i nettopp denne drillen. De fire første er hentet fra
bokas feilregister; koden i parentes er nummeret registeret bruker.

1. Å levere en korrekt, men unødvendig treg løsning uten å lete videre
(felle #1 — full eller naiv gjennomgang der beskjæring var mulig). Dette er
den dyreste feilen i faget, og den er usynlig: besvarelsen ser riktig ut, fordi
den er riktig. Kontrollspørsmålet «kan dette gjøres raskere?» skal stilles på
hver eneste Del 2-oppgave, hver gang.

2. Å oppgi en kjøretid som ikke matcher koden du faktisk skrev. Det trekkes
både for manglende og for feil kompleksitet. Den vanligste varianten er å skrive
ned den kjøretiden du ville hatt med den beste algoritmen, og deretter levere
en annen.

3. Å bruke $n$ uten å definere det (felle #10 — n uten definisjon, og
drøfting uten referanse til O-notasjon). I en oppgave med både data og spørsmål
finnes det minst to størrelser, og « $O(n)$ » er meningsløst før du sier hvilken
du mener.

4. Å skrive lang, uklar pseudokode (felle #12 — en setning man ikke
forstår etter to gjennomlesninger, blir ignorert). Fem klare linjer med en
setning som forklarer grunnideen, slår tjue linjer som må tydes. Har du dårlig
tid, skriv i naturlig språk i stedet — det gir full uttelling når det er presist.

5. Å hoppe over den naive løsningen helt. Ser du ikke grepet, skal du levere
det du har. Trappen bunner ikke i null: den naive løsningen gir alltid noen
poeng, og en blank oppgave gir ingen.

Kald bank — uten hint

Din fremgang

0 / 8 oppgaver

Begrepsbank

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

Poengtrappen

O(n)

Del 2-svarformen — fire ledd

n

Kontrollspørsmålet «kan dette gjøres raskere?»

k

Hash-settet som lineær-tid-verktøy

O(n^2)

Beskjæring i et søketre

O(n)

Én traversering som returnerer verdien nedenfra

O(n^2)

Forbehandling

O(n \cdot m)

Reversert-graf-trikset

O(|V| + |E|)

Min-heap med plass til bare k

k

Å definere n

n

Repetisjon — Del 2-strategien på ett kort

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.