Sist endret: 23.09.2016  
 

Løsningsforslag - Rangering i lineær tid

[Oppgave] [Levering] [Løsningsforslag]

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

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

$O(n^2)$
$O(n\lg n)$
$\Omega(n)$
$\Omega(n\lg n)$
$\Theta(n\lg n)$

Din kommentar:
LF-forklaring:

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

Ja
Nei

Din kommentar:
LF-forklaring: Counting sort, radix sort og bucket sort er ikke generelle sorteringsalgoritmer, fordi de gjør antakelser om input.

[ riktig ]c) En stabil sorteringsalgoritme ... (7.1 %)

holder på den relative ordningen til elementer med like nøkler.
er en algoritme som gir samme output hver gang.
sørger for at programmet kjører stabilt.

Din kommentar:
LF-forklaring:

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

Selection sort, insertion sort, quicksort og radix sort
Insertion sort, heapsort og bucket sort
Bubble sort, heapsort og merge sort
Counting sort, radix sort og bucket sort

Din kommentar:
LF-forklaring:

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

Quicksort
Mergesort
Heapsort
Selection sort (in-place)

Din kommentar:
LF-forklaring:

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

det $k$-te elementet.
gjennomsnittselementet.
det midterste elementet.

Din kommentar:
LF-forklaring:

Oppgave 2

[ riktig ]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 %)

Vi må iterere forover over A.
Vi må iterere bakover over A.
Vi kan iterere i en tilfeldig rekkefølge over A.

Din kommentar:
LF-forklaring: For at Counting Sort skal være stabil, må vi iterere bakover.

[ riktig ]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 %)

$O(n)$ med Counting Sort
$O(n)$ med Bucket Sort
$O(n\lg n)$ med Quicksort

Din kommentar:
LF-forklaring: Se eksamen 2014, oppg 3a.

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

Bucket Sort
Quick Sort
Insertion Sort
Merge Sort

Din kommentar:
LF-forklaring: Merge Sort er den raskeste av de stabile sorteringsalgoritmene.

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

$\Theta(n^2)$
$\Theta(n)$
$\Theta(n\lg n)$
$\Theta(\lg n)$

Din kommentar:
LF-forklaring: I verste tilfelle vil alle elementene havne i samme bucket.

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

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

1
2
3
4
5
6

Din kommentar:
LF-forklaring:

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

51323, 10395, 31337, 12357
10395, 12357, 31337, 51323
51323, 31337, 12357, 10395
12357, 10395, 51323, 31337

Din kommentar:
LF-forklaring:

Oppgave 4

[ feil ]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 %)

1 og 2
1 og 3
2 og 4
Bare 1
Bare 2
Bare 3
Bare 4

Din kommentar:
LF-forklaring:

[ feil ]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 %)

2 og 3
1 og 2
1, 2 og 4
1 og 4
3 og 4
2 og 4
Bare 1
Bare 2
Bare 3
Bare 4

Din kommentar:
LF-forklaring: