CMPUT 204 Assignment
Algorithm – 这个题目属于一个Algorithm的代写任务, 涵盖了Algorithm等程序代做方面
Due: March 25, 2022 (11:59 pm) (Total 40 marks)
CMPUT 204
Some questions here are based on Problem Set #5 and our lecture notes. Discussions of related problems may also be found online. You may consult, adopt, or revise any of these solutions to compose your answers. But recall that you must understand what you submitted and be able to explain your answers. If your Algorithm is the same as the one given in the Problem Set or lecture notes, just indicate so; otherwise please specify.
Problem 1.(15 marks)
a. (5 marks) Consider the 0-1 knapsack problem for itemsi= 1,2,3,4,5, whose values are [4, 3 , 6 , 5 ,7] and whose weights are [2, 2 , 3 , 4 ,5]. Assume the knapsack capacity is 10. Apply the knapsack algorithm discussed in class to the problem by filling the 2-dimensional tableA[i, D] (0i 5 , 0 D10), and apply the Print-Opt-Knapsack procedure to show which items are in your optimal solution.
Partial Solution:The tableA[i, D] below is partially filled, and you are to fill the remaining cells.
i\D 0 1 2 3 4 5 6 7 8 9 10
0 0 0 0 0 0 0 0 0 0
1 0 0 4 4 4 4 4
2 0 0 4 4 7 7 7
3 0 0 4 6 10 13
4 0 0 4 6 10 10
5
b. (5 marks) Find an LCS of strings ABAECCD and ACDEF. You should show how you derived your solution using a table similar to Fig. 15.8 of CLRS p395.
c. (5 marks) MatricesA, B, C, D, Ehave respective dimensions 15, 52, 26, 61, 14. What is the minimum number of scalar multiplications needed to computeABCDE? Give the parenthesization of matrices that yields this number. Show how you arrived at your answer.
Problem 2.(8 marks) In this question, you are asked to show how a problem instance is solved for the following problem given in Problem Set #5. There arenHudsons Bay Company posts on the River Koksoak. At any of these posts you can rent a canoe to be returned at any other post downstream (it is next to impossible to paddle against the current.) For each possible departure pointiand each possible arrival pointjthe companys tariff gives the cost of a rental betweeniandjwhich isC[i, j]. However, it can happen that the cost of renting fromitoj is higher than the total cost of a series of shorter rentals, in which case you can return the first canoe at some postkbetweeniandjand continue the journey in a second canoe. There is no extra charge for canoe change. Give an efficient algorithm to determine, givennand costsC[i, j], the sequence of canoe rentals with minimum cost for a trip from post 1 to postn.
In this question, you are asked to fill the tablesA[i] andS[i] (1i6) as defined above for the
following problem instance:
1
C[1,2] = 7, C[1,3] = 8, C[1,5] = 21
C[2,3] = 5, C[2,5] = 13
C[3,4] = 5, C[3,5] = 9, C[3,6] = 17
C[4,5] = 8, C[4,6] = 15
C[5,6] = 7
For all other pairs ofi < j,C[i, j] =, which means renting fromitoj is not available. For
part marks, wed like to understand how you did your work. For this purpose, please explain how
you filled the cells atA[5] andA[6].
According toS[.], which rental arrangement yields the minimum cost?
Problem 3.(17 marks) Longest Sub-Palindromeproblem: given a sequenceX=x 1 , …, xnfind the longest subsequence xi 1 , …, xiksuch thatij< ij+1for anyj, and that is a palindrome: kis even and the inverse sequence xik, xik 1 , …, xi 1 is identical to the original sequencexi 1 , …, xik. (E.g., abba is a sub-palidrome of tablebrand.) Note that the definition here differs slightly from the standard dictionary definition of palindrome; here we only consider palindromes whose length is an even number. In this question, you are asked to present a complete solution to demonstrate all the ingredients of solving this problem by DP.
a. Denote the problem byLSP(x 1 , ..., xn). Give a recursive definition to solve the problem. Argue that
all of the recursive calls live in a small domain so that the DP approach is possible.
b. Turn your recursive definition to a table definition. Indicate the dimensions of your table, what each
cell of your table stores, and which cell stores the value of an optimal solution (the value is the
number of characters in a longest sub-palindrome of the given string).
c. Give an algorithm in pseudocode to compute (the value of) an optimal solution. Analyze its running
time.
d. Give an algorithm in pseudocode to generate the actual string of an optimal solution. Comment on
its running time.
e. Now consider the input stringS=p, e, q, q, d, e.
(i) Draw the table according to your solution, and for each cell fill its value.
(ii) According to your algorithm, which sub-palindrome is generated? Explain briefly how it is
generated.