Question 1

Hva er forskjellen på et problem og en instans?

Accepted Answer

Problemet er relasjonen mellom input og output, for eksempel «outputen er en stigende omordning av inputen». Instansen er én bestemt input, for eksempel \langle 6, 8, 3, 5 \rangle.

Question 2

Hva koster én operasjon i RAM-modellen, og hvor brede er heltallene?

Accepted Answer

Aritmetikk, sammenligning, hopp og oppslag i én celle koster én tidsenhet hver. Heltallene er om lag c \lg n bits brede, akkurat nok til å indeksere hele inputen.

Question 3

Skriv definisjonen av f(n) = O(g(n)).

Accepted Answer

Det finnes konstanter c > 0 og n_0 slik at 0 \le f(n) \le c\,g(n) for alle n \ge n_0.

Question 4

Skriv definisjonen av f(n) = \Theta(g(n)).

Accepted Answer

Det finnes c_1, c_2 > 0 og n_0 slik at 0 \le c_1 g(n) \le f(n) \le c_2 g(n) for alle n \ge n_0. Altså både O(g) og \Omega(g).

Question 5

Hva skiller o fra O, og \omega fra \Omega?

Accepted Answer

O og \Omega tillater at f og g vokser like raskt. o og \omega gjør ikke det: de krever ulikheten for enhver c > 0, som er det samme som at f/g går mot 0 eller mot uendelig. Derfor er 2n^2 = O(n^2), mens 2n^2 
e o(n^2).

Question 6

Oversett de fem operatorene til sammenligning av tall.

Accepted Answer

O er a \le b, \Omega er a \ge b, \Theta er a = b, o er a b. Unntaket er at to funksjoner kan mangle et forhold helt, mens to tall alltid kan sammenlignes.

Question 7

Betyr O alltid verste tilfelle?

Accepted Answer

Nei. O er en øvre grense og kan brukes på hvilken som helst kjøretidsfunksjon, også beste tilfelle. Grense og tilfelle er to uavhengige akser.

Question 8

Hva betyr det at verste tilfelle er \Omega(n^2)?

Accepted Answer

Den dyreste instansen av størrelse n koster minst kvadratisk tid. Det er en nedre grense for et maksimum, på samme vis som «den høyeste i klassen er minst 1 m høy».

Question 9

Forenkle O(n^a) + \Omega(n^b) + \Theta(n^c).

Accepted Answer

\Omega(n^b + n^c). Summer nedre grenser (0 + n^b + n^c) og øvre for seg. De øvre er ubegrenset fordi \Omega(n^b) ikke setter noe tak, så bare den nedre står igjen.

Question 10

Hvorfor er n + O(n) = O(n) riktig, mens O(n) = n + O(n) er galt?

Accepted Answer

Ligninger med asymptotisk notasjon leses fra venstre mot høyre, og høyresiden må være minst like generell som venstresiden. Ikke alt som er O(n) kan skrives som n pluss noe som er O(n).

Question 11

De tre delene i et løkkeinvariant-bevis?

Accepted Answer

Initialisering (invarianten holder før første iterasjon), vedlikehold (holder den før en iterasjon, holder den før den neste) og terminering (løkka stopper, og invarianten gir da det du ville vise).

Question 12

Hva skiller svak fra sterk induksjon?

Accepted Answer

Svak induksjon antar bare forrige trinn og passer til løkker. Sterk induksjon antar alle mindre tilfeller, og passer når en algoritme kaller seg selv på instanser som er mindre enn n - 1, som halvparten.

Question 13

Hva er løkkeinvarianten til Insertion-Sort?

Accepted Answer

A[0 .. i - 1] er sortert ved starten av hver iterasjon av for-løkka, og består av de elementene som lå der fra begynnelsen.

Question 14

Insertion-Sort i beste og i verste tilfelle?

Accepted Answer

\Theta(n) når tabellen er sortert fra før og ingen forskyvninger trengs. \Theta(n^2) når den er sortert synkende, med n(n-1)/2 forskyvninger.

Question 15

