Answer Happy

Question 3: Backtracking and Branch-and-Bound [25 Points] Consider the following backtracking algorithm for solving the 0-1 Knapsack Problem: Backtracking_Knapsack (val, wght, Cn) Create two arrays A1 and A2 each of size n and initialize all of their entries to zeros Initialize the attributes takenVal, untakenVal and takenWght in each of A1 and A2 to zero totalSum = 0 for i = 1 ton totValSum += vallo Find Solutions (1) Print: Contents of A1 l/prints the actual contents of A1 Print: Contents of A2 l/prints the actual contents of A2 Find Solutions (1) 1 if (A1.takenWght > C) 2 Print: Backtrack at i I/prints the actual value of i 3 return 4 if (i == n+1) Print: Check leaf with soln A1 l/prints the actual contents of A1 if (A1.takenVal > A2 takenVal) 7 Print: Copy A1 into A2 l/prints the actual contents of both arrays 8 Copy A1 into A2 9 5 6 OOOO return 10 Takeltem(A1,0) 11 Find Solutions (i+1) 12 UndoTakeltem(A1, i) 13 DontTakeltem(A1,I) 14 Find Solutions (i+1) Small routines: Takeltem(A. ) A UndoDontTakeltem( AD) A.untakenVal = valli val is array of values, wght is array of weights, C is knapsack capacity and n is number of items. (a) Show next to the above code the output that it prints for the following input instance: Item 1: weight = 6 Kg, value = $8 Item 2: weight = 3 kg, value = 54 Item 3: weight = 7 Kg, value = $9 Capacity = 10 Assume that each print statement appears on a separate line in the output and that each print statement prints the contents of each array in it as a bit string. For example, the print statement on Line 8 of Find Solutions() may print something like this: Copy 101 into 001. (10 points)

(b) Suppose that the above code was applied to an instance with n items and that Line 2 never got executed, how many times will each of the following lines get executed? Give the exact value in terms of n, not the asymptotic value. Show your calculations and briefly explain them. (4 points) Line 6: Line 10: (c) In Assignment 4, you have implemented the following three upper bounds: UB1: Sum the values of taken items and undecided items UB2: Sum the values of taken items and the undecided items that fit in the remaining capacity UB3: Sum the values of taken items and the solution to the remaining sub-problem solved as a fractional knapsack problem. Answer the following questions: 1. Add to the above code the lines needed to implement UB1 efficiently. (2 points) 2. Which is a more precise upper bound, UB1 or UB2? (1 point) 3. Which upper bound will generally lead to visiting more tree nodes, UB1 or UB2? (1 point) 4. What was the pre-processing that you needed to do once before starting the search so that UB3 can be computed efficiently? Why was that pre-processing necessary? (2 points) 5. What was the running time of the pre-processing mentioned in the previous question? What was the processing time per tree node with this preprocessing done before the search? (2 points) 6. Assuming that the items are sorted by value per unit weight in descending order, will the following algorithm compute a valid upper bound that results in a correct B&B algorithm? Explain your answer. - Go through undecided items and add each undecided item to the knapsack until you reach an undecided item that does not fit into the remaining capacity. When you add an undecided item, subtract its weight from the remaining capacity. Add that undecided item that does not fit but stop at that point and don't take any of the remaining undecided items. Compute the upper bound as the sum of the values of the undecided items that you have added in the above steps plus the sum of taken item values. For example if the remaining capacity is 10 and undecided items have weights 3, 4, 5, 7, and values 8, 9, 10, 11, respectively, the item with weight 5 will be the last item that does not fit. So, compute the upper bound as the sum of 8, 9 and 10 plus the sum of taken item values (3 points)