[Oppgave] [Levering] [Løsningsforslag]
Innleveringsfrist: 13.11.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) Hvilken kjøretid (asymptotisk) har Floyd-Warshall implementasjon vi finner i Cormen (s. 695)? (4 %)
b) Hvor mye plass bruker Floyd-Warshall algoritmen vi finner i Cormen (s. 695)? (4 %)
c) Kan Floyd-Warshalls algoritme brukes til å finne ut om det finnes negative sykler i en graf? (4 %)
Vi skal kjøre Floyd-Warshalls algoritme (slik den er beskrevet i Cormen) på følgende graf: Gitt $D^{(0)}$:
Vi skal kjøre Floyd-Warshalls algoritme (slik den er beskrevet i Cormen) på følgende graf:
Gitt $D^{(0)}$:
a) Hvordan ser $D^{(1)}$ ut? (4 %)
b) Hvordan ser $D^{(3)}$ ut? (4 %)
c) Hvordan ser $D^{(5)}$ ut? (4 %)
d) Hvilken sti vil Floyd-Warshall gi som korteste sti fra node 1 til node 4? (4 %)
e) Hva er tolkningen av elementet i rad $i$, kolonne $j$ i matrisen $D^{(5)}$? (4 %)
a) Gitt algoritmen TRANSITIVE-CLOSURE($G$) på side. 698 i Cormen. Kan vi ved hjelp av denne algoritmen finne ut om en rettet graf er asyklisk? (4 %)
b) Hvis vi endrer linje 5 i TRANSITIVE-CLOSURE($G$) til: $\hspace{2cm} \textbf{ if } \text{ (}i,j\text{) } \text{ is in }G.E:$ Vil det nå være mulig å bruke denne algoritmen for å finne ut om en rettet graf er asyklisk? (4 %)
Hva er teoretisk raskeste algoritme (best O) for "korteste vei, alle til alle" - problemet i følgende grafer? Merk: For Dijkstras regner vi med at Extract-Min-operasjonen tar O(V) tid.
Hva er teoretisk raskeste algoritme (best O) for "korteste vei, alle til alle" - problemet i følgende grafer?
Merk: For Dijkstras regner vi med at Extract-Min-operasjonen tar O(V) tid.
a) En rettet graf uten sykler og uten negative kanter. (8 %)
b) Assymptotisk strammeste kjøretid for de(n) raskeste algoritmen(e) i a) er? (4 %)
c) En rettet graf uten sykler og med negative kanter. (8 %)
d) Assymptotisk strammeste kjøretid for de(n) raskeste algoritmen(e) i c) er? (4 %)
e) En graf med sykler og uten negative kanter. (8 %)
f) Assymptotisk strammeste kjøretid for de(n) raskeste algoritmen(e) i e) er? (4 %)
g) En graf med sykler og med negative kanter(men uten negative sykler) (8 %)
h) Assymptotisk strammeste kjøretid for de(n) raskeste algoritmen(e) i g) er? (4 %)
i) En graf med negative sykler. Her holder det ikke å kun oppdage at det finnes negative sykler (8 %)
j) Assymptotisk strammeste kjøretid for de(n) raskeste algoritmen(e) i i) er? (4 %)