Sist endret: 23.09.2016  
 

Teorioppgave - Rangering i lineær tid

[Oppgave] [Levering] [Løsningsforslag]

Innleveringsfrist: 25.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

a) Sammenligningsbaserte sorteringingsalgoritmer har en worst-case på ... (7.1 %)


b) Det finnes generelle sorteringsalgorimer med worst-case kjøretid $\Theta(n)$. (7.1 %)


c) En stabil sorteringsalgoritme ... (7.1 %)


d) Hvilket av alternativene under består kun av sammenlikningsbaserte algoritmer? (7.1 %)


e) Hvilken av følgende algoritmer er stabil? (7.1 %)


f) Medianen i ei sortert liste er ... (7.1 %)


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

Oppgave 2

a) Se på figur 8.2 s. 195 i Cormen. I det algoritmen setter inn elementer i B, itereres det over A. Hva er rett? (7.1 %)


b) Du ønsker å sortere en sekvens A av reelle tall som er fordelt etter en gitt sannsynlighetsfunksjon med kjent kumulativ sannsynlighetsfunksjon. Hva er den beste kjøretiden du kan få, i gjennomsnitt? (7.1 %)


c) Radix Sort bruker en annen sorteringsalgoritme som "del-algoritme". Hvilken av følgende algoritmer fungerer best? (7.1 %)


d) Hva er worst-case kjøretiden til Bucket Sort, slik den er beskrevet i Cormen? (7.1 %)


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

Oppgave 3

En av eksamensvaktene under fjorårets algdat-eksamen bestemte seg for å bruke radix sort for å sortere besvarelsene etter kandidatnummer, men ble litt forvirret rundt hvordan algoritmen faktisk fungerer. Som den oppegående studenten du er, bestemmer du deg for å hjelpe. Eksamensvakten har 10 bunker nummerert 0 til 9 som besvarelsene fordeles i. Gitt følgende kandidatnr:
10219, 12543, 51323, 10395, 31337, 11235, 12357, 86123, 19023

a) Etter to iterasjoner, hvor mange besvarelser ligger i bunke nr 2? (7.1 %)


b) Etter tre iterasjoner, hvilken rekkefølge har besvarelsene i bunke nr 3? (7.1 %)


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

Oppgave 4

a) Hvilke(t) utsagn er sant om Randomized-Select?
1. Forventet kjøretid er $O(n)$
2. Worst-case kjøretid er $\Theta(n^2)$
3. Worst-case kjøretid er $\Theta(n)$
4. Forventet kjøretid er $O(n\lg n)$
(7.1 %)


b) Hvilke(t) utsagn er sant om Select?
1. Det er en algoritme som er mest av teoretisk interesse og sjeldent brukt i praksis.
2. Den har garantert worst-case $O(n)$ for alle sekvenser.
3. Den kan bare finne medianen i en sekvens.
4. Den løser seleksjonsproblemet.
(7.1 %)


Ø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'.