CMPT307 20-1 Assignment 4 1 Due 16:00 March 2 (Monday). There are 100 points in this assignment. Submit your answers (must be typed) in pdf file to CourSys https://coursys.sfu.ca/2020sp-cmpt-307-d1/. The work you submitted must be your own. Any collaboration and consulting outside resources must be explicitly mentioned on your submission. 1. 20 points Implement the algorithms Cut-Rod(p, n) (slide page 4), Memoized-Cut-Rod(p, n) (slide page 6) and Bottom-Up-Rod(p, n) (slide page 7) discussed in class for the rod-cut problem. Report the running times of the three algorithms on a computer for n = 5, 10, 15, 20, 25, 30, respectively. For each instance size n, use a same price table p to run the three algorithms. 2. 20 points (Ex 15.2-2 of text book) Give a recursive algorithm Matrix-Chain-Multiply(A, s, i, j) that actually performs the optimal matrix-chain multiplication, given the sequence of matrices A1, A2, .., An, the s table computed by the algorithm Matrix-Chain-Order discussed in class, and the indices i and j. The initial call would be Matrix-Chain-Multiply(A, s, 1, n). 3. 20 points (Ex 15.3-2 of text book) Draw the recursion tree for the Merge-Sort procedure from Section 2.3.1 of text book on an array of 16 elements. Explain why memoization fails to speed up a good divide- and-conquer algorithm such as Merge-Sort. 4. 20 points (Ex 15.5-2 of text book) Give the cost and structure of an optimal binary search tree for an input instance shown below: i 0 1 2 3 4 5 6 7 pi 0 0.04 0.06 0.08 0.02 0.10 0.12 0.14 qi 0.06 0.06 0.06 0.06 0.05 0.05 0.05 0.05 5. 20 points (P 15-2 of text book) A palindrome is a nonempty string over some alphabet that reads the same forward and backward. Examples of palindromes include all strings of length 1, civic, racecar, and aibohphobia (fear of palindromes). Give an efficient algorithm to find the longest palindrome that is a subsequence of a given input string. For example, given the input ”character”, your algorithm should return carac. What is the running time of your algorithm?
