Algos Problem 5: Comparing Sequences

Question 1

Recursive Change Algorithm?

Given the denominations 6, 5, and 1, what is the minimum number of coins needed to change 9 cents?

Answer 1

MinNumCoins(9) = min {

MinNumCoins(9-6)+1 = MinNumCoins(3)+1 ;
MinNumCoins(9-5)+1 = MinNumCoins(4)+1 ;
MinNumCoins(9-1)+1 = MinNumCoins(8)+1

Question 2

How do you find a local alignment?

Answer 2

Englisch
- write a dynamic programming matrix, any negative values should be adjusted to zero
- The score of the best local alignment is the largest value in the entire array.
- To find the actual local alignment:
- start at an entry with the maximum score
- traceback as usual
- stop when we reach an entry with a score of 0

Deutsch
- ein Dynamische-Programmier-Matrix schreiben. negative Werte werden zu Null
- als Endknoten fuer das lokale Alignment den Knoten mit groessten Wert nehmen
- von denen geht man rueckwaerts (backtracking) bis der Knotenwert erstmals 0 wird
- Grund: nach diesen Knoten wird score nur wieder kleiner. Wir wollen bester score, also hoeren wir dort wo Maximum ist auf

Question 3

Wie geht man vor, beim Alignment einen Knotenwert zu berechnen ?

Answer 3

Vorgehensweise Knotenwert:
- Knotenwert = Vorgaengerknotenwert + Kantenwert
- Alle moeglicher Knotenwerte berechnen: von links, von diagonal, von oben
- Hoechsten Wert auswaehlen