Design a dynamic programming algorithm for the following problem. Find the maximum total sale price that...

  

Transcribed Image Text:

Design a dynamic programming algorithm for the following problem. Find the maximum total sale price that can be obtained by cutting a rod of n units long into integer-length pieces if the sale price of a piece i units long is pi for i = 1, 2,..., n. Optional: what are the time and space efficiencies of your algorithm? 8) Minimum-sum descent: Some positive integers are arranged in an equilateral triangle with n numbers in its base like the one shown in the figure below for n = 4. The solution for this example is highlighted: 2 5 4 1 47 8 696 The problem is to find the smallest sum in a descent from the triangle apex to its base through a sequence of adjacent numbers (shown in the figure by dashes). Design a dynamic programming algorithm for this problem. Optional: indicate its time efficiency. Hint: you might want to represent the data in a table like this: 0 12 3 0 2 5 1 8 1 2 4 4 6 7 9 3 6 (not from the book) N-Choose-K problem: Design a dynamic programming algorithm for the recursive n-choose-k problem discussed in class (and outlined below). Optional: indicate its time and space complexity. Hint: Pascals Triangle reveals n choose k. From the peak (the value of 1) move down the triangle by n, and then to the right by k to find the solution for n choose k in the triangle. Pascals Triangle up to n = 6: 1 11 121 1331 14641 1 5 10 10 51 1 6 15 20 15 6 1 The n choose k problem: I have five friends I want to invite to my birthday party. Mom says I can only invite three. How many ways can I invite these three friends? This is a 5 choose 3 problem. Here is the classic n choose k formula: n! k! (n - k)! From this formula we can figure out there are 10 ways to invite 3 people out of 5 friends. But how could we do this recursively? Let's imagine Albert is my best friend in the whole world (and one of my five possible friends to invite). Let's call Albert 'a'. From 5 choose 3, if Albert is invited we are left with a 4 choose 2 problem. From 5 choose 3, if Albert is not invited, we are left with a 4 choose 3 problem. Here are all the ways I can invite 3 of 5 friends: abc, abd, abe, acd, ace, ade, these are all the ways we can 5 choose 3 if Albert is invited bcd, bce, bce, bde, and cde - these are all the ways we can 5 choose 3 if Albert is not invited So the total number of ways we can invite 3 out of 5 friends can be found by having children to do work for the smaller n choose k problems. And the recursive formula for f(n,k) is: f(n,k) = (n-1, k-1) + (n-1, k) If we apply dynamic programming we can improve this recursive solution...that is your task. Design a dynamic programming algorithm for the following problem. Find the maximum total sale price that can be obtained by cutting a rod of n units long into integer-length pieces if the sale price of a piece i units long is pi for i = 1, 2,..., n. Optional: what are the time and space efficiencies of your algorithm? 8) Minimum-sum descent: Some positive integers are arranged in an equilateral triangle with n numbers in its base like the one shown in the figure below for n = 4. The solution for this example is highlighted: 2 5 4 1 47 8 696 The problem is to find the smallest sum in a descent from the triangle apex to its base through a sequence of adjacent numbers (shown in the figure by dashes). Design a dynamic programming algorithm for this problem. Optional: indicate its time efficiency. Hint: you might want to represent the data in a table like this: 0 12 3 0 2 5 1 8 1 2 4 4 6 7 9 3 6 (not from the book) N-Choose-K problem: Design a dynamic programming algorithm for the recursive n-choose-k problem discussed in class (and outlined below). Optional: indicate its time and space complexity. Hint: Pascals Triangle reveals n choose k. From the peak (the value of 1) move down the triangle by n, and then to the right by k to find the solution for n choose k in the triangle. Pascals Triangle up to n = 6: 1 11 121 1331 14641 1 5 10 10 51 1 6 15 20 15 6 1 The n choose k problem: I have five friends I want to invite to my birthday party. Mom says I can only invite three. How many ways can I invite these three friends? This is a 5 choose 3 problem. Here is the classic n choose k formula: n! k! (n - k)! From this formula we can figure out there are 10 ways to invite 3 people out of 5 friends. But how could we do this recursively? Let's imagine Albert is my best friend in the whole world (and one of my five possible friends to invite). Let's call Albert 'a'. From 5 choose 3, if Albert is invited we are left with a 4 choose 2 problem. From 5 choose 3, if Albert is not invited, we are left with a 4 choose 3 problem. Here are all the ways I can invite 3 of 5 friends: abc, abd, abe, acd, ace, ade, these are all the ways we can 5 choose 3 if Albert is invited bcd, bce, bce, bde, and cde - these are all the ways we can 5 choose 3 if Albert is not invited So the total number of ways we can invite 3 out of 5 friends can be found by having children to do work for the smaller n choose k problems. And the recursive formula for f(n,k) is: f(n,k) = (n-1, k-1) + (n-1, k) If we apply dynamic programming we can improve this recursive solution...that is your task.

Answer rating: 100% (QA)

Answer Dynamic Programming Algorithm Create an array maxPrice of size n1 to store the maximum total ... View the full answer