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

Forkunnskaper

Settet dekker hele boka. Er du usikker på et område mens du retter, går du hit:

Oppvarming (2 poeng)

Oppgave 0. Svar med høyst fire setninger på hvert punkt.

a) Hva er en algoritme?
b) Hva er en datastruktur?

Del 1 — auto-rettet (28 poeng)

Del 1 rettes maskinelt. Svarene er sant/usant, korte uttrykk, tabeller og
avkryssinger. Ingen begrunnelse kreves — men skriv gjerne én for deg selv, slik
at du kan sjekke om du kunne det eller gjettet.

---

Oppgave 1 (12 poeng). Sant eller usant?

Antigjettings-skalering: blokken har 12 påstander, og poengsummen regnes som
$2 \cdot \max(n - 6,\ 0)$, der $n$ er antall riktige.

a) Flettesortering er $O(n \log n)$ også i verste tilfelle.
b) Kvikksortering er $O(n \log n)$ i verste tilfelle.
c) Et vilkårlig array med $n$ elementer kan gjøres om til en heap i $O(n)$.
d) Du kan finne det største elementet i en min-heap med $n$ elementer i $O(\log n)$.
e) Innsettingssortering er stabil.
f) Utvalgssortering garanterer færrest mulige bytter av alle de tre kvadratiske sorteringene.
g) Bredde-først-søk finner korteste vei målt i antall kanter i en uvektet graf.
h) Et dybde-først-søk startet i én node er $O(|V| + |E|)$.
i) Dijkstras algoritme kan brukes på grafer med negative kantvekter, så lenge det ikke finnes en negativ sykel.
j) Komponentgrafen til en rettet graf er alltid asyklisk.
k) $P \subseteq NP$.
l) Det er bevist at $P \neq NP$.

I tillegg, som en del av samme oppgave:

m) Du kan tolv av påstandene sikkert og treffer ni riktige. Hvor mange poeng
gir blokken? Og hvor mange riktige må du minst ha for å få ett eneste poeng?

---

Oppgave 2 (6 poeng). Oppgi kjøretiden.

Svar med det strammeste $O$-uttrykket. To poeng per delspørsmål.

a)

Procedure P1(A)
  Input:  array A med n tall, indeks fra 0
  Output: en telling
  n = A.length
  c = 0
  for i = 0 to n-1:
      for j = 0 to n-1:
          for k = 0 to 49:
              c = c + 1
  return c

b)

Procedure P2(A)
  Input:  array A med n tall, indeks fra 0
  Output: en telling
  n = A.length
  c = 0
  for i = 0 to n-1:
      j = n
      while j > 1:
          j = j / 2
          c = c + 1
  for i = 0 to n-1:
      for j = 0 to n-1:
          c = c + 1
  return c

c)

Procedure P3(A)
  Input:  array A med n tall, indeks fra 0
  Output: en telling
  n = A.length
  c = 0
  for i = 0 to n-1:
      for j = 0 to i-1:
          for k = 0 to j-1:
              c = c + 1
  return c

---

Oppgave 3 (2 poeng). Håndkjøring av min-heap.

Sett inn 31, 17, 26, 9, 40, 12 og 5 i denne rekkefølgen i en tom min-heap som
ligger i et array med indeks fra 0.

a) Oppgi arrayet etter innsettingene.
b) Utfør deretter RemoveMin én gang, og oppgi arrayet etterpå.

---

Oppgave 4 (2 poeng). Håndkjøring av lineær probing.

En hashtabell har $N = 13$ plasser og hashfunksjonen $h(k) = k \bmod 13$.
Kollisjoner løses med lineær probing.

Sett inn 25, 38, 12, 7, 20 og 51 i denne rekkefølgen, og oppgi hele tabellen.
Bruk _ for tomme plasser.

---

Oppgave 5 (4 poeng). Korteste vei fra én kilde.

For hver graftype: oppgi den raskeste korrekte algoritmen og dens kjøretid.

A: B
B: A, C, E
C: B, D
D: C
E: B, F
F: E

Graf 2

P: Q, R
Q: P, R
R: P, Q, S
S: R, T
T: S

Graf 3

X: Y
Y: X
Z: W
W: Z

Kryss av for hver graf: er den sammenhengende? inneholder den en sykel?

er den et tre?

Del 2 — pseudokode og resonnement (52 poeng)

Her skal du konstruere algoritmen og skrive den ned. Pseudokode og klar
forklaring i naturlig språk gir like mye uttelling; kravet er at svaret er
entydig og presist nok til at algoritmen kan implementeres direkte fra det.

