1. Engineering
  2. Computer Science
  3. i am really having trouble with conceptualizing these problems that...

Question: i am really having trouble with conceptualizing these problems that...

Question details

I am really having trouble with conceptualizing these problems, that said, more detailed english explanations would be super useful

Socrates the Scientific Squirrel is conducting some experi- ments. Socrates lives in a very tall tree with n branches, and she wants to find out what is the lowest branch so that an acorn will break open when dropped from branch i. (If an acorn breaks open when dropped from branch i, then an acorn will also break open when dropped from branch j for any j 2 i.) The catch is that, once an acorn is broken open, Socrates will eat it immediately and it cant be dropped again.

a)Suppose that Socrates has two acorns. Give a procedure so that she can identify the correct branch using O(Vn) drops [We are expecting: Pseudocode AND a short English description of your algorithm, and a justification of the number of drops. If it helps you may assume that n is a perfect square.] b) Suppose that Socrates has k (1) acorns. Give a procedure so that she can identify the correct branch using O(n1/k) drops [We are expecting: Pseudocode AND a short English description of your algorithm, and a justification of the number of drops. If it helps you many assume that n is of the form n = m for some integer m.] C) What happens to your algorithm in part (d) when k log(n)l1? Is it O(log(n)), like in part (a)? Is it O(n/k) when k-log(n)1, like in part (d)? [We are expecting: A sentence of the form the number of drops of my algorithm in part (d) when k log(n)] +1 is O(), along with justification. Also, two yes/no answers to the two yes/no questions (you should justify your answers but do not need to include a formal proof). d) k acorns, for k = 0(1)? Either give a proof that she cant do better, or give an algorithm with asymptotically fewer drops Is Θ(nl/k) drops is the best that Socrates can do with

Solution by an expert tutor
Blurred Solution
This question has been solved
Subscribe to see this solution