8.3 Øvingseksamen 1 — bredt ordinært sett (kode E)

Forkunnskaper

Settet er bredt med vilje, og trekker på hele boka:

- asymptotisk notasjon og forenkling: kap. 1.1 og
kap. 1.2
- rekurrenser og masterteoremet: kap. 1.4
- sortering og utvelgelse: kap. 2.1,
kap. 2.2 og kap. 2.3
- hauger og binære søketrær: kap. 3.1 og
kap. 3.2
- korteste vei fra én kilde: kap. 4.3
- flytnett, snitt og maksimal flyt: kap. 5.1 og
kap. 5.2
- dynamisk programmering: kap. 6.1 og
kap. 6.2
- stabil matching: kap. 6.5
- P, NP og reduksjoner: kap. 7.1 og
kap. 7.2
- svarformen i hver oppgavetype: kap. 8.1, og
designoppskriften i kap. 8.2

Har du ikke lest alt ennå, kan du fortsatt ta settet — men da tar du det åpent,
med løsningsforslagene ved siden av, og bruker det som en kartlegging av hva som
mangler.

Oppgave 1–6: asymptotikk, rekurrens og kjøretid (~70 min)

Oppgave 1. (Sjanger A — asymptotisk forenkling, altså at du gir ett
strammest mulig uttrykk for hvor fort en funksjon vokser.) En analyse av et
lagerstyringsprogram gir kjøretidsfunksjonen $f(n) = 6n\lg n + 3n^2 + 250$.
Oppgi det strammeste asymptotiske uttrykket for $f(n)$. Svar i
$\Theta$-notasjon.

Oppgave 2. (Sjanger A.) Sorter disse fem funksjonene etter stigende
asymptotisk vekst, den saktest voksende først:
$n^2/\lg n$, $3^n$, $\lg(n!)$, $2^{\lg n}$, $n^{3/2}$.
Oppgi rekkefølgen som én liste. Her er $\lg n = \log_2 n$.

Oppgave 3. (Sjanger A.) La $f(n) = n^2\lg n$ og $g(n) = n^2$. Av de fem
asymptotiske symbolene $O$, $\Omega$, $\Theta$, $o$ og $\omega$: hvilke gjelder
når $f(n)$ beskrives i forhold til $g(n)$? Oppgi alle som gjelder, og bare dem.

Oppgave 4. (Sjanger B — rekurrensløsning med navngitt metode, altså at du
oppgir hvilken metode du bruker, ikke bare svaret.) Løs rekurrensen
$T(n) = 3T(n/4) + n\lg n$ asymptotisk. Oppgi metoden, svaret i
$\Theta$-notasjon, og hvilket tilfelle du lander i.

Oppgave 5. (Sjanger E — kjøretidskunnskap, altså at du oppgir kjøretiden og
de egenskapene algoritmen garanterer.) Oppgi verste-tilfelle-kjøretiden til
Heapsort, om den sorterer på stedet, og om den er stabil.

Oppgave 6. (Sjanger E.) Du skal sortere $n$ heltall som alle ligger i
intervallet fra $0$ til $n^3$. Hvilken av Counting-Sort og Merge-Sort gir
lavest asymptotisk verste-tilfelle-kjøretid på nettopp denne inputen? Oppgi
valget og kjøretiden.

— naturlig pausepunkt —

Oppgave 7–12: kjøretid, definisjoner og håndkjøring (~70 min)

Oppgave 7. (Sjanger E.) Oppgi kjøretiden til Randomized-Select både i
forventning og i verste tilfelle, og verste-tilfelle-kjøretiden til Select
(median av medianer).

Oppgave 8. (Sjanger D — definisjon med egne ord, altså én presis setning med
hovedpoenget først.) Definer hva det vil si at en sorteringsalgoritme er
stabil, og nevn én situasjon der egenskapen er nødvendig.

Oppgave 9. (Sjanger D.) La $G=(V,E)$ være et flytnett med kilde $s$ og sluk
$t$. Definer et snitt $(S,T)$ i $G$, og definer kapasiteten til snittet.

Oppgave 10. (Sjanger D.) Definer hva et sertifikat er, og hva det vil si
at et avgjørelsesproblem ligger i klassen NP.

Oppgave 11. (Sjanger C — håndkjøring, altså at du utfører algoritmen steg
for steg og oppgir bare sluttilstanden.) Arrayet er
A[1..8] = [4, 13, 7, 2, 19, 6, 11, 9], med indeks fra 1.

a) Kjør Build-Max-Heap(A), og oppgi hele arrayet fra indeks 1 etterpå.
b) Kjør deretter ett Heap-Extract-Max(A) på haugen fra a), og oppgi både
verdien som returneres og haugen A[1..7] etterpå.

