CS270 Homework 6 Solution

a. Define (in plain English) subproblems to be solved. (4 pts)
b. Write a recurrence relation for the subproblems (6 pts)
c. Make sure you specify
a. base cases and their values (2 pts)
b. where the final answer can be found (1 pt)
d. What is the complexity of your solution? (2 pts)
2. Solve Kleinberg and Tardos, Chapter 6, Exercise 12.
a. Define (in plain English) subproblems to be solved. (4 pts)
b. Write a recurrence relation for the subproblems (6 pts)
c. Make sure you specify
i. base cases and their values (2 pts)
ii. where the final answer can be found (1 pt)
d. What is the complexity of your solution? (2 pts)
3. Givenrepresented by array nums. You are asked to burst all the balloons. If the you burstballoon𝑛 balloons, indexed fromyou will get 0 to 𝑛 − 1. Each balloon is painted with a number on itcoins. Here and
time of your algorithm.
Here is an example. If you have the nums arrays equalssolution would be 167, where you burst balloons in the order of 1, 5, 3 and 8. The leftballoons after each step is: [3, 1, 5, 8]. The optimal
[3, 1, 5, 8] → [3, 5, 8] → [3, 8] → [8] → []
And the coins you get equals:
(3 ∗ 1 ∗ 5) + (3 ∗ 5 ∗ 8) + (1 ∗ 3 ∗ 8) + (1 ∗ 8 ∗ 1) = 167
a. Define (in plain English) subproblems to be solved. (4 pts)
b. Write a recurrence relation for the subproblems (6 pts)
c. Make sure you specify
i. base cases and their values (2 pts)
ii. where the final answer can be found (1 pt)
d. What is the complexity of your solution? (2 pts)
4. Suppose you have a rod of length N, and you want to cut up the rod and sell the pieces 𝑝𝑖 dollars. Devise a Dynamic Programming algorithm to determine the maximum amount𝑖 in a way that maximizes the total amount of money you get. A piece of length is worth
of money you can get by cutting the rod strategically and selling the cut pieces.
a. Define (in plain English) subproblems to be solved. (4 pts)
b. Write a recurrence relation for the subproblems (6 pts)
c. Using the recurrence formula in part b, write pseudocode to solve the problem. (5 pts)
d. Make sure you specify
i. base cases and their values (2 pts)
ii. where the final answer can be found (1 pt)
e. What is the complexity of your solution? (2 pts)
5. Solve Kleinberg and Tardos, Chapter 6, Exercise 10.
a. part(a) of the question (4pts)
b. part(b) of the question (answer according to the format below)
i. Define (in plain English) subproblems to be solved. (4 pts)
ii. Write a recurrence relation for the subproblems (6 pts)
iii. Using the recurrence formula in part ii, write pseudocode to solve the problem. (5 pts)
iv. Make sure you specify
i. base cases and their values (2 pts)
ii. where the final answer can be found (1 pt)
v. What is the complexity of your solution? (2 pts)