8.4 Øvingseksamen 2 — datastruktur- og graftungt sett

Forkunnskaper

Settet spenner over hele pensum, men vekten ligger på Del 3 og Del 4.

- Asymptotikk og rekurrenser: kap. 1.1,
kap. 1.2, kap. 1.4 og
kap. 1.5.
- Sortering og utvelgelse: kap. 2.1 og
kap. 2.2.
- Datastrukturer: hauger og Heapsort i
kap. 3.1, binære søketrær i
kap. 3.2, og køer, stakker og disjunkte mengder i
kap. 3.5.
- Grafalgoritmer: traversering og topologisk sortering i
kap. 4.1, minimale spenntrær i
kap. 4.2, korteste vei fra én kilde i
kap. 4.3 og alle-til-alle korteste vei i
kap. 4.4.
- Maksimal flyt: kap. 5.1 og
kap. 5.2.
- Dynamisk programmering: kap. 6.1 og
kap. 6.2.
- NP-teori: kap. 7.1,
kap. 7.2 og kap. 7.3.
- Selve svarformen: kap. 8.1 om hvordan et kortsvar
skal se ut, og designdrillen i kap. 8.2.

Trenger du et mykere første møte med $\lg$ og logaritmeregning, ligger det i
Potenser og logaritmer. Mengdenotasjonen bak $G=(V,E)$ er dekket i
Mengdelære.

Oppgave 1–5: asymptotikk, rekurrens og sortering (~55 min)

Oppgave 1. (Sjanger A — asymptotisk forenkling, altså at du gir det
strammeste uttrykket og ingenting mer.) Oppgi det strammeste $\Theta$-uttrykket
for

$$f(n) = 5n^2\lg n + \frac{n^3}{\lg n} + 9n^2\sqrt{n}.$$

Svar med ett uttrykk.

Oppgave 2. (Sjanger A.) Ranger de fem funksjonene under etter voksende
asymptotisk vekst, og marker eksplisitt hvilke to som vokser like fort:

$$g_1(n) = (\lg n)^5,\qquad g_2(n) = n^{\lg 5},\qquad g_3(n) = 5^{\lg n}, \qquad g_4(n) = n^5,\qquad g_5(n) = 2^{5n}.$$

Skriv svaret som én kjede med $<$ og $=$.

Oppgave 3. (Sjanger B — rekurrensløsning med navngitt metode, altså at du
sier hvilken metode du bruker og hva den gir.) Løs rekurrensen

$$T(1) = 1,\qquad T(n) = T(n-1) + 4n - 3 \quad \text{for } n \ge 2$$

ved iterasjon. Oppgi et eksakt uttrykk for $T(n)$ — ikke en asymptotisk
grense.

Oppgave 4. (Sjanger E — kjøretidskunnskap, altså at du oppgir kjøretiden
direkte og velger mellom $\Theta$ og $O$ med vitende og vilje.) Arrayet
A[1..n] er allerede sortert stigende. Oppgi kjøretiden til Insertion-Sort,
til Merge-Sort og til Heapsort på nettopp dette arrayet.

Oppgave 5. (Sjanger E.) Counting-Sort sorterer $n$ nøkler som alle ligger
i $\{0, 1, \ldots, k\}$. Oppgi kjøretiden, oppgi hva kjøretiden blir når
$k = n^2$, og oppgi i én setning hvorfor Counting-Sort ikke er i strid med
$\Omega(n\lg n)$-grensen for sortering.

— naturlig pausepunkt —

Oppgave 6–10: håndkjøring av haug, søketre, kø og graf (~70 min)

Alle fem oppgavene i denne bolken er sjanger C — håndkjøring, altså at du
utfører algoritmen steg for steg på papir og bare leverer sluttilstanden.
Oppgaveteksten sier hver gang nøyaktig hvilken form sluttilstanden skal ha.
Arrayer indekseres fra 1.

Oppgave 6. Arrayet

$$A[1..8] = \langle 4,\ 13,\ 7,\ 2,\ 19,\ 6,\ 11,\ 5 \rangle$$

er ikke en maks-haug. Kjør Build-Max-Heap(A) på arrayet slik det står, og
deretter den første iterasjonen av sorteringsløkka i Heapsort. Oppgi
arrayet rett etter Build-Max-Heap, og arrayet etter den første iterasjonen
sammen med haugstørrelsen. Begge arrayene oppgis i sin helhet, kommaseparert fra
indeks 1.

Oppgave 7. Nøklene

$$52,\ 31,\ 74,\ 18,\ 44,\ 63,\ 88,\ 27,\ 39,\ 70$$

