8.5 Øvingseksamen 3 — designtungt topp-sett

Forkunnskaper

Dette settet trekker på hele boka. De delene som veier tyngst:

- kap. 5.3 og kap. 8.2 —
flytmodellering og designoppskriften med de fem leddene.
- kap. 6.3 — DP-design og rekonstruksjon.
- kap. 7.2 og kap. 7.4 —
reduksjonsretning og NP-argumenter.
- kap. 6.5 — Gale-Shapley og begge orienteringene.
- kap. 1.2, kap. 1.5,
kap. 2.4, kap. 3.3 og
kap. 4.5 — grunnoppgavene.

Har du ikke tatt kap. 8.3 og
kap. 8.4 ennå, ta dem først. Dette settet er det
vanskeligste av de tre.

Oppgave 1–6: asymptotikk, rekurrens og kjøretid (~60 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) = 7n^2\lg^3 n + 4n^{5/2} + \frac{n^3}{\lg^2 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) = n^{\lg 3},\qquad g_2(n) = 3^{\lg n},\qquad g_3(n) = n\lg^2 n, \qquad g_4(n) = 2^{\sqrt{n}},\qquad g_5(n) = n!\,.$$

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) = 2,\qquad T(n) = T(n-1) + 3n - 1 \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.) Du kjører først
Insertion-Sort på hele arrayet, og deretter Merge-Sort på resultatet. Oppgi
total kjøretid i verste tilfelle, og oppgi hva totalen ville blitt i motsatt
rekkefølge. Begrunn hver av dem på én linje.

Oppgave 5. (Sjanger E.) Oppgi kjøretiden til Build-Max-Heap, til
Heapsort og til Randomized-Select i verste tilfelle. For hver: si om
grensen er tett eller bare øvre.

Oppgave 6. (Sjanger E.) Radix-Sort sorterer $n$ nøkler med $d$ siffer
hver, i et tallsystem med grunntall $k$. Oppgi kjøretiden, oppgi hvilken
egenskap delsorteringen må ha, og oppgi under hvilken betingelse Radix-Sort
er asymptotisk raskere enn Merge-Sort.

— naturlig pausepunkt —

Oppgave 7–12: håndkjøring, definisjoner og ja/nei (~65 min)

Oppgave 7. (Sjanger C — håndkjøring, altså at du utfører algoritmen steg
for steg og oppgir bare sluttilstanden.) Sett inn nøklene

54, 29, 73, 16, 41, 66, 88, 35

i denne rekkefølgen i et tomt binært søketre. Oppgi
Inorder-Tree-Walk-utskriften og treets høyde.

Oppgave 8. (Sjanger C.) Et flytnett har nodene $s$, $a$, $b$, $c$, $d$, $t$
og kapasitetene

c(s,a) = 11    c(s,b) = 7     c(a,b) = 3    c(a,c) = 6
c(b,d) = 9     c(c,t) = 8     c(c,d) = 4    c(d,t) = 10

Kjør Edmonds-Karp fra nullflyten, med naboene i alfabetisk rekkefølge. Oppgi
maksimal flytverdi og et min-snitt.

Oppgave 9. (Sjanger D — definisjon med egne ord, altså én presis setning med
hovedpoenget først.) Definér restkapasitet og ryggkant, og forklar med
én setning hvorfor ryggkanten er nødvendig.

Oppgave 10. (Sjanger D.) Definér et blokkerende par, og forklar hva det
betyr at en matching er stabil.

Oppgave 11. (Sjanger F — «stemmer dette?», altså at du svarer ja eller nei
først og deretter gir én presis setning.) En kandidat skriver: «Vi bruker
Dijkstra fordi nettet har noen strekninger med negativ kostnad, og
Dijkstra er raskest.» Stemmer resonnementet?

Oppgave 12. (Sjanger F.) Stemmer dette: «Ford-Fulkerson er
pseudopolynomisk, og maks-flyt er derfor sannsynligvis NP-hardt.»

— naturlig pausepunkt —

Oppgave 13–15: reduksjoner og NP-argumenter (~35 min)

Oppgave 13. (Sjanger G — reduksjon og argument om vanskelighet, altså at du
sier hvilken vei argumentet går, hva det viser, og hva det ikke viser.) Du
har vist 3-CNF-SAT $\le_p$ RUTEPLAN.

a) Hva forteller det om RUTEPLAN?
b) Hva mangler for at RUTEPLAN skal være NP-komplett, og hvordan vises
det?

Oppgave 14. (Sjanger G.) En kandidat skriver: «Problemet mitt LAGERFLYT kan
oversettes til SUBSET-SUM i lineær tid, og SUBSET-SUM er NP-komplett. Altså er
LAGERFLYT NP-hardt.» Er argumentet gyldig? Svar, og forklar nøyaktig hva som er
galt.

Oppgave 15. (Sjanger G.) Et forskningsmiljø kunngjør at de har funnet en
algoritme som løser VERTEX-COVER i $O(n^7)$.

a) Hvilken konsekvens har det, hvis kunngjøringen stemmer?
b) Hva ville den samme kunngjøringen om et NP-hardt, men ikke
NP-komplett problem gitt?

Oppgave 16–20: åpen algoritmedesign (~80 min)

Alle fem oppgavene besvares med en kort designskisse: hvilket klassisk
problem det er, hvilket paradigme du bruker, konstruksjonen, hvordan du henter
ut selve løsningen, og kjøretiden. Fem til ti linjer per oppgave.

