CSCI 570 Homework 3
Due Sunday Mar. 08 (by 23:30)
For all divide-and-conquer algorithms follow these steps: 1. Describe the steps of your algorithm in plain English. 2. Write a recurrence equation for the runtime complexity. 3. Solve the equation by the master theorem.
For all dynamic programming algorithms follow these steps: 1. Define (in plain English) subproblems to be solved.
2. Write the recurrence relation for subproblems.
3. Write pseudo-code to compute the optimal value
4. Compute its runtimecomplexity in terms of the input size.
1
5. Given n balloons, indexed from 0 to n 1. Each balloon is painted with a num- ber on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[i 1] ⇥ nums[i] ⇥ nums[i + 1] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent. You may assume nums[ 1] = nums[n] = 1 and they are not real therefore you cannot burst them. Design a dynamic programming algorithm to find the maximum coins you can collect by bursting the balloons wisely. Analyze the running time of your algorithm.
Example. If you have the nums = [3,1,5,8]. The optimal solution would be 167, where you burst balloons in the order of 1, 5, 3 and 8. The array nums after each step is:
[3,1,5,8] ! [3,5,8] ! [3,8] ! [8] ! []
And the number of coins you get is 3⇥1⇥5+3⇥5⇥8+1⇥3⇥8+1⇥8⇥1 = 167.
Solution:
Algorithm 1 Balloon Burst Max Coins
1:
2: 3: 4: 5: 6: 7: 8:
function MaxCoins(nums, n) . num is the array representing balloons, n is the length of nums
Create a table dp((n+2)*(n+2)) with all 0s in the table. nums = [1]+nums+[1]
for length from 1 to n do
for left from 1 to n-length+1 do right = left + length-1
for k from left to right do
dp[left][right] = max{ 1]*nums[k]*nums[right+1] + dp[left][k-1] + dp[k+1][right]}
return dp[1][n]
nums[left-
dp[left][right],
Let dp[i][j] be the maximum coins gained from bursting all the balloons between index i(left) and j(right) in the original array, i and j are included. dp is a two-dimensional array.
The base case is when left==right, then return 0. There are no balloons in the middle to burst.
To get the maximum value we can get for bursting all the balloons between [i,j], we just loop through each balloon between these two indices [i,j] and make them to be the last balloon to be burst and choose the one with maximum coins gained. Let the index of last balloon to be burst is k between [i,j], dp[i][j] =
5
max { dp[i][j], nums[i-1]*nums[k]*nums[j+1]+dp[i][k-1]+dp[k+1][j] }. nums[i- 1]*nums[k]*nums[j+1] is the coined gained when k is the last balloon to be burst. dp[i][k-1] is the maximum coins gained on the left list, and dp[k+1][j] is the maximum coins gained on the right list. For each index k between i and j(i k j), we need to find and choose a value of k(last balloon to be burst) with maximum coins gained, and update dp array. In the end, we want to find out dp[0][n-1], which is the maximum value we can get when we burst all the balloons between [0, n-1].
The pseudo-code is shown as above. In the pseudo-code, we added nums[-1] and nums[n] to nums. So the return will be dp[1][n] due to the index change. The time complexity is O(n3).
Rubric: (15 points)
• (5 points) The algorithm is stated clearly.
– 5 points if the algorithm is using dynamic programming algorithm and it is correct.
– 0 points if the algorithm is totally not correct or the algorithm is not using dynamic programming.
• (3 points) The recurrence relation for sub-problems is correct. • (5 points) The pseudo-code is clearly stated and correct.
• (2 points) The run time complexity is correct.
6. Given a non-empty string str and a dictionary containing a list of unique words, design a dynamic programming algorithm to determine if str can be segmented into a sequence of dictionary words. If str =“algorithmdesign” and your dictio- nary contains “algorithm” and “design”. Your algorithm should answer Yes as str can be segmented as “algorithmdesign”. You may assume that a dictionary lookup can be dome in O(1) time.
Solution:
The idea is simple, we consider each prefix and search it in dictionary. If the prefix is present in dictionary, we recur for rest of the string (or su x). If the recursive call for su x returns true, we return true, otherwise we try next prefix. If we have tried all prefixes and none of them resulted in a solution, we return false.
Why Dynamic Programming? The above problem exhibits overlapping sub- problems
6
Let si,k denote the substring sisi+1…sk. Let OPT(k) denote whether the substring s1,k can be segmented using the words in the dictionary, namely OPT(k) = 1 if the segmentation is possible and 0 otherwise.
E cient implementation:
We build the OPT array using matched-index array that holds the indexes for which OPT[i] is true. When the algorithm is done, last element of OPT shows whether the whole input string can be segmented or not.
s = input string
n = length of s
OPT = array of length n holding possibility of segmentation up to index i matched-index = array holding the indexes for which OPT[i] is true
if n == 0
return True
initialize OPT array with 0 initialize matched-index with -1
for i from 0 to n
msize = matched-index.size flag = 0
for j from msize-1 to 0
sb = s.substring(from: matched-index[j] + 1, length:i – matched-index[j]) if dictionary contains sb
f=1 break
if f == 1
OPT[i] = 1
push i on matched-index
return OPT[n-1]
Rubric: (20 points)
• (10 points) clear description of the algorithm
• (3 points) Objective function: OPT(k) = denote whether the substring s1,k can be segmented using the words in the dictionary
• (3 points) Computation of OPT(i) for all i
• (1 point) The fact that last element of OPT contains the solution (can
either be explicitly mentioned or inferred from the solution) 7
• (3 points) Runtime complexity analysis, result O(n3) in this case since we need O(n) to get substring.
7. A tourism company is providing boat tours on a river with n consecutive seg- ments. According to previous experience, the profit they can make by providing boat tours on segment i is known as ai. Here, ai could be positive (they earn money), negative (they lose money), or zero. Because of the administration convenience, the local community requires that the tourism company do their boat tour business on a contiguous sequence of the river segments (i.e., if the company chooses segment i as the starting segment and segment j as the ending segment, all the segments in between should also be covered by the tour service, no matter whether the company will earn or lose money). The company’s goal is to determine the starting segment and ending segment of boat tours along the river, such that their total profit can be maximized. Design a dynamic programming algorithm to achieve this goal and analyze its runtime.
Solution:
This is a framing of the well known Largest Sum Contiguous Subarray problem.
Dynamic Programming Solution MS = array that holds maximum sum ending at each index
a = input (profits)
iarray = array holding beginning index for each MS MS(0) = 0;
for j = 1, … , a.length do
MS[j] = Math.max(MS[j 1] + a[j 1], a[j 1]); if MS[j 1] + a[j 1] > a[j 1]
iarray[j] = iarray[j 1] else
iarray[j] = j 1
result = MS[0] finali = 0 finalj = 0
for j = 1, … , a.length do if result < MS[j]
result = MS[j] finali = iarray[j]
8
finalj = j return result, i, j
Rubric: (15 points)
• (4 points) Objective function: MS(i) = maximum sum ending at index i
• (5) Recursive formulation: to calculate the solution for any element at index “i” has two options
– (3 points) EITHER added to the solution found till “i-1“th index – (2 points) OR start a new sum from the index “i“.
• (3 point) recording the beginning of each MS (iarray in pseudo code)
• (2 points) handling the final-i , final-j indices
• (1 point) Computing runtime complexity = O(n).
9