MPCS 55001 — Problem Set 4

Instructions

This problem set is due on Wednesday May 6, 2020 at 20:00 Central, to be submitted on Gradescope. Each problem is worth 10 marks in total.

Problems

1. Determine the asymptotic growth of the following recurrences. You should justify your answer, but you do not need to give a formal proof.
   1. $T(n) = T\left(\frac n 2\right) + 2$
   2. $T(n) = 5 T\left(\frac n 6\right) + 4n$
   3. $T(n) = 11 T\left(\frac n 2\right) + n \log n$
2. You are asked to certify the results of a very important poll to determine the most popular historical figure. You are given limited access to the results $V$ via the following functions:
   • poll(V) returns the result of one vote, uniformly at random.
   • next(V) returns the result of the "next" vote. You can use next() to iterate through the votes in no particular order. It will return null if you have iterated through all of the votes.
   • votes(V) gives you the total number of votes.
   • reset(V) resets the iteration.
   Each of these functions have $O(1)$ running time. Suppose the results are

   {Gilgamesh, Jeanne d'Arc, Gilgamesh, Gilgamesh, Jeanne d'Arc, Zhuge Liang, Gilgamesh, Cú Chulainn, Hans Christian Andersen, Oda Nobunaga, Jeanne d'Arc}.

   Then votes(V) returns 11. Calling poll(V) will return one member, chosen at random with uniform probability, from the set of results. Calling next(V) repeatedly will result in iterating through members of the set one at a time, for example, a series of calls to next(V) returns in succession:

   Gilgamesh, Gilgamesh, Hans Christian Andersen, Zhuge Liang, Jeanne d'Arc, Oda Nobunaga, Jeanne d'Arc, Gilgamesh, Jeanne d'Arc, Gilgamesh, Cú Chulainn.

   Calling next(V) after iterating through the entire set will return null until reset(V) is called. After reset(V) is called, calling next(V) will iterate through members of the set again, in some order. The order in which the set is iterated through is not guaranteed to be the same.
   
   Suppose you have been assured that there is a clear winner; i.e. someone has 50%+1 of the votes. Give a randomized algorithm, in pseudocode, that determines, when given $V$, who won in $O(n)$ expected time and $O(1)$ space. Give proofs for correctness and efficiency.
3. Now, suppose that the results of the vote from Problem 2 are not guaranteed to have a clear winner. You are now given access to an additional function partition(V) which, in $O(1)$ time, returns a partition of $V$ into two sets $(V_1,V_2)$ with $|V_1| = \left\lfloor \frac n 2 \right\rfloor$ and $|V_2| = \left\lceil \frac n 2 \right\rceil$. All of the available functions can be called on $V_1$ and $V_2$.
   
   Give a deterministic algorithm in pseudocode that, given $V$, determines whether there is a clear winner and if there is a clear winner, who it is, in $O(n \log n)$ time and $O(1)$ space at each level of recursion (for a total of $O(\log n)$). Give proofs for correctness and efficiency.