Sist endret: 23.09.2016  
 

Løsningsforslag - Splitt og hersk

[Oppgave] [Levering] [Løsningsforslag]

Innleveringsfrist: 18.09.2017 15:00

Du er logget inn og får derfor se om du har svart riktig/feil på de enkelte oppgavene.
LF-svar er markert med grønt og feil svar er markert med rødt.

Hvis dere er uenige i fasit, oppfordres dere til å diskutere dette på Piazza.

Oppgave 1

Denne oppgaven handler om sorteringsalgoritmer.

[ feil ]a) Vi har en usortert liste med $n$ elementer, og vi ønsker å finne ut om alle elementene i listen er unike. Etter algoritmene vi har lært så langt, hva er raskeste kjøretiden vi kan få når vi løser denne oppgaven? (5 %)

$\Theta(\log(\log(n)))$
$\Theta(\log(n))$
$\Theta(\sqrt{n})$
$\Theta(n)$
$\Theta(n \log(n))$
$\Theta(n \sqrt{n})$
$\Theta(n^2)$
Ingen av alternativene stemmer.

Din kommentar:
LF-forklaring: Vi sorterer listen først med en $O(n \lg(n))$ algoritme. Deretter søker vi gjennom listen sekvensielt og ser etter etterfølgende elementer med samme verdi. (Dette blir egentlig $O(n \lg(n)) + O(n)$, men som vi har lært så dominerer det asymptotisk største leddet, så vi ignorerer $O(n)$.)

[ riktig ]b) Vi ønsker å sortere en liste med lavest mulig minneforbruk. Hvilken algoritme er best? (5 %)

Bubblesort
Mergesort
Heapsort
De bruker like mye

Din kommentar:
LF-forklaring: Heapsort sorterer in place, og bruker asymptotisk mindre minne enn mergesort. Den er også raskere enn bubblesort, så vi velger den.

[ riktig ]c) Vi oppnår worst-case tid for quicksort hvis listen allerede er sortert. (5 %)

Sant
Usant

Din kommentar:
LF-forklaring: Vi vil da til enhver tid velge en pivot som gir oss worst-case partisjonstilfelle.

[ riktig ]d) Quicksort forbruker $O(1)$ ekstra minne i tillegg til det minnet som trengs for å lagre tallene som skal sorteres. (5 %)

Sant
Usant

Din kommentar:
LF-forklaring: Man må lagre indeksene for hvert rekursive kall.

[ riktig ]e) All input kan gi worst-case kjøretid for randomized-quicksort. (5 %)

Sant
Usant

Din kommentar:
LF-forklaring: Vi kan ha uflaks og alltid velge det største eller minste elementet som pivot. Heldigvis skjer det veldig sjeldent.

Oppgave 2

Denne oppgaven tar for seg substitusjonsmetoden for å løse rekurrenser.

Gitt rekurrensen:

$$T(n) = 2401 T(n/7) + n^3$$ $$T(1) = 1$$

Dersom vi skulle benyttet oss av substitusjonsmetoden og antatt at:

$$T(n/2) \leq c \cdot \frac{n^2}{4} \cdot \log(n/2)$$

[ riktig ]a) Hva håper vi på å kunne bevise? (5 %)

At man kan finne en nedre asymptotisk grense for rekurrensen.
At $T(n) \leq c \cdot \frac{n^2}{4} \cdot \log(n/2)$
At $T(n) \leq c \cdot n \cdot \log(n)$
At $T(n) \leq c \cdot n^2 \cdot \log(n)$

Din kommentar:
LF-forklaring: Antagelsen om at $T(n/2) \leq c \cdot \frac{n^2}{4} \cdot log(n/2)$ for $n/2$ impliserer at vi forsøker å bevise at $T(n) \leq c \cdot n^2 \cdot log(n)$ for $n$. (Dette ser vi hvis vi erstatter $n/2$ med $n$.)

[ riktig ]b) Hvis du anvender master-teoremet på denne rekurrensen, hvilket tilfelle tilhører den? (5 %)

Case 1
Case 2
Case 3
Ingen av dem

Din kommentar:
LF-forklaring: Masterteoremet gir case 1: $a = 7^4$, $b=7$, $f(n)=n^3$.

[ riktig ]c) Hva blir kjøretiden? (Du kan velge fremgangsmåte selv) (5 %)

$\Theta(n)$
$\Theta(n \log(n))$
$\Theta(n^2)$
$\Theta(n^3)$
$\Theta(n^4)$

Din kommentar:
LF-forklaring:

[ riktig ]d) Hvis vi bytter ut $n^3$ med $n^5$, hvilket case får vi hvis vi vil bruke masterteoremet? (5 %)

Case 1
Case 2
Case 3
Ingen av dem

Din kommentar:
LF-forklaring:

Oppgave 3

Løs denne oppgaven ved hjelp av variabelskifte. Husk at $n^\frac{1}{2} = \sqrt{n}$.

[ feil ]a) Løs rekurrensen gitt ved: $T(n) = T(n^\frac{1}{2}) + 1$ (5 %)

