Sist endret: 23.09.2016  
 

Teorioppgave - Splitt og hersk

[Oppgave] [Levering] [Løsningsforslag]

Innleveringsfrist: 18.09.2017 15:00

NB! Du er ikke innlogget. Logg inn for å få frem det du har skrevet tidligere.
Dersom du har levert øvingen fra før, vil det du har levert bli slettet dersom du klikker på 'Vis alternativer'

NB! Det du skriver i tekstfeltene blir ikke vurdert som en del av besvarelsen. De er kun til eget bruk, før du velger 'Vis alternativer'.

Oppgave 1

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 %)


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 %)


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

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)$$

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 %)


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

Oppgave 3

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 %)


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

Oppgave 4

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 %)


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

Oppgave 5

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 %)


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

Oppgave 6

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 %)


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 %)


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 %)


Ønsker gjennomgang: (Sett kryss dersom du ønsker at oppgaven ovenfor skal bli gjennomgått på øvingsforelesning)

Stikkord til forelesning

Du får mer utbytte av en forelesning dersom du på forhånd vet helt overfladisk hva den handler om. Du bør ane hva stikkordene for neste forelesning betyr.
Skriv gjerne ned kommentarer til stikkordene for neste forelesning og se over dem på neste teoriøving.

Kommentarer til stikkordene er kun til eget bruk og blir ikke vurdert av andre.

Det er ikke lagt inn noen stikkord for neste forelesning.


Eventuelt tidligere innlevering vil bli OVERSKREVET om du klikker på 'Vis alternativer'.