Du skal bare oppgi sluttilstandene, ikke mellomstegene.

Oppgave 12. (Sjanger C.) Et transportnett er en rettet graf med seks
omlastingspunkter $s$, $t$, $u$, $v$, $x$ og $y$. Kantene, med kjøretid i
minutter, er:

s -> u 7, s -> x 3, u -> v 4, u -> x 2, x -> u 2, x -> v 9,
x -> y 5, y -> v 3, y -> t 8, v -> t 6.

Kjør Dijkstra fra $s$ og oppgi v.d for hver node, i rekkefølgen $s$, $t$,
$u$, $v$, $x$, $y$. Bare sluttilstanden.

— naturlig pausepunkt —

Oppgave 13–16: ja/nei-utsagn og NP-argumenter (~45 min)

Oppgave 13. (Sjanger F — «stemmer dette?», altså at du svarer ja eller nei
først og deretter begrunner i én setning.) Stemmer denne påstanden?
«Inorder-Tree-Walk på et binært søketre skriver ut nøklene i den rekkefølgen
de ble satt inn i treet.»

Oppgave 14. (Sjanger F.) Stemmer denne påstanden? «Ford-Fulkerson er
NP-hardt, siden kjøretiden ikke er polynomisk i inputstørrelsen.»

Oppgave 15. (Sjanger G — reduksjon og NP-argument, altså at du oppgir
hvilken vei reduksjonen går, hva den beviser og hva den ikke beviser.) Et
vaktplanleggingsproblem kalt RUTEVAKT skal vises å være vanskelig. Noen gir en
polynomisk reduksjon fra RUTEVAKT til 3-CNF-SAT, og konkluderer med at RUTEVAKT
er NP-hardt. Er argumentet gyldig? Oppgi hva reduksjonen faktisk viser, og hva
som må gjøres i stedet.

Oppgave 16. (Sjanger G.) Du har gitt en korrekt polynomisk reduksjon fra
VERTEX-COVER til et bemanningsproblem kalt BEMANNING. Hva har du dermed vist?
Hva mangler før du kan konkludere at BEMANNING er NP-komplett, og hva har du
fremdeles ikke vist om BEMANNING?

— naturlig pausepunkt —

Oppgave 17–20: åpen algoritmedesign (~55 min)

De fire siste oppgavene er åpne. Svar kort, i fem ledd: hvilket klassisk problem
dette er, hvilket paradigme du bruker, hvordan konstruksjonen ser ut, hvordan du
henter ut selve løsningen, og hva kjøretiden blir. Fem korte punkter holder — det
er formen, ikke lengden, som gir uttelling.

Oppgave 17. (Sjanger H — åpen algoritmedesign, altså at du skisserer en
algoritme i fem korte ledd i stedet for å skrive kode.) Et sykehjem skal sette
opp vaktlisten for en periode. Det er $n$ ansatte og $m$ vakter. Ansatt $i$ kan
ta høyst $b_i$ vakter i perioden, og har en liste over hvilke vakter hen er
kvalifisert for. Vakt $j$ må bemannes av nøyaktig $r_j$ personer. Beskriv en
algoritme som avgjør om hele vaktlisten kan dekkes, og som i så fall også
skriver ut hvem som tar hvilken vakt. Oppgi kjøretiden.

Oppgave 18. (Sjanger H.) Et bagasjeanlegg på en flyplass er en rettet graf:
nodene er sorteringspunkter, kantene er transportbånd, og hvert bånd har en
kapasitet i kolli per minutt. All bagasje kommer inn i punktet $s$ og skal ut i
punktet $t$. Beskriv en algoritme som finner hvor mange kolli per minutt
anlegget tåler, og som i tillegg peker ut et sett bånd som til sammen er det som
begrenser kapasiteten. Oppgi begge svarene og kjøretiden.

Oppgave 19. (Sjanger H.) En vandrerute går innom $k$ hytter i fast
rekkefølge. Etappen fra hytte $i-1$ til hytte $i$ er $d_i$ kilometer. Turen skal
deles i dagsmarsjer: hver dagsmarsj er en sammenhengende følge av etapper, og en
dag med samlet lengde $\ell$ gir ubehaget $(M - \ell)^2$, der $M$ er den ønskede
dagslengden. Beskriv en algoritme som finner oppdelingen med minst samlet
ubehag, og som skriver ut hvilke hytter man overnatter på. Oppgi kjøretiden.

Oppgave 20. (Sjanger H.) $n$ studenter skal fordeles på $n$ praksisplasser,
én student per plass. Hver student har rangert alle plassene, og hver plass har
rangert alle studentene. Fordelingen skal være slik at det ikke finnes en student
og en plass som begge helst ville byttet til hverandre. Beskriv en algoritme som
finner en slik fordeling, si hvordan du henter den ut, og oppgi kjøretiden. Si
også hvilken av de to sidene du lot fri.