settes inn i den rekkefølgen, med Tree-Insert, i et binært søketre som starter
tomt. Ingen rebalansering. Oppgi utskriften fra Inorder-Tree-Walk på det
ferdige treet, og oppgi hvilken nøkkel som er forelder til 39.

Oppgave 8. En FIFO-kø ligger i arrayet Q[1..7]. Køen har vært i bruk før,
så cellene inneholder restverdier:

$$Q[1..7] = \langle 41,\ 17,\ 63,\ 33,\ 26,\ 71,\ 55 \rangle, \qquad Q.head = 5,\qquad Q.tail = 5.$$

Utfør denne sekvensen, i rekkefølge: Enqueue(Q, 3), Enqueue(Q, 8),
Enqueue(Q, 12), Enqueue(Q, 5), Dequeue(Q), Enqueue(Q, 21),
Enqueue(Q, 9), Dequeue(Q), Dequeue(Q), Enqueue(Q, 30).

Oppgi hele tabellen Q[1..7] etterpå, inkludert de døde cellene, sammen med
Q.head og Q.tail.

Oppgave 9. Sju målestasjoner i et fiberanlegg er merket A til G. De
mulige gravetraseene mellom dem har disse kostnadene:

radvis, og oppgi rad 3 i forgjengermatrisen $\pi^{(2)}$.
— naturlig pausepunkt —

Oppgave 11–17: definisjoner, ja eller nei, og NP (~65 min)

Oppgave 11. (Sjanger D — definisjon med egne ord, altså én til to presise
setninger med hovedpoenget først.) Definér hva et minimalt spenntre er for en
sammenhengende, urettet, vektet graf $G = (V, E)$.

Oppgave 12. (Sjanger D.) Definér et snitt $(S, T)$ i et flytnett
$G = (V, E)$ med kilde $s$ og sluk $t$, og oppgi hva kapasiteten til snittet
er.

Oppgave 13. (Sjanger D.) Definér en topologisk sortering av en rettet
graf.

Oppgave 14. (Sjanger F — «stemmer dette?», altså at du svarer ja eller nei
først og deretter begrunner med én presis setning.) Vurdér dette utsagnet:

«Dijkstras algoritme gir riktige korteste avstander også når noen kantvekter er
negative, så lenge grafen ikke inneholder noen negativ sykel.»

Stemmer det? Svar ja eller nei, og begrunn.

Oppgave 15. (Sjanger F.) Vurdér dette utsagnet:

«En topologisk sortering av en rettet asyklisk graf får du ved å kjøre et
dybde-først-søk og deretter liste nodene etter stigende oppdagelsestid.»

Stemmer det? Svar ja eller nei, og begrunn.

Oppgave 16. (Sjanger G — reduksjon og NP-argument, altså at du oppgir hva et
resultat beviser og hva det ikke beviser.) Anta at noen i morgen publiserer en
algoritme som løser avgjørelsesvarianten av VERTEX-COVER i polynomisk tid, og
at beviset holder. Oppgi hva som da følger for de øvrige NP-komplette
problemene, og oppgi minst to ting som ikke følger.

Oppgave 17. (Sjanger G.) Et nytt problem, VAKTPOST, er definert slik: gitt
et korridornett modellert som en urettet graf $G = (V, E)$, der nodene er kryss
og kantene er korridorer, og gitt et heltall $k$ — finnes det en mengde på høyst
$k$ kryss slik at hver korridor har en vakt i minst ett av endepunktene sine?

Du skal vise at VAKTPOST er NP-hardt. Oppgi hvilken vei reduksjonen må gå og
hvilket kjent problem du reduserer med, hva reduksjonen beviser, og hva den
ikke beviser.

— naturlig pausepunkt —

Oppgave 18–20: åpen algoritmedesign (~50 min)

De tre siste oppgavene er sjanger H — åpen algoritmedesign, altså
«hvordan vil du gå fram?». Her forventes en kort designskisse, ikke pseudokode
og ikke bevis. Et fullt svar navngir det klassiske problemet du kjenner igjen,
navngir paradigmet, beskriver konstruksjonen presist, sier hvordan du henter ut
selve løsningen og ikke bare tallet, og oppgir kjøretiden med symbolene
definert.

Oppgave 18. Hovtangen sykehjem skal legge nattevaktplanen for en måned. Det
er $m$ nattevakter som alle må dekkes, og $n$ pleiere. Pleier $i$ har oppgitt
hvilke av vaktene hen er kvalifisert og tilgjengelig for, og kan etter avtalen ta
maksimalt $c_i$ nattevakter i måneden. Hver vakt skal dekkes av nøyaktig én
pleier.