For hver oppgave: navngi problemet, oppgi antagelsene dine om representasjon,
gi algoritmen, og oppgi kjøretiden — med $n$ (eller $|V|$ og $|E|$) definert.

---

Oppgave 7 (8 poeng). Et biblioteksystem lagrer utlånsnumre i et binært
søketre. Systemet skal finne det nest største utlånsnummeret i treet.

a) Skriv en algoritme som finner det nest største tallet. Oppgi antagelser
og kjøretid.
b) En kandidat foreslår å skrive ut treet i sortert rekkefølge og ta det
nest siste tallet. Hva er kjøretiden for det, og hvorfor gir din løsning mer
uttelling?
c) Treet er bygget ved å sette inn 46, 22, 71, 15, 34, 58, 84 og 63 i denne
rekkefølgen. Hva svarer algoritmen din?

---

Oppgave 8 (8 poeng). En billettkontroll har logget $n$ billettnumre i et
usortert array. Et nummer regnes som misbrukt hvis det forekommer mer enn
to ganger.

Skriv en algoritme som avgjør om minst ett nummer er misbrukt. Oppgi antagelser
og kjøretid, og forklar hvorfor kjøretiden er lavest mulig.

---

Oppgave 9 (8 poeng). En urettet graf beskriver et rørnett mellom
pumpestasjoner.

a) Skriv en algoritme som avgjør om nettet er et tre. Oppgi antagelser og
kjøretid.
b) Hvorfor er det ikke nok å telle kantene?

---

Oppgave 10 (10 poeng). Et monteringsverksted har ni arbeidstrinn.
Avhengighetene er gitt som en rettet graf, der en kant fra $X$ til $Y$ betyr at
$X$ må være ferdig før $Y$ kan begynne:

A: C, D
B: D
C: E, I
D: E, F
E: G
F: G
G: H
H: (ingen)
I: H

Hvert trinn tar nøyaktig én dag, og ubegrenset mange trinn kan gjøres samtidig
så lenge avhengighetene er oppfylt.

a) Skriv en algoritme som finner hvor mange dager hele monteringen minst
tar. Oppgi antagelser og kjøretid.
b) En kandidat foreslår å kjøre et dybde-først-søk fra hver node og ta den
lengste stien som finnes. Hva er kjøretiden for det?
c) Kjør din algoritme for hånd på grafen over, og oppgi svaret.

---

Oppgave 11 (10 poeng). Et intranett har ni sider. En kant fra $X$ til $Y$
betyr at side $X$ lenker til side $Y$; lenkene er enveis:

A: B
B: C
C: A, D
D: E
E: D, F
F: G
G: F
H: A, I
I: D, H

Redaksjonen vil vite om det finnes minst én side som kan nås fra alle de
andre, slik at den kan brukes som felles bunnpunkt.

a) Skriv en algoritme som avgjør dette, og som oppgir sidene hvis de finnes.
Oppgi antagelser og kjøretid.
b) Begrunn hvorfor kriteriet du bruker, er riktig.
c) Kjør algoritmen på grafen over og oppgi svaret.

---

Oppgave 12 (8 poeng). Et medlemsregister med $n$ medlemmer skal støtte to
operasjoner:

- Finnes(id) — er dette medlemsnummeret registrert?
- SortertListe() — skriv ut alle medlemsnumrene i stigende rekkefølge.

Sammenlign to strategier på kjøretid (verste og forventet) og minne, og
konkludér om når hver av dem lønner seg:

a) et hashmap fra medlemsnummer til medlemsdata
b) et balansert binært søketre (AVL) ordnet på medlemsnummer

Definér $n$.

Poengoversikt og selvdiagnose

Selvdiagnose

☐ Oppga du kjøretid på hver Del 2-oppgave?
☐ Matcher hver kjøretid den algoritmen du faktisk skrev — ikke den du hadde
tenkt å skrive?
☐ Definerte du hva $n$ (eller $|V|$ og $|E|$) er, hver gang du brukte det?
☐ Skrev du ned antagelsene dine om representasjon, minst én linje per oppgave?

☐ Stilte du spørsmålet «kan dette gjøres raskere?» på alle de seks

Del 2-oppgavene, eller leverte du den første løsningen du kom på?

☐ Meldte algoritmen din fra om sykel i oppgave 10, i stedet for å levere et tall

uansett?
☐ Er det noen oppgave du lot stå helt blank? (Den naive løsningen er alltid

verdt poeng.)
Neste steg: kap. 8.3 er et håndkjørings- og

hashing-tungt sett, og kap. 8.4 er et grafmodellerings-tungt

topp-sett. Ta dem på hver sin kveld, ikke etter hverandre.