1
$\begingroup$

Consider all strictly decreasing functions from {1,2,3,4} to {1,2,3,4,5,6}, or in other words, all functions defined on {1,2,3,4} such that f(1)>f(2)>f(3)>f(4). Draw a decision tree so that the leaves are in lexicographical order when read from left to right. Then answer the following questions:

(a) What is the rank of 5431?

(b) What function has rank 0?

I have been looking all over the internet but I could not find a good resource for decision tree. I would be very appreciate it if anyone could show me how to approach this problem. Thanks

|cite|improve this question|||||
$\endgroup$
  • 1
    $\begingroup$ Try harder to find examples of decision trees. Presumably you were given some in the course. $\endgroup$ – Yuval Filmus May 12 '14 at 0:52
2
$\begingroup$

The decision tree implements the following algorithm for finding $f$:

  1. What is $f(1)$?

  2. What is $f(2)$?

  3. What is $f(3)$?

  4. What is $f(4)$?

There are six possible answers to the first question, but only three of them lead to a valid function. You split according to these answers in the correct order (you want the result to be in lexicographic order), and then continue to the second question. And so on. If you did everything correct, you'll find $\binom{6}{2} = 15$ different leaves, the last of which is $6543$.

|cite|improve this answer|||||
$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.