0

I have a question where I'm completely confused how to set up a recurrence.

A watch manufacturer looks to find out if an integer value for water resistance is in the range of 0 to n. The water resistance is 0 if a watch leaks, and the watch does not leak at the depth of n meters. The water resistance is defined as n.

To test the water resistance at a depth k, a scuba diver does a dive at k meters and stays under water at that depth for one hour. If the watch leaks, it is discarded. If it does not leak, it can be reused in another experiment.

How many watches leak in the worst case? (worst case here means the maximum number of damaged watches)?

What's given: Describe the worst case situation and then give a recurrence relation for the number of damaged watches. Assume that the midpoint is chosen for the sub-problem for row lower to upper by the formula: mid = floor[(lower+upper)/2] where lower = 1, and upper = n for the first sub-problem.

So what I got from this is mid = floor[(1+n)/2] but I'm not sure how to come up with a recurrence that holds for any value of n.

Can someone guide me on what to do / how to get started? I would appreciate any help from anyone.

Thanks guys.

user2958631
  • 1
  • 6
  • 2
    Your question is not clear. Can you give an example? – Abhishek Bansal Nov 12 '13 at 07:02
  • The question is asking how many watches leak in the worst case (meaning to set up a recurrence equation for it.) I edited my original post, I hope you can help me. Thanks for response Abhishek. – user2958631 Nov 12 '13 at 07:03
  • 1
    It'll be helpful if you can provide a sample input and output data. – Abhishek Bansal Nov 12 '13 at 07:05
  • I do not have any sample input / output data as this is just based on the recurrence. That is why I am asking for help because I don't know how to set it up. All that is given is the midpoint (which is between lower and upper). – user2958631 Nov 12 '13 at 07:07
  • I've edited the original post to add any missing parts. – user2958631 Nov 12 '13 at 07:42
  • 2
    Sounds very similar to [Throwing cats out of windows](http://stackoverflow.com/questions/3974077/throwing-cats-out-of-windows). – Bernhard Barker Nov 12 '13 at 07:43

1 Answers1

1

If you want to minimize the total number of watches leaked, then it is one. You can just test it sequentially for k = 0, k = 1, etc till a watch leaks. The complexity for number of tests in this case is O(m) where m is the water resistance of the watches.

If you want to minimize the total number of tests, then IMO it is a binary search problem. You are searching for the minimum k at which the watches leak.

Start from the mid-point.

If the watch leaks, then its resistance is less than the mid-point. 

Hence new mid-point = (lower + mid-point)/2.

If it does not leak, then its resistance is greater than the mid-point. 

Hence new mid-point = (mid-point + upper)/2.

In the worst case, all the tested watches leak. This is the complexity of the algorithm which is O(logn).

If you have a constraint on the maximum number of watches you can leak or the maximum number of trials you can do, then you should follow the link shown by @Dukeling for suitable Dynamic Programming formulation.

Community
  • 1
  • 1
Abhishek Bansal
  • 12,589
  • 4
  • 31
  • 46
  • As hinted by article pointed by @Dukeling, the optimal should be found using dynamic programming, and not binary search. =) – justhalf Nov 12 '13 at 07:52
  • @justhalf OOPs! mis-interpreted the question. Shall delete my answer. – Abhishek Bansal Nov 12 '13 at 07:56
  • 1
    @justhalf See my update. IMO This problem is slightly different from the linked question because, there is no constraint on the maximum number of watches. – Abhishek Bansal Nov 12 '13 at 08:10
  • Hi, thanks for the responses. I was trying to find how to set up the recurrence though for T(n) using the floor and ceiling function as I included for the given midpoint sub-problem. Hope someone can respond again, thanks for all the resourceful comments. – user2958631 Nov 12 '13 at 10:02
  • Can anyone provide any assistance? – user2958631 Nov 13 '13 at 01:22
  • @user2958631 I suggest you look up the link that Dukeling provided. That explains clearly how to approach such problems and how to set up the recurrence relation. http://stackoverflow.com/questions/3974077/throwing-cats-out-of-windows – Abhishek Bansal Nov 13 '13 at 04:24
  • I have looked at it but I don't see the relation between the questions. I'm mainly wondering how to get the recurrence from just the midpoint – user2958631 Nov 13 '13 at 05:43