[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.
Denne oppgaven handler om sorteringsalgoritmer.
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 %)
Ingen av alternativene stemmer.
b) Vi ønsker å sortere en liste med lavest mulig minneforbruk. Hvilken algoritme er best? (5 %)
c) Vi oppnår worst-case tid for quicksort hvis listen allerede er sortert. (5 %)
d) Quicksort forbruker $O(1)$ ekstra minne i tillegg til det minnet som trengs for å lagre tallene som skal sorteres. (5 %)
e) All input kan gi worst-case kjøretid for randomized-quicksort. (5 %)
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)$$
Gitt rekurrensen:
Dersom vi skulle benyttet oss av substitusjonsmetoden og antatt at:
a) Hva håper vi på å kunne bevise? (5 %)
b) Hvis du anvender master-teoremet på denne rekurrensen, hvilket tilfelle tilhører den? (5 %)
c) Hva blir kjøretiden? (Du kan velge fremgangsmåte selv) (5 %)
d) Hvis vi bytter ut $n^3$ med $n^5$, hvilket case får vi hvis vi vil bruke masterteoremet? (5 %)
Løs denne oppgaven ved hjelp av variabelskifte. Husk at $n^\frac{1}{2} = \sqrt{n}$.
a) Løs rekurrensen gitt ved: $T(n) = T(n^\frac{1}{2}) + 1$ (5 %)
Løs denne oppgaven ved hjelp av rekursjonstrær.
a) Vi har en rekurrens $T(n) = T(n/3) + T(n/2) + n$, $T(1) = 1$. Hva er høyden til rekursjonstreet? (10 %)
Denne oppgaven handler om kjøretidsanalyse.
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 %)
Funksjonen gjoerNoe() har kjøretid $\Theta(1)$.
gjoerNoe()
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.)
f1(n)
$$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)$.
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 %)
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)$?
gjorNoe(n)
funksjon1(42)
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 %)
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)$?
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 %)
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)$?