8.4 Øvingseksamen 3 — grafmodellerings-tungt topp-sett

Forkunnskaper

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 (20 poeng)

---

Oppgave 1 (8 poeng). Sant eller usant?

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

a) En rettet graf har en topologisk rekkefølge hvis og bare hvis den er asyklisk.
b) Et bredde-først-søk finner et minimalt spenntre i en vektet urettet graf.
c) Et spenntre over $|V|$ noder har alltid nøyaktig $|V| - 1$ kanter.
d) Prims og Dijkstras algoritmer har samme asymptotiske kjøretid når begge bruker en binær prioritetskø.
e) Å finne alle sterkt sammenhengende komponenter i en rettet graf kan gjøres i $O(|V| + |E|)$.
f) Hvis et problem ligger i $NP$, kan det ikke ligge i $P$.
g) Å redusere problemet ditt til et kjent NP-komplett problem viser at problemet ditt er NP-hardt.
h) At det finnes en verifikator som sjekker et sertifikat i polynomisk tid, viser at problemet ligger i $NP$.

---

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

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

a)

Procedure R1(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 = 1 to n:
          k = 1
          while k < j:
              k = k * 2
              c = c + 1
  return c

b)

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

---

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

En min-heap ligger i arrayet 4, 9, 7, 21, 13, 12, 18 med indeks fra 0.

a) Utfør RemoveMin to ganger, og oppgi arrayet etter hver av dem.
b) Hvor mange elementer måtte flyttes nedover i den andre operasjonen?

---

Oppgave 4 (5 poeng). Grafalgoritmer: valg og kjøretid.

a) For hver graftype: oppgi den raskeste korrekte algoritmen for korteste vei
fra én kilde.

1. uvektet
2. vektet, alle vekter positive
3. vektet med noen negative kanter, ingen negativ sykel

b) Oppgi kjøretiden for hver av disse to:

1. å finne alle sterkt sammenhengende komponenter
2. Dijkstras algoritme med binær prioritetskø

Del 2 — modellering og design (58 poeng)

For hver oppgave: navngi problemet, oppgi antagelser om representasjon, gi
algoritmen, og oppgi kjøretiden med $|V|$, $|E|$ eller $n$ definert. Pseudokode
og klar forklaring i naturlig språk gir like mye uttelling.

Oppgavene stiger i vanskelighet. Rekker du ikke alt, er det bedre å levere en
treg, korrekt løsning på alle enn en perfekt løsning på halvparten.

---

Oppgave 5 (10 poeng). Et binært tre kalles høydebalansert hvis de to
subtrærne til hver node skiller seg med høyst 1 i høyde. Det er kravet et
AVL-tre oppfyller.

a) Skriv en algoritme som avgjør om et binært tre er høydebalansert. Oppgi
antagelser og kjøretid.
b) En kandidat foreslår: «For hver node regner jeg ut høyden til venstre og
høyre subtre og sammenligner.» Hva er kjøretiden for det, og hvorfor er din
løsning raskere?
c) Et binært søketre er bygget ved å sette inn 40, 20, 60, 10, 30, 50, 5 og 3
i denne rekkefølgen. Er det høydebalansert? Hvis ikke: hvilken node er den
første som bryter kravet?

---

Oppgave 6 (12 poeng). Et regnearkprogram lar hver celle inneholde en formel
som viser til andre celler. Avhengighetene mellom åtte celler er gitt som en
rettet graf, der en kant fra $X$ til $Y$ betyr at $Y$ bruker verdien i $X$:

A1: B2, E3
B2: C4
C4: D1, G5
D1: B2
E3: F2
F2: G5
G5: (ingen)
H1: A1

a) Skriv en algoritme som finner en lovlig beregningsrekkefølge, eller
melder at ingen finnes. Oppgi antagelser og kjøretid.
b) Kjør algoritmen på grafen over. Hva svarer den?
c) Når ingen rekkefølge finnes, vil brukeren vite nøyaktig hvilke celler
som inngår i en sirkulær referanse. Skriv en algoritme for det, og oppgi
kjøretiden.
d) Kjør den på grafen over. Hvilke celler er det?

