Homework II Solution

$30.00

Description

Problem 1: Nesting Boxes (CLRS)

  • d-dimensional box with dimensions (x1; x2; : : : ; xd) nests within another box with dimensions (y1; y2; : : : ; yd) if there exists a permutation on f1; 2; : : : ; dg such that x (1) < y1; x (2) < y2; : : : ; x (d) < yd.

    1. Argue that the nesting relation is transitive.

    1. Describe an e cient method to determine whether or not one d-dimensional box nests inside another.

    1. Suppose that you are given a set of n d-dimensional boxes fB1; B2; : : : ; Bng. Describe an e cient

algorithm to determine the longest sequence hBi1 ; Bi2 ; : : : ; Bik i of boxes such that Bij nests within

Bij+1 for j = 1; 2; : : : ; k 1i. Express the running time of your algorithm in terms of n and d.

Problem 2: Business plan

Consider the following problem. You are designing the business plan for a start-up company. You have identi ed n possible projects for your company, and for, 1 i n, let ci > 0 be the minimum capital required to start the project i and pi > 0 be the pro t after the project is completed. You also know your initial capital C0 > 0. You want to perform at most k, 1 k n, projects before the IPO and want to

maximize your total capital at the IPO. Your company cannot perform the same project twice.

In other words, you want to pick a list of up to k distinct Projects,

i ; : : : ; i

k0

with k0

k. Your

accumulated capital after completing the project ij will be Cj = C0 +

h=j

1

h=1 pih . The sequence must satisfy

after completing the rst j projects,

the constraint that you have su cient capital to start the project ij+1P

i.e., Cj

cij+1 for each j = 0; : : : ; k0 1. You want to maximize the nal amount of capital, Ck0 .

Problem 3: Scheduling to minimize average completion time (CLRS)

Suppose you are given a set S = fa1; a2; : : : ; an g of tasks, where task ai requires pi units of processing time to complete, once it has started. You have one computer on which to run these tasks, and the computer can run only one task at a time. Let ci be the completion time of task ai, that is, the time at which

task ai completes processing. Your goal is to minimize the average completion time, that is, to minimize Pn

(1=n) i=1 ci. For example, suppose there are two tasks, a1 and a2, with p1 = 3 and p2 = 5, and consider the schedule in which a2 runs rst, followed by a1. Then c2 = 5, c1 = 8, and the average completion time is (5 + 8)=2 = 6:5.

  1. Give an algorithm that schedules the tasks so as to minimize the average completion time. Each task must run non-preemtively, that is, once task ai is started, it must run continuously for pi units of time. Prove that your algorithm minimizes the average completion time, and state the running time of your algorithm.

  1. Suppose now that the tasks are not all available at once. That is, each task has a release time ri before which it is not available to be processed. Suppose also that we allow preemption, so that a task can be suspended and restarted at a later time. For example, a task ai with processing time pi = 6 may start running at time 1 and be preempted at time 4. It can then resume at time 10 but be preempted at time 11 and nally resume at time 13 and complete at time 15. Task ai has run for a total of 6 time units, but its running time has been divided into three pieces. We say that the completion time of ai is 15. Give an algorithm that schedules the tasks so as to minimize the average completion time in this new scenario. Prove that your algorithm minimizes the average completion time, and state the running time of your algorithm.

1

Problem 4: Shortest wireless path sequence (KT 6.14)

A large collection of mobile wireless devices can naturally form a network in which the devices are the nodes, and two devices x and y are connected by an edge if they are able to directly communicate with each other (e.g., by a short-range radio link). Such a network of wireless devices is a highly dynamic object, in which edges can appear and disappear over time as the devices move around. For instance, an edge (x; y) might disappear as x and y move far apart from each other and lose the ability to communicate directly.

In a network that changes over time, it is natural to look for e cient ways of maintaining a path between certain designated nodes. There are two opposing concerns in maintaining such a path: we want paths that are short, but we also do not want to have to change the path frequently as the network structure changes. (That is, we’d like a single path to continue working, if possible, even as the network gains and loses edges.) Here is a way we might model this problem.