Beskriv hvordan du avgjør om alle vaktene kan dekkes, og hvordan du finner en
konkret vaktplan når de kan det. Oppgi kjøretiden.

Oppgave 19. Et vedlikeholdslag kan ta høyst ett oppdrag per dag, og trenger
en full hviledag etter hvert oppdrag — tar laget oppdraget på dag $i$, kan det
ikke ta noe på dag $i+1$. For hver av de $n$ dagene i planperioden er verdien
$v_i > 0$ av dagens oppdrag kjent på forhånd.

Beskriv hvordan du finner hvilke dager laget skal jobbe for å maksimere
samlet verdi. Oppgi kjøretiden.

Oppgave 20. Adgangssystemet på Nordhella teknikkbygg bruker koder på $\ell$
tegn. Systemet har en liste med $n$ gyldige koder. Av sikkerhetshensyn kan en kode
bare byttes ut med en annen gyldig kode som skiller seg fra den forrige i
nøyaktig ett tegn. Gitt to gyldige koder $a$ og $b$: finn den korteste sekvensen
av gyldige koder som starter i $a$, slutter i $b$, og der hvert steg endrer
nøyaktig ett tegn — eller fastslå at ingen slik sekvens finnes.

Beskriv framgangsmåten, og oppgi kjøretiden med $n$ og $\ell$ definert.

Hva skiller de to besvarelsene (~10 min)

Begge kjenner igjen flytproblemet, og begge setter opp nettet riktig. Forskjellen
ligger ikke i lengden — den ligger i tre konkrete ledd.

- Navngi det klassiske problemet i første setning. «Dette er maksimal bipartitt

matching med kapasitet på den ene siden» plasserer hele besvarelsen med én
gang.

Selvdiagnose (~15 min)

Gå gjennom listen med ditt eget besvarelsesark foran deg. Kryss av det du
faktisk gjorde, ikke det du mente å gjøre.

☐ Oppga du bare det som ble etterspurt, uten å legge til en forklaring ingen ba
om?

☐ Er hvert kjøretidssvar det strammeste uttrykket du kan gi — sto det
$\Theta(n^3/\lg n)$ og ikke $O(n^3)$ i oppgave 1?

☐ Står $\Theta$ der garantien er tett, og $O$ der du bare har vist en øvre
grense?

☐ Leverte du hele kø-tabellen i oppgave 8, inkludert de tre døde cellene, og
begge pekerne?

☐ Oppga du haugstørrelsen i oppgave 6, og stoppet du etter den første
iterasjonen?

☐ Er utskriften fra Inorder-Tree-Walk i oppgave 7 sortert stigende? Er den
ikke det, er det en regnefeil, ikke en smakssak.

☐ Merket du de forkastede kantene i oppgave 9, og har spenntreet ditt nøyaktig
$|V| - 1 = 6$ kanter?

☐ Brukte du $\pi$-regelen og ikke $d$-regelen på forgjengermatrisen i oppgave 10?

☐ Sto ordet «nei» først i oppgave 14 og 15, før begrunnelsen?

☐ Går reduksjonen i oppgave 17 fra det kjente vanskelige problemet til det
nye — og sa du hva den ikke beviser?

☐ Rekonstruerte du selve løsningen i oppgave 18, 19 og 20, og ikke bare verdien,
tallet eller lengden?

☐ Nevnte du heltallsteoremet der du modellerte med flyt?

Oppgraderingsmenyen for dette settet

Kommer du til bunns i grunnoppgavene, ligger avstanden opp mot toppen fire
konkrete steder — og alle fire kan trenes:

1. Håndkjøringene skal være feilfrie, ikke omtrentlige. Fem av tjue oppgaver
er sjanger C her. En haug som er nesten riktig, gir mindre enn en haug som er
riktig, og forskjellen er ren nøyaktighet. Kjør dem om igjen på papir til de
sitter.
2. Sluttilstanden skal ha den formen oppgaven ber om. Hele arrayet, hele
tabellen, den etterspurte matrisen, kantene i tilleggsrekkefølge. Riktig
innhold i feil form taper poeng helt unødvendig.
3. Rekonstruksjon er ikke en bonus. På de åpne designoppgavene er «hvilke
dager», «hvilken pleier på hvilken vakt» og «hvilken sekvens» selve
spørsmålet. Verdien alene er et halvt svar.
4. Kjøretiden skal begrunnes i én setning. «$O(mE)$ fordi flyten er høyst
$m$ og hver forøkende sti gir minst 1» er et helt annet svar enn «$O(mE)$».