hey, i have a solution to ur prob :
a) for k=2 case, check at intervals of sqrt(n) you will find the jar between
say sqrt(i) and sqrt(i+1)
do a linear search between sqrt(i) and sqrt(i+1)
( clearly the order is sqrt(n) )
b) for k=k! , consider at kth root of n instead of sqrt everywhere above.
I guess you will be able to do the reasoning part now
Rohit Saraf
Sophomore
IIT Bombay
-------
http://www.cse.iitb.ac.in/~rohitfeb14
On Tue, Feb 9, 2010 at 8:03 PM, suganya c <sugu18901...@gmail.com> wrote:
> can u help with the solution for this problem.??
>
> You’re 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 with n rungs, and you want to find the highest rung
> from which you can drop a copy of the jar and not have it break..We ca~,
> 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 n/4 or 3n/4
> depending on the outcome. But this has the drawback that y9u 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 j ar--at the
> moment
> it breaks, you have the correct answer--but you may have to drop it rt
> times (rather than log rt as in the binary search solution).
> So here is the trade-off: it seems you can perform fewer drops if
> you’re willing to break more jars. To understand better how this tradeoff
> works at a quantitative level, let’s consider how to run this experiment
> given a fixed "budget" of k >_ 1 jars. In other words, you have to
> determine
> the correct answer--the highest safe rung--and can use at most k jars In
> doing so.
> (a) Suppose you are given a budget of k = 2 jars. Describe a strategy for
> finding the highest safe rung that requires you to drop a jar at most
> f(n) times, for some function f(n) that grows slower than linearly. (In
> other words, it should be the case that limn-.~ f(n)/n = 0.)
> (b) Now suppose you have a budget of k > 2 jars, for some given k.
> Describe a strategy for fInding the highest safe rung using at most
> k jars. If fk(n) denotes the number of times you need to drop a jar
> according to your strategy,then the functions f1,f2,f3...should have.
> the property that each grows asymptotically slower than the previous
> one: lirnn_~ fk(n)/fk_l(n) = 0 for each k.
>
> thank u,
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
