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?

Answer 1

/I Function prototype placed before the function is used double getArea (double); // without the parameter nane int max(int, int); You could optionally include the parameter names in the function prototype. The names will be ignored by the compiler, but serve as documentation. For example, // Function Prototype double getArea (double radius); // parameter names are ignored, but serve as documentation int max(int number1, int number2);

/* Testing max function (TestMaxFunction.cpp) #include <iostream» using namespace std; 3 4 5 int maximum(int, int); // Function prototype (declaration) 7 int main() 8 cout << maximum(5, 8) << endl; /1 Call maximum() with literals int a - 6, b-9,c c = maximum(a, b); cout << c << endl; 10 /I Call maximum() with variables 12 13 14 cout << maximum(c, 99) << endl; // Call maximum() 15 16 17 // Function definition 18 IIA function that returns the maximum of two given int 19 int maximum(int num1, int num2) 2臼 return (num1>num2) ? num1 num2; 21

Boolean Functions A boolean function returns a bool value (of either true or false) to the caller Suppose that we wish to write a function called isodd() to check if a given number is odd. 2 *Test Boolean function (BooleanfunctionTest.cpp). 4 #include <iostream> 5 using namespace std; 7 // Function Prototype 8 bool isodd(int); 10 int main() cout << boolalpha; I/ print bool as true or false cout << isodd (5) << endl; // true cout << isodd (6) <<endl; // false cout << isodd (-5) << endl; // false 12 13 14 15 16 17 bool isodd(int number) 18 19 20 21 if (number % 2-1) { return true; else return false 23