Hvor stor n rekker en faktoriell og en kvadratisk algoritme på hundre år, ved ett mikrosekund per operasjon?

Accepted Answer

17 mot rundt 56 millioner. En eksponentiell algoritme kommer til 51.

Question 16

Hvorfor koster indeksering i en tabell konstant tid?

Accepted Answer

Tabellen ligger sammenhengende i minnet, så element i ligger på adresse a + b(i - s): ett gangestykke og én addisjon, uansett størrelse.

Question 17

Stakk og kø: hva er forskjellen?

Accepted Answer

Stakken er sist inn, først ut, med Push og Pop på toppen. Køen er først inn, først ut, med Enqueue bakerst og Dequeue forrest.

Question 18

Hvordan får en kø plass i en tabell med fast lengde, uten at noe flyttes?

Accepted Answer

Som ringbuffer: head peker på den første i køen og tail på neste ledige plass, og begge går rundt til starten når de passerer enden.

Question 19

Hva koster søk, innsetting og sletting i en lenket liste?

Accepted Answer

Søk er \Theta(n): pekerne må følges fra hodet. Innsetting og sletting er \Theta(1), men bare når du allerede står ved noden.

Question 20

Hva er kjeding i en hashtabell?

Accepted Answer

Hver plass i tabellen holder en lenket liste, og alle nøkler som hasher dit, settes inn forrest i lista. Kollisjoner koster dermed bare lengre lister.

Question 21

Forventet og verste søketid i en hashtabell med kjeding?

Accepted Answer

Forventet \Theta(1 + \alpha) med belastningsfaktor \alpha = n/m og jevn fordeling; konstant når m = \Theta(n). Verste tilfelle \Theta(n): alle nøklene kan havne på samme plass.

Question 22

Hva er perfekt hashing, og når kan den brukes?

Accepted Answer

To nivåer for en statisk nøkkelmengde: m = n plasser, og plass j med n_j nøkler får en kollisjonsfri sekundærtabell med n_j^2 plasser. Søk tar garantert konstant tid og plassen er O(n), men nøklene må være kjent på forhånd.

Question 23

Hvorfor er tabelldobling amortisert konstant per innsetting?

Accepted Answer

n innsettinger koster n skrivinger pluss kopieringene. Er n en toerpotens, er kopieringene 1 + 2 + 4 + \cdots + n/2 = n - 1, totalt 2n - 1. Ellers er kopieringene færre enn 2n, så totalen er alltid under 3n, altså under 3 per innsetting.

Question 24

Amortisert kjøretid og gjennomsnittstilfellet: hva er forskjellen?

Accepted Answer

Amortisering er et snitt over operasjonene i en følge, i verste fall og uten sannsynlighet. Gjennomsnittstilfellet er et snitt over instanser, med en sannsynlighetsfordeling.

Question 25

Søke-, beslutnings- og optimeringsvarianten av CLIQUE?

Accepted Answer

Søk: finn en klikk med k noder. Beslutning: finnes en klikk med k noder? Optimering: finn en størst mulig klikk.

Question 26

Hva er et sertifikat?

Accepted Answer

En påstått løsning y som verifiseres mot instansen: sjekk om (x, y) \in R. Ofte langt billigere enn å finne løsningen, som når en permutasjon sjekkes i lineær tid mens sortering krever \Omega(n \lg n) sammenligninger.

Question 27

Cook-, Levin- og Karp-reduksjoner: hva skiller dem?

Accepted Answer

Cook: vilkårlig mange orakelkall og eget polynomisk arbeid. Levin: ett kall, og løsningen oversettes tilbake. Karp: ett kall for beslutningsproblemer, ja/nei går uendret gjennom. Hver er et spesialtilfelle av den forrige.

Question 28

Du reduserer X billig til Y. Hva vet du om vanskegraden?

Accepted Answer

Y er minst like vanskelig som X: en effektiv algoritme for Y gir en for X, og kan ikke X løses effektivt, kan heller ikke Y.

Question 29

