Prelab 4: Decision Trees

1. Read Chapter 2 in Great Ideas in Computer Science with Java.

2. Draw a decision tree for some task on a sheet of paper. The task will be one of your own choosing which gives advice on some topic on which you are an "expert". Here are some ideas:

   1. How to get out of bed in the morning?
   2. How to stay awake in CPS1 class?
   3. How to be admitted to a prestigious university?
   4. How to flunk out of a prestigious university?

   You may choose any topic for a decision tree you desire. Particularly original or humorous ideas promote favoritism from the lab TAs. Negative points for offending the staff. Draw your decision tree complete with location numbers, indicating the root and leaf nodes. The tree should be at least 4 levels deep, meaning that you should have a total of 15 nodes! (There should be at least 7 questions total and 8 possible final answers.)

Questions

Turn in the answers to the following questions along with your decision tree for your prelab

1. Give at least 2 examples of real life decision trees.
2. For the reasonable decision trees that you have seen thus far, what is the general relationship between the number of questions and the number of answers?
3. The tree you have designed is considered to have a depth of 4. How many nodes would you have if you were to have a tree with a depth of 5? What is the general formula for the number of nodes in an n depth tree?
4. How does this formula change if each question had 3 options rather than 2? That is what if the possible answers for all of the questions were "Yes", "No", and "I don't know", how many nodes would an n depth tree have then?