[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.
a) Grådige algoritmer brukes til å løse optimaliseringsproblemer. Sant eller usant? (2.4 %)
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 %)
c) Grådige algoritmer er garantert $O(n)$. Sant eller usant? (2.4 %)
d) Grådige algoritmer tar lokalt optimale beslutninger. Sant eller usant? (2.4 %)
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 %)
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 %)
g) Vi må ha overlappende delproblemer for å bruke en grådig algoritme. Sant eller usant? (2.4 %)
a) Hvilke to egenskaper må et problem ha for å vi kan bruke en grådig algoritme? (2.4 %)
b) Hvorfor kan det være ønskelig å bruke en grådig algoritme istedenfor dynamisk programmering? (2.4 %)
c) Grådighetsegenskapen (the greedy-choice property) sier... (2.4 %)
d) Hva har grådige algoritmer og dynamisk programmering til felles? (2.4 %)
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$
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$
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 %)
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 %)
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 %)
d) Hva forteller teorem 16.1 i boka oss om aktivitetsutvalg-problemet? (4.8 %)
e) Hvordan beviser de teorem 16.1 i boka? (12 %)
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,$
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,$
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 %)
b) Du bruker Huffmans algoritme. Hvilke to bokstaver slår du sammen først? (2.4 %)
c) Du bruker Huffmans algoritme. Hvor mange bits blir $a$ kodet til? (2.4 %)
d) Du bruker Huffmans algoritme. Hvor mange bits blir $b$ kodet til? (2.4 %)
e) Du bruker Huffmans algoritme. Hvor mange bits blir $c$ kodet til? (2.4 %)
f) Du bruker Huffmans algoritme. Hvor mange bits blir $d$ kodet til? (2.4 %)
g) Du bruker Huffmans algoritme. Hvor mange bits trenger vi for kode strengen med løsningen du finner? (2.4 %)
h) Hva forteller lemma 16.2 om prefix-kode-problemet? (2.4 %)
i) Hvordan beviser de lemma 16.2 i boka? (9.6 %)
j) Hva forteller lemma 16.3 om prefix-kode-problemet? (2.4 %)
a) 0/1 knapsack har optimal substruktur. Sant eller Usant? (2.4 %)
b) 0/1 knapsack har grådighetsegenskapen. Sant eller Usant? (2.4 %)
c) Fractional knapsack har optimal substruktur. Sant eller Usant? (2.4 %)
d) Fractional knapsack har grådighetsegenskapen. Sant eller Usant? (2.4 %)