Assignment 3: Twenty Questions! [100 Points]
Due Monday, February 6 by 11:59 PM

In this assignment you will implement the 20 Questions Game, described in class, using Java. This is a lot of fun but also requires some careful design. There are also two completely optional bonus problems this week. Most students find this assignment to be more challenging than Assignment 2, so please try to start early!

You will find a compiled version of our solution to this assignment in a file called twenty_questions.class in the directory /cs/cs60/assignments/assignment3. Note that Node.class is the compiled version of Node.java, which in our solution is the class describing a single node in the binary tree. Play this game by running

  java twenty_questions

• The program should start off knowing only one question ("Is it bigger than a breadbox?") and two animals ("a mouse" and "an elephant"). This data should be organized as a binary tree. To make the graders' lives easier, please use this question and these two animals as the starting data.
  
  
• Each time the game is played, the program asks a question (the question at the current node in the tree) and waits for the user's "yes" or "no" response. You should assume throughout this assignment that any answer that starts with the letter 'y' or 'Y' stands for "yes" and anything else stands for "no". Based on this response, the program then asks the next question.
  
  
• At the end of the game, the program has either guessed the animal correctly or doesn't know the animal. In the latter case, the program asks the user to tell it the animal. It is assumed that the user will also specify the correct article ("a" or "an") before the name of the animal, e.g., "an aardvark" or "a giraffe". Then the program asks the user to give it a question that distinguishes between this new animal and the one it found in its binary tree. (It is assumed that the user will give an actual question, ending in a question mark.) Finally, the program asks if the answer to this question would be yes or no for the animal that it has just learned. Now the binary tree is updated to contain all of this new information.
  
  
• The player should then be asked if she or he would like to play again. If the answer is yes, the game should repeat from the root of the tree. If the answer is no, the game should thank the player for playing and then list all of the animals that it knows. This listing should be printed using a recursive traversal of the tree. You should not store the names of the known animals in another data structure (e.g. an array or linked list) - the tree should be the only place where this data is stored. For full credit, keep this code as simple and elegant as possible.

The only slightly "grungy" thing is that of getting input from the user. To demonstrate how input works in Java, we have provided a small demonstration program called IO.java in the directory /cs/cs60/assignments/assignment3. You may use any and all of this code in your own code.

Think about the design of your code before starting to program. We will be grading this program for both functionality and good style. Regarding style, keep the following in mind:

• Break up the problem into small logical chunks and make sure that your methods are short and elegant. If the game is implemented in a single long method, or even a small number of long methods, this is hard to read and debug. Each method should generally be short and have a specific purpose. This will help make the code easy for somebody else to read and comprehend.
• You will need to define a Node class representing a node in the binary tree. Every internal variable in your Node class must be private. You should use getters and setters to get and set the values of these variables.
• Remember to avoid the use of "magic numbers" (or magic values of any sort!) in your code.
• Finally, remember to document your code by providing a header with your name, file name, and date and a description of what the file does. In addition, have at least one line (and ideally even more) of explanation for each method in your code.

Please submit all of the files that comprise your implementation of this game. Undoubtedly, you will have a file describing a node in the binary tree as well as the executable class. If you wish, you may have other files as well. You can use cs60submit multiple times, once for each file that you need to submit. Alternatively, if you type cs60submitall and hit the RETURN key, all of the java files in the directory in which you are currently located will be submitted. cs60submitall will show you the name of each file that it is sumbitting for you.

Optional Bonus Problem 1 (10 Points)

Optional Bonus Problem 2 (10 Points)

In class we looked at B-trees (specifically, "2-3-4 trees") - a beautiful data structure for the Dictionary abstract data type. The wonderful thing about this data structure is that all operations can be performed in O(log n) time. Implement a B-tree class in a file called Btree.java. This class should implement the abstract data type provided in the interface DictionaryADT.java in /cs/cs60/assignments/assignment3/bonus. Specifically, the interface supports the following operations:

• void insert(int n) which inserts the integer n into the Dictionary.
• boolean find(int n) which returns true if integer n is in the tree and false otherwise.
• void inorder() which prints the contents of the tree in order from smallest to largest number.

In addition, you should have a method int height() which returns the height of the tree. Recall from class that the height of a tree is the length of the longest path from the root to a leaf node, where the leaf nodes are assumed to be "null" nodes. Thus, a tree comprising just a single root node with two null children has height 1. An empty tree is a "null" tree and thus has height 0. Do you see why this height method wasn't specified in the DictionaryADT interface, even though we want to have it implemented in the Btree class?

Make sure that your code is well-structured, clean, and readable. Submit your file Btree.java and any other files which it requires. Notice that Btree.java defines a B-tree and is not executable. However, you should write a thorough tester program to make sure that your class functions correctly. We will test your Btree class using our own tester programs.