Sist endret: 23.09.2016  
 
Øvinger
 
Blackboard
Piazza
 
IDI
NTNU
 
haakowar logget inn
Poengoversikt

Løsningsforslag - Grådige algoritmer

[Oppgave] [Levering] [Løsningsforslag]

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

[ riktig ]a) Grådige algoritmer brukes til å løse optimaliseringsproblemer. Sant eller usant? (2.4 %)

Sant
Usant

Din kommentar:
LF-forklaring:

[ riktig ]b) Hvis man kan løse et problem med dynamisk programmering kan man alltid løse det med en grådig algoritme. Sant eller usant? (2.4 %)

Sant
Usant

Din kommentar:
LF-forklaring: F.eks. lar ikke 0/1 knapsack seg løse grådig.

[ feil ]c) Grådige algoritmer er garantert $O(n)$. Sant eller usant? (2.4 %)

Sant
Usant

Din kommentar:
LF-forklaring: Det er ingenting generelt iboende med grådige algoritmer som gjør at de må være $O(n)$. Et eksempel på en algoritme som ikke er det er Huffman.

[ riktig ]d) Grådige algoritmer tar lokalt optimale beslutninger. Sant eller usant? (2.4 %)

Sant
Usant

Din kommentar:
LF-forklaring: Definisjonen av grådig algoritme.

[ riktig ]e) En grådig algoritme må vite løsningen på alle mulige delproblemer før den kan gjøre det grådige valget. Sant eller usant? (2.4 %)

Sant
Usant

Din kommentar:
LF-forklaring: Det er nettopp det den ikke trenger å gjøre når den tar lokalt optimale beslutninger.

[ riktig ]f) En grådig algoritme kan ombestemme seg senere når den har funnet ut mer om løsningene på delproblemene. Sant eller usant? (2.4 %)

Sant
Usant

Din kommentar:
LF-forklaring: Den må ta beslutninger lokalt uten å ta løsninger på delproblemer i betraktning.

[ riktig ]g) Vi må ha overlappende delproblemer for å bruke en grådig algoritme. Sant eller usant? (2.4 %)

Sant
Usant

Din kommentar:
LF-forklaring:

Oppgave 2

[ riktig ]a) Hvilke to egenskaper må et problem ha for å vi kan bruke en grådig algoritme? (2.4 %)

Grådighetsegenskapen og polynomisk kjøretid
Syklisk og optimal substruktur
Grådighetsegenskapen og optimal substruktur
Polynomisk kjøretid og problemet lar seg redusere til bare ett delproblem
Ingen av delene

Din kommentar:
LF-forklaring:

[ riktig ]b) Hvorfor kan det være ønskelig å bruke en grådig algoritme istedenfor dynamisk programmering? (2.4 %)

Algoritmen kan være enklere å implementere og ha bedre kjøretid.
For å få utnyttet overlappende delproblemer på en bedre måte
Fordi vi ønsker å løse problemet rekursivt - noe vi ikke får til med dynamisk programmering

Din kommentar:
LF-forklaring:

[ feil ]c) Grådighetsegenskapen (the greedy-choice property) sier... (2.4 %)

at vi kan finne en global optimal løsning ved å ta mange små valg underveis
at vi kan finne en global optimal løsning ved å ta lokalt optimale valg
at algoritmer som tar lokalt optimale valg er grådige
at algoritmer som er grådige tar lokalt optimale valg

Din kommentar:
LF-forklaring:

[ feil ]d) Hva har grådige algoritmer og dynamisk programmering til felles? (2.4 %)

Begge løser problemer ovenfra og ned
Begge løser problemer nedenfra og opp
Begge utnytter optimal delstruktur
Begge utnytter overlappende delproblemer

Din kommentar:
LF-forklaring:

Oppgave 3

Denne oppgaven handler om aktivitetsutvalg (se kapittel 16.1 i boka).

Du ønsker å velge ut så mange aktiviteter som mulig fra en mengde av åtte aktiviter uten at noen overlapper. Aktivitetene har følgende start og sluttidspunkter:

$s_1=12,s_2=12,s_3= 6,s_4=15,s_5=20,s_6= 0,s_7= 4,s_8= 6$
$f_1=14,f_2=17,f_3=10,f_4=18,f_5=24,f_6=22,f_7= 7,f_8= 9$

[ feil ]a) Gitt at du hadde brukt RECURSIVE-ACTIVITY-SELECTOR (side 419) til å løse problemet. Hvilken aktivitet ville du først valgt ut til å være i løsningsmengden $A$? (2.4 %)

1
2
3
4
5
6
7
8

Din kommentar:
LF-forklaring: Denne har tidligste avslutningstid.

[ feil ]b) Gitt at du hadde brukt GREEDY-ACTIVITY-SELECTOR (side 421) til å løse problemet. Hvilken aktivitet ville du først valgt ut til å være i løsningsmengden $A$? (2.4 %)

1
2
3
4
5
6
7
8

Din kommentar:
LF-forklaring: Denne har tidligste avslutningstid.

[ feil ]c) Gitt at du hadde brukt GREEDY-ACTIVITY-SELECTOR (side 421) til å løse problemet. Hva blir løsningen? Aktiviter i kronologisk rekkefølge. (7.2 %)

