Föreläsning 6

Question 1

Vad innebär dynamic programming?

Answer 1

Problemet delas upp i delproblem, vars lösningar kan användas för att spara beräkningar senare.

Question 2

Vad innebär pseudo-polynomial tidskomplexitet?

Answer 2

Tidskomplexiteten beror på en konstant multiplicerad med n, exempelvis O(n*W) där W är maxvikten i knapsack problem.

Question 3

Hur fungerar Bellman-Ford algoritmen? Vad är dess tidskomplexitet?

Answer 3

Bellman-Ford algoritmen används för att hitta den optimala vägen från en nod till alla andra i en graf genom dynamic programming. Bellman-Ford klarar av negativa kostnader i grafen.

1. Välj en rotnod, och sett dess vikt till 0. Sätt alla andra noders vikt till +inf.
2. För varje nod, se över dess kanters vikter och jämför vägens kostnad med den i tabellen
3. Fortsätt tills ingen skillnad sker, eller vi når n-1 iterationer

Tidskomplexitet: O(m*n)

Question 4

Hur görs sequence alignment (DNA exempelvis) mest effektivt?

Answer 4

Med dynamic programming, genom att sätta upp en NxM matris där N och M är mängden symboler i vardera sekvens

Question 5

Hur kan man identifiera negativa cykler med Bellman-Ford algoritmen?

Answer 5

Låt algoritmen köra n-1 steg. Om du nu kör ännu ett steg och det resulterar i en updatering måste det finnas en negativ cykel i grafen.