---

Oppgave 7 (10 poeng). Sju målestasjoner skal knyttes sammen med fiberkabel.
Alle strekninger som kan graves, er kartlagt med en anleggskostnad i
hundretusen kroner. Strekningen mellom $S_1$ og $S_2$ har kostnad 0, fordi det
allerede ligger en kabel der:

Oppgave 8 (10 poeng). En kommune har tolv bydeler forbundet med gangbroer.
Broene er gitt som en urettet graf:

A: B, F, L
B: A, C
C: B, D, G
D: C, E, H
E: D, J
F: A, G
G: C, F, H
H: D, G, I
I: H, J
J: E, I, K
K: J, L
L: A, K

b) En kandidat foreslår å kjøre ett bredde-først-søk fra hver legevakt og ta

minimum for hver bydel. Hva er kjøretiden for det, og når er forskjellen viktig?
c) Kjør algoritmen på grafen over, og oppgi avstanden for hver av de tolv

bydelene.

---
Oppgave 9 (8 poeng). En strømmetjeneste skal holde orden på ventende

avspillingsjobber. Strukturen skal støtte tre operasjoner, alle så raskt som
mulig:
- SettInn(x) — legg til en jobb med prioritet $x$
- FjernMinste() — fjern og returner jobben med lavest prioritet
- FjernStorste() — fjern og returner jobben med høyest prioritet

a) Forklar hvorfor én min-heap ikke er nok.

b) Foreslå en struktur som støtter alle tre. Oppgi kjøretiden per operasjon
og begrunn valget.
c) Finnes det et alternativ som også virker? Sammenlign kort.

---
Oppgave 10 (8 poeng). En graf med $|V|$ noder og $|E|$ kanter skal lagres.
To operasjoner er hyppige:

- ErNabo(u, v) — finnes det en kant mellom $u$ og $v$?
- AlleNaboer(u) — gå gjennom alle naboene til $u$
Sammenlign nabomatrise og nabolister på kjøretid for begge operasjonene
og på minnebruk, og konkludér om når hver representasjon lønner seg. Definér

størrelsene du bruker.

Poengoversikt og selvdiagnose

Selvdiagnose

☐ Oppga du kjøretid overalt, og matcher hver kjøretid den algoritmen du faktisk
skrev?
☐ Definerte du $|V|$, $|E|$ og $n$ der du brukte dem?
☐ I oppgave 5: returnerte traverseringen din høyden oppover, eller regnet du

den ut på nytt i hver node?
☐ I oppgave 6: meldte algoritmen fra om sirkulær referanse, og skilte du mellom
cellene som er i ringen og cellene som bare venter på den?

☐ I oppgave 7: kontrollregnet du at spenntreet har $|V| - 1$ kanter?

☐ I oppgave 8: la du alle kildene i køen før løkken startet?

☐ I oppgave 9: oppga du kjøretiden for hver av de tre operasjonene?
☐ I oppgave 10: er konklusjonen din betinget — sier den når hver representasjon

lønner seg?
☐ Lot du noen oppgave stå blank? Den naive løsningen er alltid verdt poeng, og

trappen bunner aldri i null.
---

Du har nå tatt alle tre settene. Er du usikker på et område, går veien

tilbake gjennom drillkapitlene: kap. 1.3 for kode til O,
kap. 3.3 for hashing, kap. 4.5 for

håndkjøring, kap. 5.5 for grafalgoritmer,
kap. 6.5 for korteste vei og spenntrær, og

kap. 8.1 for selve strategien.

Og et siste råd som er verdt mer enn det ser ut: ta minst ett av de tre settene

om igjen på tid, noen dager før eksamen. Ikke for å se om du husker svarene —

for å kjenne hvor lang tid fire timer faktisk er.