There is a prize hidden in a box; the value of the prize is a positive integer between 1 and N, and you are given N. To win the prize, you have to guess its value. Your goal is to do it in as few guesses as may only make at most g guesses that are too high. The value g will be specified at the start of the game, and if you make more than g guesses that are too high, you lose. So, for example, if g- 0, you then can win in N guesses by simply guessing the sequence 1, 2, 3,... a. Suppose g logN1. What strategy minimizes the number of guesses?
b. Suppose g 1. Show that you can always win in O(N1/2) guesses.
c. Suppose g 1. Show that any algorithm that wins the prize must use 2 (N1/2) possible; however, among those guesses, you guesses
d. Give an algorithm and matching lower bound for any constant g.