Homework 6 Solution

For the programming problem below, include in your hardcopy submission a listing of your algorithm and of the output. Please follow the electronic submission instructions.




1. (U&G-required) [100 points]




Assume that you are given a task of managing the placement of commercial advertisements along a freeway that runs from west to east for a distance of D miles. The freeway has a set of n possible sites for the advertisement locations, given by positions x1, x2, … ,xn along the freeway, all within the interval [0, D], measured in miles from the western end. Placing an advertisement at a location xi will earn you a revenue ri 0. The rules for placing the advertisement boards require that no two commercials can be placed within less than or equal to 5 miles of each other. Your job is to place the advertisements at a subset of the possible sites in such a way that you maximize your total revenue. Develop a dynamic programming algorithm that finds the optimal value and the optimal solution for this problem using the steps outlined below.




[20 points] Write a recursive formula of an optimal solution (i.e., define the variable that you wish to optimize and explain how a solution to computing it can be obtained from solutions to subproblems).



Submit: the recursive formula, along with definitions and explanations on what is computed.

[30 points] Write an algorithm that computes the optimal value to this problem, based on the recurrence above. Implement your algorithm in C/C++ and run it on the following values:
D = 20, n = 4




{x1, x2, x3, x4} = {6, 7, 12, 14} {r1, r2, r3, r4} = {5, 6, 5, 1}




Submit:




A printed version of the algorithm



A printout of the table that contains the solutions to the subproblems, run on the values given above (print the entire table!)
The optimal value computed by your algorithm






[20 points] Update the algorithm you developed at point (b) to enable the reconstruction of the optimal solution, i.e., at which locations you choose to place the commercial advertisements for an optimal solution. (Hint: use an auxiliary table like we did in the examples in class.) Include these updates in your algorithm implementation from point (b).



Submit:




A printed version of the algorithm



A printout of the values that you obtain in the table containing the additional information needed to reconstruct the optimal solution, run on the values given above (print the entire table)



[30 points] Using the additional information computed at point (c), write an algorithm that outputs the locations you choose to place the commercial advertisements in the optimal solution. Implement this algorithm in C/C+.



Submit:




A printed version of the algorithm



A printout of the solution to the problem given by the numerical values in point



(b).

(G-required) [20 points] Show how the algorithm MATRIX-CHAIN-ORDER discussed in class computes the number of scalar multiplications for the product of the following three matrices (i.e., give the values in table “m” as computed by the algorithm): A: size 4x3



B: size 3x5




C: size 5x2







Extra credit




[20 points] Answer the following questions and justify your answers.



If X and Y are sequences that both begin with the character A, every longest common subsequence of X and Y begins with A.
If X and Y are sequences that both end with the character A, some longest common subsequence of X and Y ends with A.