CS590-homework 4 Dynamic Programming, Greedy Algorithms Solved

The class random_generator has been updated (random_generator.h and ran- 
dom_generator.cc) by a member function which generates random strings of a fixed 
length using the a given number of characters from the alphabet, starting with "a".

 char* random.string.m(int n, int no_ch)
The function allocates n + 1 characters. The first n characters (0 ...n — 1) are chosen at random using the first no_ch characters from the alphabet start­ing with "a" (e.g., for no_ch = 4 the characters are randomly chosen out of {"a","b","c","d"}). The n-th character is set to 0 in order to mark the end of the string.

Dynamic programming

The dynamic programming Smith-Waterman algorithm is matching sequences recur­sively defined as follows, given X = XI,... , xn (along table rows) and Y = ye, ... , y,n (along table columns)

M(i, 0) = 0, for all 0 < i < n M(0,j) =0, for all 0 < j <m

M(i — 1, j — 1) + 2 if xi = y; 
M(i — 1, j — 1) — 1 if x, 0 yi

M(i' -1) — max M(i — 1, j) — 1 if "-" is inserted into Y M(i, j — 1) — 1 if "-" is inserted into X

The function M(i,j) defines a so called matching score for the partial sequences X, and it,. If in the recursive definition of M the maximum value is due to the third or fourth line, you have to insert the character "-" into either X or Y in order to reconstruct the matching sequences X' and Y'. Similar to the LCS problem we need only need a table to store the M(i, j) values, but an additional table that allows us to later generate X' and Y' from X and Y.

 

 
Example 1
Example 2
Example 3
x

x' 
y,

v
abababda
cacacccbab
cdbaabbdca
a-bababda
ca-cacccbab
c-dba--abbdca
acbabab-a
cadaadcc---
cadcacca-bd--
acbababa
bccadaadcc
cadcaccabd
M(n,m)
12
4
5
 

 
Example 4
Example 5 
x

X : r

Y
caacbdacca
dcacccbbba
caacb-dacc-a
dcacccb-bba
c--cbcd-ccba
dca--badba
bccbcdccba
aadcabadba
M(n,m)
 
7
 

Implement the bottom-up version of the Smith-Waterman algorithm given by the recursive definition of the function M (as seen on the slides).
Implement the top-down with memoization version of the Smith-Waterman algorithm given by the recursive definition of the function 
Notes:

How do you initialize the necessary tables given the definition of  Keep in mind that you have to able to determine whether or not you already computed a table value (memoization).
Values could be negative, but is there a limit for how small they can get?
Implement the function void PRINT-SEQ-ALIGN-X ( ...) that takes a number of parameters and then recursively prints the matching sequence that is derived from  Implement a separate function void PRINT-SEQ-ALIGN-Y( . ) that recursively prints the matching sequence that is derived from Y.
Find the maximum alignment for X = dcdcbacbbb and Y = acdccabdbb by using the Smith-Waterman algorithm (see slides). Execute the pseudocode algorithm and fill the necessary tables H and P in a bottom-up fassion. Re­construct the strings X' and Y' using the tables H and 
(7+20+8+15 = 50 points)

Exercise 15.1-2 Show, by means of a counterexample, that the following "greedy" strategy does not always determine an optimal way to cut rods. Define the density of a rod of length i to be that is, its value per inch. The greedy strategy for a rod of length 71 cuts off a first piece of length i, where 1 < i < n, having maximum density. It then continues by applying the greedy strategy to the remaining piece of length n



Exercise 15.1-5 The Fibonacci numbers are defines by recurrence (3.22). Give an 0(n) time dynamic-programming algorithm to compute the n-th Fibonacci number. Draw the subproblem graph. How many vertices and edges are in the graph?


Exercise 15.4-1 Determine              an        LCS           of         (1, 0, 0, 1, 0, 1, 0,1)            and

(0, 1,0,1,1,0,1,1,0).