De tre delene i et dekomponeringsdesign, og hva som må gjelde i tillegg?

Accepted Answer

Grunntilfelle som løses direkte, induksjonshypotese om at delinstansene kan løses, og et induksjonssteg som dekomponerer og kombinerer riktig. I tillegg må instansene krympe, så rekursjonen terminerer.

Question 30

Insertion-Sort som dekomponering?

Accepted Answer

Kutt av siste element, sorter resten etter induksjonshypotesen, og sett elementet inn på rett plass. Alt arbeidet ligger i kombinasjonen; selection sort er speilbildet, med arbeidet i dekomponeringen.

Question 31

De fire delene i splitt og hersk?

Accepted Answer

Grunntilfelle som løses direkte; del instansen i uavhengige delinstanser; løs dem rekursivt; kombiner delsvarene. Arbeidet ligger som regel i enten delingen (Quicksort) eller kombinasjonen (Merge-Sort).

Question 32

Hva er en algoritmisk rekurrens?

Accepted Answer

En rekurrens med konstant grunntilfelle, T(n) = \Theta(1) for n under en grense, som terminerer etter endelig mange kall. Antas når ikke annet er sagt.

Question 33

Løs T(n) = T(n/2) + 1 med iterasjonsmetoden.

Accepted Answer

T(n) = T(n/4) + 2 = \cdots = T(n/2^i) + i. Grunntilfellet T(1) nås ved i = \lg n, så T(n) = \lg n + 1 = \Theta(\lg n). Det er binærsøk.

Question 34

Hvorfor er Merge-Sort \Theta(n \lg n) i alle tilfeller?

Accepted Answer

T(n) = 2T(n/2) + n: rekursjonstreet har \lg n + 1 nivåer, og hvert nivå fletter til sammen n elementer. Delingen på midten avhenger ikke av inputen.

Question 35

Hva gjør vaktposten \infty i flettingen?

Accepted Answer

Den står bakerst i både L og R, så ingen av halvdelene går tom før den andre. Løkka trenger da ingen egen test for tomme halvdeler.

Question 36

Invarianten i Partition?

Accepted Answer

Tre soner: elementene fra p til og med i er små (\le x), fra i+1 til og med j-1 store, og fra j og utover ikke sett ennå. Pivoten x = A[r] settes til slutt inn på plass i+1, sin endelige plass.

Question 37

Quicksort i beste, gjennomsnittlige og verste tilfelle?

Accepted Answer

\Theta(n \lg n) ved jevn deling og i snitt over alle rekkefølger. \Theta(n^2) når pivoten står alene på hvert nivå, T(n) = T(n-1) + n, som på allerede sortert input.

Question 38

Hva oppnår Randomized-Quicksort?

Accepted Answer

Pivoten velges tilfeldig, så ingen instans er alltid dårlig. Hvert element er med i O(\lg n) delinger i forventning, så forventet kjøretid er \Theta(n \lg n) for enhver input; verste tilfelle er fortsatt \Theta(n^2), men krever uflaks med de tilfeldige valgene.

Question 39

Gjennomsnittstilfelle, amortisert og forventet kjøretid: tre snitt over hva?

Accepted Answer

Gjennomsnittstilfelle: snitt over instanser, med en sannsynlighetsfordeling over input. Amortisert: snitt over operasjonene i én følge, i verste fall. Forventet: snitt over algoritmens egne tilfeldige valg, for én fast instans.

Question 40

Masterteoremets tre tilfeller for T(n) = aT(n/b) + f(n)?

Accepted Answer

Sammenlign f(n) med n^{\log_b a}. Polynomisk mindre: \Theta(n^{\log_b a}), løvnodene dominerer. Lik opp til \lg^k n for en konstant k \ge 0: \Theta(n^{\log_b a} \lg^{k+1} n), alle nivåene like. Polynomisk større og regulær: \Theta(f(n)), rota dominerer.

Question 41

Løs T(n) = 2T(n/2) + n \lg n.

Accepted Answer