$\Theta(\lg n)$
$\Theta(\lg \lg n)$
$\Theta(\lg \lg \lg n)$
$\Theta(\lg \lg \lg \lg n)$

Din kommentar:
LF-forklaring: La $m = \lg n$ og $S(m) = T(2^m)$. Dermed får vi: $T(n) = T(2^\frac{m}{2}) + 1$, som igjen gir: $S(m) = S(m/2) + 1$. Denne løser vi med masterteoremet og får $S(m) = \Theta(\lg m)$. Setter vi dette inn i den opprinnelige rekurrensen finner vi løsningen: $T(n) = T(2^m) = S(m) = \Theta(\lg m) = \Theta(\lg \lg n)$. )

Oppgave 4

Løs denne oppgaven ved hjelp av rekursjonstrær.

[ feil ]a) Vi har en rekurrens $T(n) = T(n/3) + T(n/2) + n$, $T(1) = 1$. Hva er høyden til rekursjonstreet? (10 %)

$\Theta(n \log(n))$
$\log_3 (n) + 1$
$\log_6 (n) + 1$
$\Theta(\log (n))$
$\log_\frac{3}{2} (n) + 1$

Din kommentar:
LF-forklaring: $T(n/2)$-leddet er det dominerende, slik at høyden vil være $\log_2 (n) + 1$ (det krever flere delinger for å komme til $0$ når du bare deler på $2$ enn når du deler på $3$). I asymptotisk notasjon ser vi bort fra konstanter. $\log_a (n)$ er bare forskjellig fra $\log_b (n)$ med en konstant faktor, $\log_a (n) = \log_b (n) / \log_b (a)$. I alternativene som ikke bruker asymptotisk notasjon, kan vi ikke se bort fra denne konstanten, så de er derfor feil alle sammen. 1-tallet ses bort fra i asymptotisk notasjon fordi det domineres av log $n$.

Oppgave 5

Denne oppgaven handler om kjøretidsanalyse.

[ feil ]a)

Funksjonen gjoerNoe() har kjøretid $\Theta(1)$.

def f1(i):
  gjoerNoe()
  if i <= 1:
    return
  f1(i // 2)
  f2(i - 2)

def f2(i):
  gjoerNoe()
  if i <= 1:
    return
  f1(i // 2)

Hva er kjøretiden til f1(n)? (Tips: Ikke prøv å regne det ut nøyaktig.)

(10 %)

$\Theta(\log \log (n))$
$\Theta(\log (n))$
$\Theta(\sqrt{n})$
$\Theta(n)$
$\Theta(n \log (n))$
$\Theta(n \sqrt{n})$
$\Theta(n^2)$
Ingen av alternativene stemmer.

Din kommentar:
LF-forklaring:

$$T1(n) = \Theta(1) + T1(n/2) + T2(n-2), T1(1) = \Theta(1)$$ $$T2(n) = \Theta(1) + T1(n/2), T2(1) = \Theta(1)$$

$$T1(n) = \Theta(1) + T1(n/2) + \Theta(1) + T1((n-2)/2) = T1(n/2) + T1(n/2 - 1) + \Theta(1) \doteq 2 * T1(n/2) + \Theta(1)$$

Ser at $T1(n) = \Theta(n)$.

Oppgave 6

[ riktig ]a)

def funksjon1(n):
  if n > 0:
    funksjon1(n-42)
    funksjon1(42)
  gjorNoe(42)

Hva er kjøretiden til funksjonen hvis gjorNoe(n) har kjøretid $\Theta(n)$?

(10 %)

$O(1)$
$O(n)$
$O(\log n)$
$O(n \log n)$
$O(n^2)$
$O(n^3)$
Den vil aldri stoppe.

Din kommentar:
LF-forklaring: funksjon1(42) kaller funksjon1(42) som igjen kaller funksjon1(42).

[ riktig ]b)

def funksjon2(n):
  gjorNoe(n)
  if n >= 1:
    funksjon2(n//3)
    funksjon2(2n//3)

Hva er kjøretiden hvis gjorNoe(n) har kjøretid $\Theta(n)$?

(10 %)

$O(1)$
$O(n)$
$O(\log n)$
$O(n \log n)$
$O(n^2)$
$O(n^3)$
Den vil aldri stoppe.

Din kommentar:
LF-forklaring: Ved å bruke et rekursjonstre ser vi at det er n elementer på hvert nivå og høyden til treet er $\Theta(\log(n))$.

[ feil ]c)

def funksjon3(n):
  gjorNoe(n//6)
  if n > 0:
    funksjon3(n/2-2)
    funksjon3(n/2-3)

Hva blir kjøretiden hvis gjorNoe(n) har kjøretid $\Theta(n)$?

(10 %)

$O(1)$
$O(n)$
$O(\log n)$
$O(n \log n)$
$O(n^2)$
$O(n^3)$
Den vil aldri stoppe.

Din kommentar:
LF-forklaring: Vi bruker masterteoremet. Vi ser bort ifra $-2$ og $-3$ ved store verdier av $n$, og tilnærmer dermed rekurrensen $T(n) = 2T(n/2)+ \Theta(n)$. Vi får case $2$ av masterteoremet og kjøretid $\Theta(n \lg n)$.