QUESTION: A Loading Problem: We are given a set S of n items with weights specified by positive real numbers wi , i=1..n, and a truck with load weight capacity specified by a positive real number L. We want to load the truck with as many items as possible without exceeding its load capacity. That is, we want to find a maximum cardinality subset C Í S such that the sum of the item weights in C does not exceed the truck load capacity L.
Describe an O(n) time algorithm to solve this problem if S is given in arbitrary unsorted order. [Hint: use median selection and prune-&-search.]
QUESTION: Smallest Hitting Set: Design and analyze an efficient greedy algorithm for the following problem:
Input: A set P = { p1, p2, … , pn} of points, and a set I = { I1, I2, … , Im} of intervals, all on the real line. These intervals and points are given in no particular order. Each interval is given by its starting and finishing times.
Output: (i) A minimum cardinality subset H of P such that every interval in I is hit by (i.e., contains) at least one point in H, or
(ii) an interval Ik Î I that is not hit by any point in P.
QUESTION: Laser Beams and Balloons:
Suppose you have a high-powered laser beam gun in your hand, standing amidst a number of large balloons in a vast open plateau. You want to use your laser gun to shoot all the balloons without moving from your current location. You want to fire as few shots as possible. The (2 dimensional) Minimum Beams Problem (MBP) can be stated more formally as follows. Given a
set 𝐶 of 𝑛 circles in the plane, each specified by its radius and the (𝑥, 𝑦) coordinates of its center, compute a minimum number of laser beam directions from the origin that collectively intersect every circle in 𝐶. [Each such non-vertical beam may geometrically be viewed as a half- line with the equation 𝑦 = 𝑠𝑥 (with slope 𝑠) that is restricted to one of the 4 quadrants by an additional inequality 𝑥 ≥ 0 or 𝑥 ≤ 0.] Your goal is to find an efficient algorithm for this problem.
12 balloons hit by 5 laser beams. [Problem description continued on the next page.]
- a) For the sake of this problem we will assume, that in addition to the RAM arithmetic
operations, the square-root operation on reals also takes 𝑂(1) time. Give a list of geometric primitives that would be needed by your algorithm. These operations, when
implemented, should run in 𝑂(1) time. The details of their implementation is left as optional (not required). However, you must give a precise definition of these primitives.
For instance, the boolean function 𝐼𝑛𝑡𝑒𝑟𝑠𝑒𝑐𝑡𝑠(𝑏, 𝑐) returns true if and only if beam 𝑏
intersects circle 𝑐. You should convince yourself that this function can be implemented to
run in 𝑂(1) time.
- b) First consider the special case of MBP where there is a known beam direction that does
not hit any circle. Can you transform this special case to a more familiar problem and
efficiently obtain the optimum solution that way?
- c) Using part (b), describe an efficient algorithm that approximately solves the general MBP
by producing a solution that is either optimum or uses one more beam than the optimum.
Prove that fact.
- d) Design and analyze an 𝑂(𝑛6) time algorithm that exactly solves the general MBP. You
must prove that your algorithm does indeed output an optimum solution. [Hint: each circle can in turn be considered as the “first” candidate target. How do you proceed from there to handle the rest?]
- e) [10% Extra Credit and Optional]
Design and analyze an 𝑂(𝑛 log 𝑛) time algorithm that exactly solves the general MBP . Don’t forget the optimality proof. [Hint: This is more challenging!]