n^{\log_2 2} = n, og f(n) = n \lg n ligger en logaritmisk faktor over. Det er ikke polynomisk, så tilfelle 2 med k = 1: \Theta(n \lg^2 n).

Question 42

Hva er galt med «T(n-1) = O(1) gir T(n) \le c + 1 = O(1)» for T(n) = T(n-1) + 1?

Accepted Answer

Konstanten i hypotesen er c, i konklusjonen c + 1. Induksjon krever nøyaktig samme påstand før og etter, så asymptotisk notasjon i induksjonssteget kan skjule at grensen vokser med n. Riktig svar er T(n) = n.

Question 43

Hvorfor bruker sammenligningsbasert sortering \Omega(n \lg n) sammenligninger i verste tilfelle?

Accepted Answer

Beslutningstreet må ha en løvnode for hver av de n! permutasjonene, og et binært tre med høyde h har høyst 2^h løvnoder. Så h \ge \lg n! > n \lg n - n \lg e ved Stirling. Høyden er antall sammenligninger på den lengste stien.

Question 44

Hva sier sorteringsgrensen om beste tilfelle?

Accepted Answer

Ingenting ut over \Omega(n), for hvert element må leses. Grensen er en nedre grense for verste tilfelle; Insertion-Sort bruker \Theta(n) på sortert input.

Question 45

Hvordan får et annet problem en nedre grense fra sorteringsgrensen?

Accepted Answer

Ved en reduksjon fra sortering til problemet med kjøretid o(n \lg n). Kunne problemet løses raskere, kunne også sortering gjøres raskere. En reduksjon fra problemet til sortering sier ingenting.

Question 46

Hva skiller Randomized-Select fra Quicksort?

Accepted Answer

Ett rekursivt kall i stedet for to. Pivoten på plass q har rang k = q - p + 1; er i = k, er den svaret, er i < k, søkes rang i blant de små, ellers rang i - k blant de store.

Question 47

Forventet og verste kjøretid for Randomized-Select?

Accepted Answer

Forventet \Theta(n) for enhver input. Deler pivoten på midten hver gang, er T(n) = T(n/2) + n = 2n - 1, en geometrisk sum. Det gjør den ikke alltid, men forventningen over de tilfeldige valgene gir samme orden. Verste tilfelle \Theta(n^2) når pivoten står ytterst hver gang, som for Quicksort.

Question 48

Hvordan garanterer Select en god pivot, og hva blir rekurrensen?

Accepted Answer

Pivoten er medianen av medianene til grupper på fem. Halvparten av gruppemedianene er \ge x, hver med to elementer over seg, så minst 3n/10 er \ge x, og tilsvarende \le x. T(n) \le T(n/5) + T(7n/10) + \Theta(n) = \Theta(n), siden 1/5 + 7/10 < 1.

Question 49

Hvordan finner du de k minste elementene i O(n)?

Accepted Answer

Finn elementet med rang k med Select, og del tabellen rundt det med Partition. De k minste står til venstre for pivoten, usortert.

Question 50

Hva er en stabil sorteringsalgoritme?

Accepted Answer

Like nøkler står i samme innbyrdes rekkefølge i output som i input. Det betyr noe når elementene bærer mer enn nøkkelen, og det er det Radix-Sort bygger på.

Question 51

Hvorfor er Counting-Sort stabil?

Accepted Answer

Etter den kumulative tellingen er C[v] antall elementer \le v, altså plassen etter den siste v-en i B. A gjennomgås baklengs: den siste v-en i A får den siste plassen i sin blokk, og hver tidligere v legges ett hakk til venstre.

Question 52

Kjøretiden til Counting-Sort, og hvorfor bryter den ikke sorteringsgrensen?

Accepted Answer

\Theta(n + k) for heltall i 0 .. k, lineært når k = O(n). Grensen gjelder algoritmer som bare sammenligner; Counting-Sort bruker verdiene som indekser i C, og det krever små heltall.

Question 53

Hvorfor må Radix-Sort starte med det minst signifikante sifferet, med en stabil subrutine?

Accepted Answer