Herfra og ned står løsningsforslagene, ett per oppgave. Ta dem først når du er
ferdig med å svare.

To modellbesvarelser på oppgave 17 (~15 min)

De to besvarelsene under er nyskrevet av oss for å vise forskjellen på et svar
som lander skarpt og et som er riktig, men ikke ferdig. Begge svarer på oppgave
17, vaktlisten. Les dem etter hverandre, og se om du finner de tre forskjellene
før du åpner kommentaren til slutt.

Hva skiller de to

Begge velger riktig paradigme, og begge setter opp det samme flytnettet med
riktige kapasiteter. Forskjellen ligger i tre ting.

Rekonstruksjonen. Oppgaven ber om hvem som tar hvilken vakt. Den øverste
besvarelsen leser tilordningen av midtkantene med flyt $1$ og sier at avlesningen
koster $O(E)$ og ikke endrer kjøretiden. Den nederste stopper ved flytverdien og
svarer dermed bare på halve spørsmålet (felle #6 — å behandle rekonstruksjonen av
selve løsningen som noe som kommer av seg selv).

Heltallsteoremet. Uten det er det ingenting i den nederste besvarelsen som
forklarer hvorfor en flyt på en midtkant er $0$ eller $1$ og ikke $0{,}5$. Den
øverste sier det i én setning, og det er den setningen som gjør at «flyt» og
«vaktliste» faktisk er samme ting her.

Kjøretiden. «Polynomisk tid» er sant, men det er ikke et uttrykk. Den øverste
oppgir $O(VE^2)$, definerer $V$ og $E$ i oppgavens egne størrelser, og sier
hvorfor grensen er $O$ og ikke $\Theta$. En riktig algoritme uten kjøretid mister
det siste poenget — og en kjøretid uten $V$ og $E$ definert er halvveis.

Fra midt til topp på denne oppgaven:

- skriv kjøretiden som et uttrykk, ikke som ordet «polynomisk»;
- definer hver bokstav i uttrykket i oppgavens egne størrelser;
- si hvordan du henter ut selve løsningen, og at det ikke endrer kjøretiden;
- nevn heltallsteoremet i én setning hver gang du modellerer med flyt;
- velg $O$ eller $\Theta$ bevisst, og si hvorfor når det er tvil.

Selvdiagnose (~10 min)

Gå gjennom svarene dine med denne lista. Kryss av det du faktisk gjorde, ikke det
du mente å gjøre.

☐ Oppga du bare det som ble etterspurt, og ikke mer?
☐ Er hver kjøretid det strammeste uttrykket du kan gi?
☐ Står $\Theta$ der garantien er tett, og $O$ der du bare har vist en øvre grense?
☐ Skilte du forventet fra verste tilfelle der de er forskjellige?
☐ Går reduksjonen din FRA det kjent vanskelige problemet TIL det nye?
☐ Skrev du ut hva reduksjonen ikke beviser?
☐ Leverte du haugen som et array fra indeks 1, og ikke som et tre?
☐ Kjørte du Dijkstra helt ferdig, i stedet for å stoppe da sluknoden først fikk en endelig verdi?
☐ Navnga du paradigmet i hver designoppgave, med ordet?
☐ Rekonstruerte du selve løsningen — vaktlisten, snittet, oppdelingen, matchingen — og ikke bare verdien?
☐ Nevnte du heltallsteoremet der du modellerte med flyt?
☐ Definerte du $V$, $E$, $n$ og $m$ i kjøretidsuttrykkene dine?

Herfra og opp. Fire ting skiller midtsjiktet fra toppen på nettopp dette
settet:

- Fra riktig til strammest. $O(n^2)$ er ikke galt der $\Theta(n\lg n)$ er
sant, men det er ikke svaret oppgaven ber om. Spør deg alltid om du kan gi en
tettere grense.
- Fra verdi til løsning. Flytverdien, minimumsubehaget og snittkapasiteten er
tall. Vaktlisten, oppdelingen og båndene er løsninger. Oppgavene ber om det
siste, og rekonstruksjonen koster asymptotisk ingenting.
- Fra retning til konsekvens. Å si hvilken vei reduksjonen går er første
halvdel. Andre halvdel er å si hva den beviser og hva den ikke beviser.
- Fra formel til begrunnelse. En kjøretid som står alene, kan være pugget.
Én setning om hvor den kommer fra — hvor mange delproblemer, hvor mange
forøkende stier, hvor høy haugen er — viser at du kan utlede den igjen.