Sist endret: 23.09.2016  
 

Teorioppgave - Grådige algoritmer

[Oppgave] [Levering] [Løsningsforslag]

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


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

Oppgave 2

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


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

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$

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


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

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

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


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

Oppgave 5

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


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