Invarianten er at tallene etter i pass er sortert på de i siste sifrene. Stabiliteten er induksjonssteget: like siffer beholder ordningen fra de lavere sifrene. Starter du fremst, ødelegger neste pass ordningen fra det forrige.

Question 54

Bucket-Sort: forutsetning, kjøretid og hva slags snitt er det?

Accepted Answer

Input uniformt fordelt i [0, 1), n bøtter, Insertion-Sort i hver. Forventet \Theta(n) fordi hver bøtte får forventet ett element; verste tilfelle \Theta(n^2). Forventningen er et snitt over inputer, ikke over algoritmens egne valg som i Randomized-Select.

Question 55

Hva skiller dynamisk programmering fra splitt og hersk?

Accepted Answer

Delinstansene overlapper: den samme delinstansen trengs av flere større instanser. Dynamisk programmering lagrer hvert delsvar og løser hver delinstans én gang. I splitt og hersk overlapper ikke delinstansene, så lagring gir ingenting.

Question 56

Hvorfor gjør Cut-Rod uten lagring 2^n kall?

Accepted Answer

Kallet på lengde n kaller alle lengdene fra n - 1 ned til 0, så T(n) = 1 + \sum_{j=0}^{n-1} T(j). Trekk T(n-1) fra: T(n) = 2T(n-1), og med T(0) = 1 er T(n) = 2^n. Det finnes bare n + 1 forskjellige delinstanser.

Question 57

Hva er delinstansgrafen, og hvorfor må den være asyklisk?

Accepted Answer

Én node per delinstans og en kant fra u til v når v bygger på u. En sykel betyr at en instans bygger på seg selv: rekursjonen stopper aldri, og en løkke har ikke noe sted å starte.

Question 58

Hva er optimal delstruktur, og hvilket kjent problem mangler det?

Accepted Answer

En optimal løsning består av optimale løsninger på delinstansene. Korteste vei har det. Lengste enkle vei har det ikke: lengste enkle veier fra 1 til 2 og fra 2 til 4 kan bruke de samme nodene, og da er sammensetningen ikke en enkel vei.

Question 59

Hva er forskjellen på memoisering og løsning nedenfra og opp?

Accepted Answer

Memoisering beholder rekursjonen og lagrer svaret første gang en delinstans løses, og løser bare delinstansene som trengs. Nedenfra og opp løser alle delinstansene i topologisk rekkefølge uten kall, og er som regel raskere med en konstant faktor. Kjøretiden er som regel asymptotisk den samme.

Question 60

Hvordan finner du selve kappingen i stavkapping, og ikke bare den beste prisen?

Accepted Answer

Lagre valget: s[j] er lengden på den første biten i en optimal kapping av lengde j. Les av bakfra: skriv ut s[n], sett n = n - s[n], og gjenta til n = 0.

Question 61

Skriv rekurrensen for LCS.

Accepted Answer

c[i, j] = 0 hvis i = 0 eller j = 0, c[i-1, j-1] + 1 hvis x_i = y_j, og ellers \max(c[i-1, j], c[i, j-1]). Tabellen fylles rad for rad i \Theta(mn).

Question 62

Hvordan leser du av hvilke gjenstander som er med, fra ryggsekktabellen K?

Accepted Answer

Start i K[n, W]. Er K[i, j] 
e K[i-1, j], var gjenstand i med, og du fortsetter fra K[i-1, j - w_i]. Ellers fortsetter du fra K[i-1, j].

Question 63

Er \Theta(nW) for det binære ryggsekkproblemet en polynomisk kjøretid?

Accepted Answer

Nei, den er pseudopolynomisk. W tar bare m = \lfloor \lg W \rfloor + 1 bits, så \Theta(nW) = \Theta(n 2^m), som er eksponentielt i inputstørrelsen.

Question 64

Hva sier grådighetsegenskapen, og hva sier den ikke?

Accepted Answer

Det finnes en optimal løsning som tar det første grådige valget. At du kan fortsette å velge grådig, følger først sammen med optimal delstruktur, ved induksjon.