CSCI 570  - HW 6

CSCI 570  - HW 6
Graded Problems
For the grade problems, you must provide the solution in the form of pseudocode and also give an analysis on the running time complexity.
Problem 1
[10 points] Suppose you have a rod of length N, and you want to cut up the
rod and sell the pieces in a way that maximizes the total amount of money
you get. A piece of length i is worth pi dollars. Devise a Dynamic
Programming algorithm to determine the maximum amount of money you can
get by cutting the rod strategically and selling the cut pieces.
Problem 2
[10 points] The Trojan Band consisting of n band members hurries to lined up
in a straight line to start a march. But since band members are not positioned
by height the line is looking very messy. The band leader wants to pull out the
minimum number of band members that will cause the line to be in a
formation (the remaining band members will stay in the line in the same order
as they were before). The formation refers to an ordering of band members
such that their heights satisfy r1 < r2 < ... < ri > ... > rn, where 1 ≤ i ≤ n.
For example, if the heights (in inches) are given as
R = (67, 65, 72, 75, 73, 70, 70, 68)
the minimum number of band members to pull out to make a formation will be
2, resulting in the following formation:
(67, 72, 75, 73, 70, 68)
Give an algorithm to find the minimum number of band members to pull
out of the line.
Note: you do not need to find the actual formation. You only need to find
the minimum number of band members to pull out of the line, but you need to
find this minimum number in O(n2) time.
For this question, you must write your algorithm using pseudo-code.
Problem 3
[10 points] From the lecture, you know how to use dynamic programming to solve
the 0-1 knapsack problem where each item is unique and only one of each kind is
available. Now let us consider knapsack problem where you have infinitely many
items of each kind. Namely, there are n different types of items. All the items of
the same type i have equal size wi and value vi. You are offered with infinitely
many items of each type. Design a dynamic programming algorithm to
compute the optimal value you can get from a knapsack with capacity W .
Practice Problems
Problem 4
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 you burst balloon i you will get nums[lef t] " nums[i] " nums[right]
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 can not burst them. Design an dynamic
programming algorithm to find the maximum coins you can collect by bursting
the balloons wisely. Analyze the running time of your algorithm.
Here is an example. If you have the nums arrays equals [3, 1, 5, 8]. The
optimal solution would be 167, where you burst balloons in the order of 1, 5 3
and 8. The left balloons after each step is:
[3, 1, 5, 8] → [3, 5, 8] → [3, 8] → [8] → []
And the coins you get equals:
167=3"1"5+3"5"8+1"3"8+1"8"1.
Problem 5
Solve Kleinberg and Tardos, Chapter 6, Exercise 5.
Problem 6
Solve Kleinberg and Tardos, Chapter 6, Exercise 6.