Unformatted text preview:

COS 423 Problem Set No. 2 Due Wed. 3/8Spring 20061. (See Kleinberg and Tardos, Chapter 2, ex. 8.) You are doing some stress-testing on various models of glass jars to determine the height from which they can be dropped and still not break. The setup for this experiment, on a particular type of jar, is as follows. You have a ladder withnrungs, and you want to find the highest rung from which you can drop a copy of the jar and not have it break. We call this the highest safe rung.It might be natural to try binary search: drop a jar from the middle rung, see if it breaks,and then recursively try from rung / 4nor 3 / 4n depending on the outcome. But this has the drawback that you could break a lot of jars in finding the answer.If your primary goal were to conserve jars, on the other hand, you could try the following strategy. Start by dropping a jar from the first rung, then the second rung, and so forth, climbing one higher each time until the jar breaks. In this way, you only need a single jar – at the moment it breaks, you have the correct answer – but you may have to drop it ntimes (rather than lg nas in the binary search solution).So here is the trade-off: it seems you can perform fewer drops if you are willing to break more jars. To study this trade-off, letkbe the number of jars you are given, and let nbe the actual highest safe rung. Give a bound on the number of drops needed to find the highest safe rung, as a function of kand .n Your goal is to make this number as small as possible. Describe a corresponding strategy for finding the highest safe rung. Hint: consider the case 2,k = and then think about what happens whenk increases. Try writing a recurrence for the minimum number of drops as a function ofk and nand then solving it, or at least giving bounds on its value.2. (See Kleinberg and Tardos, Chapter 3, ex.11.) You are helping some security analysts monitor a collection of networked computers tracking the spread of an online virus. There are ncomputers in the system, labeled 1 2, ,..., ,nC C Cand as input you are given a collection of trace data indicating the times at which pairs of computers communicated. Thus the data is a sequence of ordered triples ( , , );i j kC C tsuch a triple indicates that iCand jCexchanged bits at time.kt There aremtriples total. We will assume that the triples are presented to you in sorted order of time.The security analysts you are working with would like to be able to answer questions ofthe following form: if the virus was inserted into computer aCat time ,xcould it possibly have infected computer bCby time?y The mechanics of infection are simple: if an infected computer iCexchanges bits with an uninfected computer jCat time kt (that is, if either of the triples ( , , )i j kC C t or ( , , )j i kC C t appears in the trace data) thenjCbecomes infected as well, starting at time.kt Infection can thus spread from onemachine to another through a sequence of communications, which must happen in non-decreasing order of time. Describe an ( ) - timeO n m+algorithm which, given an initial infection of a computer aC at time ,tdetermines for each other computer the earliest time at which it can become infected. Your algorithm should keep track of enough information so that, for any computer ,bC it is possible to retrieve in O( )ntime a sequence of communications by whichbCcould have become infected.3. (See Kleinberg and Tardos, Chapter 4, ex. 6.) Your friend is working as a camp counselor, and she is in charge of organizing activities for a set of campers. One of her plans is a mini-triathlon exercise: each contestant must swim 20 laps of a pool, then bike 10 miles, then run 3 miles. The plan is to send the contestants out in a staggered fashion, via the following rule: the contestants must use the pool one at a time. In otherwords, first one contestant swims the 20 laps, gets out, and starts biking. As soon as this first person is out of the pool, a second contestant begins swimming the 20 laps; as soon as he or she is out and starts biking, a third contestant begins swimming, and so on.Each contestant has a projected swimming time, biking time, and running time. Your friend wants to decide on a schedule for the triathlon; namely, an order in which to sequence the starts of the contestants, so as to minimize the completion time of the event, the time when all contestants are done. Again, at most one person can swim at a time, but any number can be running or biking at the same time. What is the best order for sending people out if one wants the whole competition to be over as early as possible (assuming the projected times of all contestants are accurate)? More precisely,give an efficient algorithm that produces a schedule whose completion time is as small as possible.4. (Kleinberg and Tardos, Chapter 4, ex.30) Let G=(V,E)be a graph with nnodes in which each pair of nodes is joined by an edge. There is a positive weight ijWon each edge ( , );i jand we will assume these weights satisfy the triangle inequality.ijik jkW W W� + For a subset ,V V�� we will use [ ]G V�to denote the subgraph (with edge weights) induced on the nodes in .V�We are given a set X V�of kterminals that must be connected. We say that a Steiner Tree on X is a set Zso that ,X Z V� �together with a spanning subtree Tof [ ].G Z The weight of the Steiner tree is the weight of the tree .TShow that the problem of finding a minimum-weight Steiner tree on Xcan be solved intime ( )( ).O kO n5. (Kleinberg and Tardos, Chapter 4, ex. 31) Let’s go back to the original motivation for the Minimum Spanning Tree Problem. We are given a connected, undirected graphG = (V,E) with positive edge lengths { },eland we want to find a spanning subgraph of it. Now suppose we are willing to settle for a subgraph ( , )H V F=that is “denser” than a tree, and we are interested in guaranteeing that, for each pair of vertices , ,u v V � the length of the shortest u v-path in His not much longer than the length of the shortestu v-path in.G By the length of a path Phere, we mean the sum of elover all edges ein .PHere is a variant of Kruskal’s Algorithm designed to produce such a subgraph.- First we sort all the edges in order of increasing length. (You may assume all edge lengths are distinct.)- We then construct a subgraph ( , )H V F=by considering each edge in order.- When we


View Full Document

Princeton COS 423 - Problem Set No. 2

Download Problem Set No. 2
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Problem Set No. 2 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Problem Set No. 2 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?