7, 8, 1, 4, 5
7, 1, 4, 5
8, 1, 5
0, 2, 5
5, 4, 1, 8
5, 4, 1, 3

Din kommentar:
LF-forklaring:

[ feil ]d) Hva forteller teorem 16.1 i boka oss om aktivitetsutvalg-problemet? (4.8 %)

At det ikke lar seg løse
At man må bruke dynamisk programmering
At det har optimal substruktur
At det har grådighetsegenskapen

Din kommentar:
LF-forklaring:

[ feil ]e) Hvordan beviser de teorem 16.1 i boka? (12 %)

De starter med en optimal løsning og viser at denne allerede må inneholde det grådige valget
De starter med en optimal løsning, bytter ut en aktivitet i løsningen med det grådige valget og viser at den nye løsningen er like bra
De starter med en suboptimal løsning, gjør et grådig valg og viser at den nye løsningen blir optimal
De starter med en vilkårlig løsning og viser at en grådig løsning må være minst like bra
De starter med en optimal løsning og viser at den hadde blitt dårligere hvis den ikke inneholdt det grådige valget

Din kommentar:
LF-forklaring:

Oppgave 4

Denne oppgaven handler om Huffman-koder (se kapittel 16.3 i boka).

Du ønsker å finne optimal prefix-kode for en streng. Strengens alfabet representeres ved bokstavene a til g. Frekvensene er som følger:

$a.freq=5,b.freq=2,c.freq=20,d.freq=255,e.freq=10,f.freq=22,g.freq=35,$

[ feil ]a) Gitt at vi velger å kode alfabetet på følgende måte: $a:00001,b:001,c:1,d:00000,e:0001,f:010,g:011,$. Hvor mange bits må vi bruke for å representere strengen? (4.8 %)

1537
1689
1453
1220

Din kommentar:
LF-forklaring:

[ riktig ]b) Du bruker Huffmans algoritme. Hvilke to bokstaver slår du sammen først? (2.4 %)

$a$ og $b$
$d$ og $g$
$c$ og $e$
$a$ og $e$

Din kommentar:
LF-forklaring:

[ riktig ]c) Du bruker Huffmans algoritme. Hvor mange bits blir $a$ kodet til? (2.4 %)

1
2
3
4
5
6

Din kommentar:
LF-forklaring:

[ riktig ]d) Du bruker Huffmans algoritme. Hvor mange bits blir $b$ kodet til? (2.4 %)

1
2
3
4
5
6

Din kommentar:
LF-forklaring:

[ riktig ]e) Du bruker Huffmans algoritme. Hvor mange bits blir $c$ kodet til? (2.4 %)

1
2
3
4
5
6

Din kommentar:
LF-forklaring:

[ riktig ]f) Du bruker Huffmans algoritme. Hvor mange bits blir $d$ kodet til? (2.4 %)

1
2
3
4
5
6

Din kommentar:
LF-forklaring:

[ riktig ]g) Du bruker Huffmans algoritme. Hvor mange bits trenger vi for kode strengen med løsningen du finner? (2.4 %)

446
450
452
561
603
723
734
776
895

Din kommentar:
LF-forklaring:

[ feil ]h) Hva forteller lemma 16.2 om prefix-kode-problemet? (2.4 %)

At det ikke lar seg løse
At man må bruke dynamisk programmering
At det har optimal substruktur
At det har grådighetsegenskapen

Din kommentar:
LF-forklaring:

[ feil ]i) Hvordan beviser de lemma 16.2 i boka? (9.6 %)

De starter med et tre som representerer en optimal løsning og viser at nodene som representerer det grådige valget må ligge på maks dybde i treet
De starter med et tre som representerer en optimal løsning og viser at det hadde blitt dårligere hvis den ikke inneholdt det grådige valget
De starter med et tre som representerer en optimal løsning og viser at denne allerede må inneholde det grådige valget
De starter med et tre som representerer en optimal løsning, bytter om på noder slik at treet inneholder det grådige valget og viser at den nye løsningen er like bra
De starter med et tre som representerer en suboptimal løsning, gjør et grådig valg og viser at den nye løsningen blir optimal
De starter med et tre som representerer en vilkårlig løsning og viser at en grådig løsning må være minst like bra

Din kommentar:
LF-forklaring:

[ feil ]j) Hva forteller lemma 16.3 om prefix-kode-problemet? (2.4 %)

At det ikke lar seg løse
At man må bruke dynamisk programmering
At det har optimal substruktur
At det har grådighetsegenskapen

Din kommentar:
LF-forklaring:

Oppgave 5

[ riktig ]a) 0/1 knapsack har optimal substruktur. Sant eller Usant? (2.4 %)

Sant
Usant

Din kommentar:
LF-forklaring:

[ riktig ]b) 0/1 knapsack har grådighetsegenskapen. Sant eller Usant? (2.4 %)

Sant
Usant

Din kommentar:
LF-forklaring:

[ riktig ]c) Fractional knapsack har optimal substruktur. Sant eller Usant? (2.4 %)

Sant
Usant

Din kommentar:
LF-forklaring:

[ riktig ]d) Fractional knapsack har grådighetsegenskapen. Sant eller Usant? (2.4 %)

Sant
Usant

Din kommentar:
LF-forklaring: