Homework #4 Introduction to Algorithms/Algorithms 1

Homework #4
Introduction to Algorithms/Algorithms 1
601.433/633

Where to submit: On Gradescope.
Please type your answers; handwritten assignments will not be accepted.
1 Problem 1 (15 points)
Suppose you are managing the construction of billboards on an east-west highway
that extends in a straight line. The possible sites for billboards are given by reals
x1, x2, . . . , xn with 0 ≤ x1 < x2 < · · · < xn, specifying their distance in miles
from the west end of the highway. If you place a billboard at location xi
, you receive payment pi 0.
Regulations imposed by the Baltimore County’s Highway Department require that
any pair of billboards be more than 5 miles apart. You’d like to place billboards at
a subset of the sites so as to maximize your total revenue, subject to that placement
restriction.
For example, suppose n = 4, with
hx1, x2, x3, x4i = h6, 7, 12, 14i,
and
hp1, p2, p3, p4i = h5, 6, 5, 1i.
The optimal solution would be to place billboards at x1 and x3, for a total revenue
of p1 + p3 = $10.
1
Give an O(n) time dynamic-programming algorithm that takes as input an instance
(locations {xi} given in sorted order and their prices {pi}) and returns the maximum revenue obtainable. As usual, prove correctness and running time of your
algorithm.
EDIT: We will give full credit for an O(n log(n)) algorithm too.
2 Problem 2 (20 points)
You are given two numbers, n and k, such that n ∈ N and k ∈ {1, . . . , 9}. Use
dynamic programming to devise an algorithm which will find the number of 2ndigit integers for which the sum of the first n digits is equal to the sum of the last
n digits and each digit takes a value from 0 to k.
For example, when k = 2 and n = 1: you have only 3 such numbers 00, 11, 22.
For example, when k = 1 and n = 2: you have only 6 such numbers 0000, 0101,
0110, 1001 , 1010, 1111.
Your algorithm should work in time polynomial of n and k. Prove correctness and
provide running time analysis.
3 Problem 3 (15 points)
Alice and Bob found a treasure chest with different golden coins, jewelry and various old and expensive goods. After evaluating the price of each object they created
a list P = {p1, . . . , pn} for all n objects, where pi ∈ {1, . . . , K} is the price of the
object i. Help Alice and Bob to check if the treasure can be divided equally, i.e. if
it is possible to break the set of all abjects P into two parts PA and PB such that
PA ∪ PB = P, PA ∩ PB = ∅ and P
i∈PA
pi =
P
i∈PB
pi?
Your algorithm should run in time polynomial in n and K. As usual, prove correctness and running time of your algorithm.
2