$30.00
Description
Problem 1: Nesting Boxes (CLRS)

ddimensional box with dimensions (x_{1}; x_{2}; : : : ; x_{d}) nests within another box with dimensions (y_{1}; y_{2}; : : : ; y_{d}) if there exists a permutation on f1; 2; : : : ; dg such that x _{(1)} < y_{1}; x _{(2)} < y_{2}; : : : ; x _{(d)} < y_{d}.


Argue that the nesting relation is transitive.



Describe an e cient method to determine whether or not one ddimensional box nests inside another.



Suppose that you are given a set of n ddimensional boxes fB_{1}; B_{2}; : : : ; B_{n}g. Describe an e cient

algorithm to determine the longest sequence hB_{i}_{1} ; B_{i}_{2} ; : : : ; B_{i}_{k} i of boxes such that B_{i}_{j} nests within
B_{i}_{j+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 startup company. You have identi ed n possible projects for your company, and for, 1 i n, let c_{i} > 0 be the minimum capital required to start the project i and p_{i} > 0 be the pro t after the project is completed. You also know your initial capital C_{0} > 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 
k^{0} 
with k^{0} 
k. Your 

accumulated capital after completing the project i_{j} will be C_{j} = C_{0} + 
h=j 
1 

_{h=1} p_{i}_{h} . The sequence must satisfy 

after completing the rst j projects, 

the constraint that you have su cient capital to start the project i_{j+1}^{P} 

i.e., C_{j} 
c_{i}_{j+1} for each j = 0; : : : ; k^{0} 1. You want to maximize the nal amount of capital, C_{k}0 . 

Problem 3: Scheduling to minimize average completion time (CLRS)
Suppose you are given a set S = fa_{1}; a_{2}; : : : ; a_{n} g of tasks, where task a_{i} requires p_{i} 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 c_{i} be the completion time of task a_{i}, that is, the time at which
task a_{i} completes processing. Your goal is to minimize the average completion time, that is, to minimize Pn
(1=n) _{i=1} c_{i}. For example, suppose there are two tasks, a_{1} and a_{2}, with p_{1} = 3 and p_{2} = 5, and consider the schedule in which a_{2} runs rst, followed by a_{1}. Then c_{2} = 5, c_{1} = 8, and the average completion time is (5 + 8)=2 = 6:5.

Give an algorithm that schedules the tasks so as to minimize the average completion time. Each task must run nonpreemtively, that is, once task a_{i} is started, it must run continuously for p_{i} units of time. Prove that your algorithm minimizes the average completion time, and state the running time of your algorithm.

Suppose now that the tasks are not all available at once. That is, each task has a release time r_{i} 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 a_{i} with processing time p_{i} = 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 a_{i} 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 a_{i} 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 shortrange 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 E_{0} of edges among these nodes. As the nodes move, the set of edges changes from E_{0} to E_{1}, then to E_{2}, then to E_{3}, and so on, to an edge set E_{b}. For i = 0; 1; 2; : : : ; b, let G_{i} denote the graph (V; E_{i}). 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 G_{0}; G_{1}; G_{2}; : : : ; G_{b} _{1}; G_{b}. We will assume that each of these graphs G_{i} is connected.
Now consider two particular nodes s; t 2 V . For an st path P in one of the graphs G_{i}, 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 P_{0}; P_{1}; : : : ; P_{b} so that for each i, P_{i} is an st path in G_{i}. 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(P_{0}; P_{1}; : : : ; P_{b}) to be the number of indices i (0 i b 1) for which P_{i} 6= P_{i+1}.
Fix a constant K > 0. We de ne the cost of the sequence of paths P_{0}; P_{1}; : : : ; P_{b} to be
b
X
cost(P_{0}; P_{1}; : : : ; P_{b}) = ‘(P_{i}) + K changes(P_{0}; P_{1}; : : : ; P_{b}):
i=0

Suppose it is possible to choose a single path P that is an st path in each of the graphs G_{0}; G_{1}; : : : ; G_{b}. Give a polynomialtime algorithm to nd the shortest such path.

Give a polynomialtime algorithm to nd a sequence of paths P_{0}; P_{1}; : : : ; P_{b} of minimum cost, where
P_{i} is an st path in G_{i} 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 p_{1}; p_{2}; : : : ; p_{n} 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 y_{1} shares
on day 1, we obtain a price per share of p_{1} f(y_{1}), for a total income of y_{1} (p_{1} f(y_{1})). Having sold y_{1}
shares on day 1, we can then sell y_{2} shares on day 2 for a price per share of p_{2} f(y_{1}) f(y_{2}); this yields
an additional income of y_{2} (p_{2} f(y_{1}) f(y_{2})). 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 p_{1}; : : : ; p_{n} 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 y_{1}; y_{2}; : : : ; y_{n} so that x = y_{1} + : : : + y_{n}, and selling y_{i} shares on day i for i = 1; 2; : : : ; n maximizes the total income achievable. You should assume that the share value p_{i} 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 p_{1} (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