Give pseudocode that performs the traceback to construct an LCS from a filled dy

Question

Give pseudocode that performs the traceback to construct an LCS from a filled dynamic programming table without using the “arrows”, in O(n + m) time.

2. Suppose we are given a “chain” of n nodes as shown below. Each node i is “neighbors” with the node to its left and the node to its right (if they exist). An independent set of these nodes is a subset of the nodes such that no two of the chosen nodes are neighbors. In the below example, the first and fourth vertices form an independent set, but the first, third, and fourth vertices do not (because the third and fourth are neighbors). Now suppose each node has a positive weight. We are interested in computing an independent set such that the sum of the weights of the chosen nodes are as large as possible. In the example, the optimal solution is to choose the second and fourth vertices for a weight of 30.

(15) - (20) - (7) - (10)

(a) A natural attempt of a greedy algorithm for this problem is to take the vertex with the largest weight, then delete that vertex’s neighbors (because they cannot also be in an independent set). Repeat this process until there are no more vertices which can be included. Give a counterexample which shows that this algorithm may not give an optimal solution.

(b) Let a[i] denote the weight of a maximum-weight independent set when only considering the first i vertices of the path. Give the values a[1], a[2], a[3], and a[4] for the example given above.

(c) Define a recursive definition of a[i]. Don’t forget the base case.

(d) Give a bottom-up dynamic programming algorithm based off your recursive definition. What is the running time of your algorithm?

Explanation / Answer

HI, Please find my implementation of Q1 => printing LCS from generated table

1) Construct L[m+1][n+1] table => using lcs algorithm

2) The value L[m][n] contains length of LCS. Create a character array lcs[] of length equal to the length of lcs plus 1 (one extra to store ).

2) Traverse the 2D array starting from L[m][n]. Do following for every cell L[i][j]
   .a) If characters (in X and Y) corresponding to L[i][j] are same (Or X[i-1] == Y[j-1]), then include this character as part of LCS.
   .b) Else compare values of L[i-1][j] and L[i][j-1] and go in direction of greater value.

void printLCS(int L[m][n]){
   // Start from the right-most-bottom-most corner and
// one by one store characters in lcs[]
int i = m, j = n;
while (i > 0 && j > 0)
{
// If current character in X[] and Y are same, then
// current character is part of LCS
if (X[i-1] == Y[j-1])
{
lcs[index-1] = X[i-1]; // Put current character in result
i--; j--; index--; // reduce values of i, j and index
}

// If not same, then find the larger of two and
// go in the direction of larger value
else if (L[i-1][j] > L[i][j-1])
i--;
else
j--;
}

// Print the lcs
cout << "LCS of " << X << " and " << Y << " is " << lcs;
}

Please repost other questions separately.

Please let me know in case of any issue in Q1

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.