Egg$-$Drop. Given $2$ eggs and a device to hold the egg, determine the highest floor of

a building of $N$ floors from which the egg will survive the fall. Your method should

improve the method discussed in class.

$(20$ pts$)$

Consider the function hat$(O)$ defined as follows:

iff there exists a positive constant, $c$ and an integer $n_0$ such that

$0f(n)cg(n)logn,$AAn$n_0$

Prove or Disprove

$($a$)f(n)=$hat$(O)(g(n))$ implies $g(n)=$hat$(O)(f(n)).$

$($b$)f(n)=$hat$(O)(g(n))$ implies $logf(n)=$hat$(O)(logg(n)).$

Also prove or disprove:

$($c$)f(n)+o(f(n))=(f(n)).$

$($d$)f(n)+g(n)=(min(f(n),g(n))).$

$(20$ pts$)$

Consider lopsided trees with costs $1$ and $3$ on the left and right branches, respectively,

of the search tree. Characterize the weights $($costs$)$ at the leaves of the optimal trees.

Establish a recurrence for the maximum number of leaf nodes of cost w$(.$ No need to

solve the recurrence$).(30$ pts$)$

Consider a ternary search algorithm similar to binary search algorithm, except that

instead of a comparing with a single array element in each iteration we now have $2$

elements at positions $\frac{1}{3}$ and $\frac{2}{3}$ distance from the beginning of the list. Draw out the

decision tree for a list of $10$ elements and analyze the worst case time of the algorithm

as a function $n,$ the number of elements in the list. $(30$pts$)$