Oppgave 16. (Sjanger H — åpen algoritmedesign.) En sykehusavdeling har $n$
leger og $m$ vaktdøgn. Hver lege har oppgitt hvilke døgn hun kan ta, og kan ta
høyst fire. Hvert vaktdøgn trenger nøyaktig to leger. Beskriv hvordan du
avgjør om alle døgnene kan dekkes, og hvordan du finner en konkret vaktliste.

Oppgave 17. (Sjanger H.) En kommune vil hindre at en skogbrann sprer seg
fra et industriområde til et boligfelt. Kartet er et rutenett; å rydde
brannbelte i en rute koster et oppgitt beløp. Finn den billigste samlingen
ruter som gjør spredning umulig, og oppgi hvilke ruter det er.

Oppgave 18. (Sjanger H.) Et forlag skal dele en manusfil på $n$ avsnitt inn
i kapitler. Et kapittel som består av avsnittene $i$ til $j$, har en oppgitt
ubalansekostnad $K(i,j)$ som kan slås opp i konstant tid. Summen av
kostnadene skal minimeres. Beskriv en algoritme som finner både den laveste
totalkostnaden og selve kapittelinndelingen.

Oppgave 19. (Sjanger H.) Tre studenter og tre veiledningsgrupper har rangert
hverandre slik:

Aina:  Sild, Rev, Torsk        Rev:    Cato, Bror, Aina
Bror:  Sild, Rev, Torsk        Sild:   Cato, Bror, Aina
Cato:  Torsk, Sild, Rev        Torsk:  Aina, Bror, Cato

Aina spør om hun kan bli tildelt Sild i en stabil fordeling. Beskriv hvordan du
avgjør det, gjennomfør avgjørelsen, og oppgi svaret.

Oppgave 20. (Sjanger H, den vanskeligste.) Et jernbaneselskap har et nett
med $V$ stasjoner og $E$ strekninger, hver med en positiv kjøretid. Blant
alle ruter fra hovedstasjonen $s$ til endestasjonen $t$ som har minst
mulig samlet kjøretid, vil selskapet finne den som har flest
mellomstasjoner — flere stopp gir flere reisende. Beskriv en algoritme, og
oppgi kjøretiden.

Hva skiller de to besvarelsene (~10 min)

Begge kandidatene valgte riktig paradigme, skrev en rekurrens med riktig form,
og fikk kjøretiden riktig. Likevel ligger de et helt karaktertrinn fra
hverandre, og forskjellen er fire setninger:

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^2 n)$ og ikke $O(n^3)$ i oppgave 1?

☐ Markerte du eksplisitt hvilke to funksjoner som vokser like fort i
oppgave 2?

☐ Ga du et eksakt uttrykk i oppgave 3, og ikke en asymptotisk grense?

☐ Sto ordet «forventet» der det hørte hjemme i oppgave 5, og oppga du
$\Theta(n^2)$ og ikke $\Theta(n)$ som verste tilfelle for Randomized-Select?

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

☐ Leverte du både flytverdien og min-snittet i oppgave 8 — og kontrollerte
du at de to tallene er like?

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

☐ Sa du i oppgave 13 og 14 hva reduksjonen ikke viser, og ikke bare hva den
viser?

☐ Gikk reduksjonen i oppgave 14 fra det kjente vanskelige problemet til
det nye i din rettelse?

☐ Har hvert av de fem designsvarene (16–20) alle fem leddene? Tell dem, ett
svar om gangen.

☐ Rekonstruerte du selve løsningen i oppgave 16, 17, 18 og 20 — vaktlisten,
rutene, kapittelinndelingen og ruten — og ikke bare verdien?

☐ Nevnte du heltallsteoremet i oppgave 16?

☐ Nevnte du nodesplittingen i oppgave 17, og sa du hvorfor den trengs?

☐ Sa du i oppgave 19 hvilken orientering hver kjøring hadde?

☐ Argumenterte du i oppgave 20 for at korteste-vei-grafen er syklusfri?

☐ Oppga du kjøretidene i problemets egne størrelser — hva $V$ og $E$ er i
din konstruksjon — og ikke bare «$O(VE^2)$»?

Oppgraderingsmenyen for dette settet

Kommer du til bunns i grunnoppgavene 1–12, ligger avstanden opp mot toppen fire
konkrete steder. Alle fire kan trenes, og alle fire koster under et minutt hver
på selve eksamen:

1. Rekonstruksjonen i hvert designsvar. Fire av de fem designoppgavene ber
om selve løsningen. To setninger per oppgave — hva som leses av, og at det
ikke øker kjøretiden.
2. Reduksjonsretningen, tre ganger på rad. Oppgave 13, 14 og 15 tester det
samme fra tre vinkler. Les pilen høyt hver gang.
3. Kjøretid i problemets egne størrelser. «$O(VE^2)$ med $V = n+m+2$» er ett
ledd; «$O(VE^2)$» er et halvt.
4. De små forbeholdene. Heltallsteoremet i flytmodelleringen,
syklusfriheten i oppgave 20, kravet om stabil delsortering i oppgave 6. Det
er disse som gjør et riktig svar til et fullstendig svar.

Og et råd om tempo: klarte du ikke alle fem designoppgavene på 80 minutter,
er det ikke kunnskapen som mangler — det er rutinen. Ta
kap. 8.2 en gang til, med klokke.