Suppose we have a set of mobile nodes V , and at a particular point in time there is a set E0 of edges among these nodes. As the nodes move, the set of edges changes from E0 to E1, then to E2, then to E3, and so on, to an edge set Eb. For i = 0; 1; 2; : : : ; b, let Gi denote the graph (V; Ei). So if we were to watch the structure of the network on the nodes V as a \time lapse”, it would look precisely like the sequence of graphs G0; G1; G2; : : : ; Gb 1; Gb. We will assume that each of these graphs Gi is connected.

Now consider two particular nodes s; t 2 V . For an s-t path P in one of the graphs Gi, we de ne the length of P to be simply the number of edges in P , and we denote this ‘(P ). Our goal is to produce a sequence of paths P0; P1; : : : ; Pb so that for each i, Pi is an s-t path in Gi. We want the paths to be relatively short. We also do not want there to be too many changes{points at which the identity of the path switches. Formally, we de ne changes(P0; P1; : : : ; Pb) to be the number of indices i (0 i b 1) for which Pi 6= Pi+1.

Fix a constant K > 0. We de ne the cost of the sequence of paths P0; P1; : : : ; Pb to be

b

X

cost(P0; P1; : : : ; Pb) = ‘(Pi) + K changes(P0; P1; : : : ; Pb):

i=0

  1. Suppose it is possible to choose a single path P that is an s-t path in each of the graphs G0; G1; : : : ; Gb. Give a polynomial-time algorithm to nd the shortest such path.

  1. Give a polynomial-time algorithm to nd a sequence of paths P0; P1; : : : ; Pb of minimum cost, where

Pi is an s-t path in Gi for i = 0; 1; : : : ; b.

Problem 5: Selling shares of stock (KT 6.25)

Consider the problem faced by a stockbroker trying to sell a large number of shares of stock in a company whose stock price has been steadily falling in value. It is always hard to predict the right moment to sell stock, but owning a lot of shares in a single company adds an extra complication: the mere act of selling many shares in a single day will have an adverse e ect on the price.

Since future market prices, and the e ect of large sales on these prices, are very hard to predict, brokerage rms use models of the market to help them make such decisions. In this problem, we will consider the following simple model. Suppose we need to sell x shares of stock in a company, and suppose that we have an accurate model of the market: it predicts that the stock price will take the values p1; p2; : : : ; pn over the next n days. Moreover, there is a function f( ) that predicts the e ect of large sales: if we sell y shares on a single day, it will permanently decrease the price by f(y) from that day onward. So, if we sell y1 shares

on day 1, we obtain a price per share of p1 f(y1), for a total income of y1 (p1 f(y1)). Having sold y1

shares on day 1, we can then sell y2 shares on day 2 for a price per share of p2 f(y1) f(y2); this yields

an additional income of y2 (p2 f(y1) f(y2)). This process continues over all n days. (Note, as in our calculation for day 2, that the decreases from earlier days are absorbed into the prices for all later days.)

Design an e cient algorithm that takes the prices p1; : : : ; pn and the function f( ) (written as a list of values f(1); f(2); : : : ; f(x)) and determines the best way to sell x shares by day n. In other words, nd natural numbers y1; y2; : : : ; yn so that x = y1 + : : : + yn, and selling yi shares on day i for i = 1; 2; : : : ; n maximizes the total income achievable. You should assume that the share value pi is monotone decreasing, and f( ) is monotone increasing; that is, selling a larger number of shares causes a larger drop in the price.

2

Your algorithms running time can have a polynomial dependence on n (the number of days), x (the number of shares), and p1 (the peak price of the stock).

Example Consider the case when n = 3; the prices for the three days are 90, 80, 40; and f(y) = 1 for y 40; 000 and f(y) = 20 for y > 40; 000. Assume you start with x = 100; 000 shares. Selling all of them on day 1 would yield a price of 70 per share, for a total income of 7,000,000. On the other hand, selling 40,000 shares on day 1 yields a price of 89 per share, and selling the remaining 60,000 shares on day 2 results in a price of 59 per share, for a total income of 7,100,000.

3