Say that your friend picks a word $(w_1, w_2,\dots,w_n)$ according to a known probability distribution $(p_1,p_2,\dots,p_n)$. You ask yes or no questions until you are certain which word has been chosen. For example, you can eliminate a subset $S$ with the question "Is the word in $S$?" The cost of the guessing strategy is the expected number of queries it takes to find the right word. Let an optimal strategy be one that minimizes cost. Design an $O(n \log n)$ algorithm to determine the cost of the optimal strategy.

I'm really confused about this question. I know one strategy would be to ask "is it {word i}" in linear time, but apparently thats nonoptimal? Another thought I had would be to sort the probabilities greatest to least as $(w_a, w_b, w_c,\dots)$ and ask "is it {word a,b...}" until you get the right answer. But I think that could be worst case $O(n \log n + n)$. I guess though that reduces to $O(n \log n)$, but is that the best that we can do?

  • $\begingroup$ There are two aspects, which you seem to be mixing up: (1) Given a list of words and their probabilities, determining which questions to ask; (2) Asking the questions until you identify the word. Almost any strategy you could think of for (1) manages to do (2) in $O(n)$ worst-case time; the question is, can it be done in less? If so, how to design (1) for that? $\endgroup$ Oct 9 at 23:16
  • $\begingroup$ but if we have $O(n log n)$ for coming up with the questions (for example, by sorting) in (1) then even doing $O(n)$ in (2) maintains $O(n log n)$ right? @j_random_hacker $\endgroup$
    – Manny
    Oct 9 at 23:38
  • $\begingroup$ No, you're combining (adding) the two complexities when the question doesn't want you to. (If it did want you to, then the optimal solution would be $O(n)$: Do nothing at all for (1), and ask $n$ questions in any order for (2).) $\endgroup$ Oct 9 at 23:39
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Huffman_coding $\endgroup$ Oct 10 at 6:36
  • 2
    $\begingroup$ Where did you encounter this? We require you to credit the original source of all copied material: cs.stackexchange.com/help/referencing. Please edit your question to provide the proper references. $\endgroup$
    – D.W.
    Oct 10 at 6:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.