8.3 Øvingseksamen 2 — håndkjørings- og hashing-tungt 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 (35 poeng)

---

Oppgave 1 (10 poeng). Sant eller usant?

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

a) I en hashtabell med lukket hashing og lineær probing skal en nøkkel som allerede ligger i tabellen, overskrives i stedet for å settes inn en gang til.
b) Etter en rehashing til dobbelt så stor tabell kan de gamle indeksene gjenbrukes direkte.
c) Load-faktoren er antall lagrede elementer delt på tabellstørrelsen.
d) Et oppslag i en hashtabell er $O(1)$ i verste tilfelle.
e) Tellesortering kan brukes på hvilke som helst elementer, så lenge de kan sammenlignes.
f) Radix-sortering krever at delsorteringen på hvert siffer er stabil.
g) Haugsortering er stabil.
h) Ethvert AVL-tre kan fargelegges slik at det oppfyller kravene til et rød-svart-tre.
i) En dobbeltrotasjon i et AVL-tre telles som to enkle rotasjoner.
j) I et Huffman-tre får aldri et hyppigere symbol en lengre kode enn et sjeldnere symbol.

I tillegg:

k) Du er sikker på seks av påstandene og gjetter på de fire siste. Hvor mange
poeng kan du forvente?

---

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

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

a)

Procedure Q1(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 = 1
      while j < n:
          j = j * 3
          c = c + 1
  return c

b)

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

---

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

Sett inn 23, 8, 41, 15, 6, 19 og 3 i denne rekkefølgen i en tom min-heap
(array, indeks fra 0).

a) Oppgi arrayet etter innsettingene.
b) Utfør RemoveMin to ganger. Oppgi arrayet etter hver av dem.

---

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

En hashtabell har $N = 11$ plasser og $h(k) = k \bmod 11$, med lineær probing.

Sett inn 34, 45, 23, 34, 10 og 21 i denne rekkefølgen.

a) Oppgi hele tabellen, med _ for tomme plasser.
b) Hvor mange nøkler ligger i tabellen til slutt?
c) Hvilken innsetting brukte wraparound?

---

Oppgave 5 (3 poeng). Håndkjøring av AVL-tre.

Sett inn 9, 18, 27, 36, 45 og 22 i denne rekkefølgen i et tomt AVL-tre.

a) Hvor mange enkle rotasjoner utføres totalt?
b) Hva er rotverdien til slutt?
c) Er resultatet et gyldig AVL-tre?

---

Oppgave 6 (3 poeng). Huffman-koding.

Seks symboler har frekvensene $E$ 21, $T$ 13, $A$ 8, $R$ 5, $S$ 3 og $K$ 2.

a) Oppgi kodelengden til hvert symbol.
b) Hvor mange bits trengs for å kode hele teksten?
c) Hvor mange bits ville en fastlengdekode med like mange bits per symbol
brukt på den samme teksten?

---

Oppgave 7 (4 poeng). Sorteringsegenskaper.

Fyll inn tabellen. Ett poeng per rad.

2. Et veinett med kjøretider i minutter, alle positive.

3. En rettet asyklisk graf av arbeidsprosesser med varighet på hver kant.

b) Oppgi kjøretiden for hver av disse fire, med binær prioritetskø der det er
relevant:

1. dybde-først-søk over hele grafen
2. Kahns topologiske sortering
3. Prims algoritme

4. Bellman-Fords algoritme

Del 2 — pseudokode og resonnement (46 poeng)

Navngi problemet, oppgi antagelser om representasjon, gi algoritmen, og oppgi
kjøretiden med $n$ (eller $|V|$ og $|E|$) definert. Pseudokode og klar tekst gir
like mye uttelling.

---

Oppgave 9 (10 poeng). En avisredaksjon vil finne det første ordet som
gjentas i en artikkel — altså det ordet som først forekommer for andre gang
når du leser teksten fra begynnelsen. Teksten er gitt som et array T med $n$
ord i den rekkefølgen de står.

a) Skriv algoritmen. Oppgi antagelser og kjøretid.
b) En kandidat foreslår å sortere ordene og se etter to like ved siden av
hverandre. Hvorfor løser ikke det oppgaven?
c) Sett opp poengtrappen for oppgaven.

---

Oppgave 10 (8 poeng). Et sortert array A inneholder $n$ måleverdier, og
samme verdi kan forekomme flere ganger. Du skal finne den laveste indeksen
der verdien $x$ står, eller melde at $x$ ikke finnes.

a) Skriv algoritmen, og si eksplisitt hva du har endret i forhold til
binærsøket slik det står i pensum.
b) Oppgi kjøretiden.
c) Kjør algoritmen for hånd på
A = 4, 4, 9, 12, 12, 12, 17, 21, 21, 30 med $x = 12$. Vis lav, hoy og
midt for hvert steg.

---

Oppgave 11 (10 poeng). Et lagersystem lagrer varenumre i et binært søketre.
Når en kunde spør etter et varenummer som ikke finnes, skal systemet foreslå det
nærmeste varenummeret i treet — altså det tallet med minst absolutt
differanse fra det etterspurte.

a) Skriv algoritmen. Oppgi antagelser og kjøretid.
b) En kandidat foreslår å traversere hele treet og holde det beste tallet
underveis. Hva er kjøretiden for det, og hvor mye mindre uttelling gir det?
c) Treet er bygget ved å sette inn 55, 28, 74, 13, 39, 66, 88, 21, 33 og 47.
Hvilke noder besøker algoritmen din når kunden spør etter 42, og hva foreslår
den?

---

Oppgave 12 (10 poeng). Et driftsmiljø har tretten servere. Nettverkskablene
mellom dem er gitt som en urettet graf:

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

Driftsavdelingen vil vite hvor stor den største sammenhengende gruppen av
servere er, altså hvor mange servere som henger sammen i den største klyngen.

a) Skriv algoritmen. Oppgi antagelser og kjøretid.
b) En kandidat foreslår å kjøre et bredde-først-søk fra hver server og se
hvilken som når flest. Hva er kjøretiden for det?
c) Kjør algoritmen på grafen over. Hvor mange grupper finnes, og hvor stor
er den største?

---

Oppgave 13 (8 poeng). To ord er anagram hvis det ene kan skrives om til
det andre ved å stokke om bokstavene. Ordene består av små bokstaver fra a til
z.

Sammenlign to strategier for å avgjøre om to ord av lengde $n$ er anagram:

a) sortér begge ordene og sammenlign dem tegn for tegn
b) tell forekomsten av hver bokstav i begge ordene og sammenlign tellingene

Drøft kjøretid (verste og forventet) og minne, og konkludér om når hver
strategi lønner seg. Definér $n$.

Poengoversikt og selvdiagnose

Selvdiagnose

☐ Oppga du kjøretid på alle fem Del 2-oppgavene, og matcher hver av dem
koden du faktisk skrev?
☐ Sto forbeholdet «forventet» der du skrev $O(1)$ eller $O(n)$ om hashing?
☐ Definerte du både $n$ og $K$ i oppgave 13, og konkluderte du betinget?

Neste steg: kap. 8.4 er det grafmodellerings-tunge

topp-settet. Ta det på en egen kveld.