Assignment 4 About Binary tree.
Assignment 4: Trees COMP 2140, Fall 2021 Due: Tuesday 23 November 2021 at 5:00 p.m Instructions • You must complete the “Honesty Declaration” checklist on the course website before you can submit any assignment. • Assignments must follow the programming standards document published on UM Learn. • After the due date and time, assignments may be submitted, but will be subject to a late penalty. Please see the course outline document published on UM Learn for the course policy for late submissions. • If you make multiple submissions, only the most recent version (the last submission) will be marked. We strongly encourage you to submit early! • These assignments are your chance to learn the material for the exams. Code your assignments inde- pendently. We use software to compare all submitted assignments to each other, and pursue academic dishonesty vigorously. • You can get help from the T.A. during your lab section and from the instructors and from the course Assignment 4 discussion forum on UM Learn. You can discuss general topics related to the assignment with fellow students or other people, but you cannot discuss the solution to the assignment with them. You cannot copy code from anywhere except COMP 2140 class notes, unless we tell you otherwise. For a full discussion of our expectations for individual work on this assignment, see the Department of Computer Science’s expectations webpage. • Your Java program must compile and run upon download, without requiring any modifica- tions. The marker will not fix your program’s problems. See also the “Hand in” instructions at the end of this assignment Objective To implement a binary tree (but not a binary SEARCH tree), and to use it to store knowledge for a program that plays “20 questions”. 20 Questions 20 Questions is a game played by two players. One player (the answerer) thinks of a thing (an object). The other player (the questioner) is allowed to ask up to 20 yes/no questions to figure out what object the answerer was thinking of. The answerer must honestly answer the questions. Here’s the beginnings of a game played by Dr. Cameron (questioner) and her husband (answerer): • Question 1: Is it an animal? Answer: No. • Question 2: Is it a plant? Answer: No. 1 https://sci.umanitoba.ca/cs/expectations/ • Question 3: Is it an inanimate object? Answer: Yes. • Question 4: Is it bigger than a loaf of bread? Answer: Yes. • Question 5: Is it in this house? Answer: No. • Question 6: Can I walk to this thing in 10 minutes or less? Answer: No. • Question 7: Have I seen it? Answer: Yes. • Question 8: Is it made by humans? Answer: Yes. • Question 9: Is it in Winnipeg? Answer: Yes. • Question 10: Is it bigger than a human? Answer: Yes. • Question 11: Is it a building? Answer: Yes. • Question 12: It is a place people go for entertainment? Answer: No. • Question 13: Is it west of the Red River? Answer: Yes. • Question 14: Is it south of the Assiniboine River? Answer: Yes. At this point, they got interrupted by a family emergency, so they didn’t end up finishing the game. (The answerer had chosen: The Buller Building at the University of Manitoba.) In this assignment, your program will be the questioner, and the person who runs the program (the “user”) will be the answerer. Assignment Question The assignment is divided into three levels. Each level provides a working game, but with more functionality that the previous level. To get full marks for the assignment, you need to complete all three levels. Level 1: A Really Dumb Questioner Your Questioner will use a binary tree to store knowledge to help it figure out what thing the answerer has thought of — the tree is a decision tree. In a decision tree, a node either has exactly two children — it is an internal node — or it has zero children — it is a leaf. Either way, for your Questioner, a node will contain a String. • Each internal node will contain, as its String item, a yes/no question. • Each internal node will have two children: 2 – The left child will correspond to the “Yes” answer to the question, and – The right child will represent the “No” answer. • Each leaf contains, as its String item, an answer. An example of a binary tree representing a decision tree is given below. Is it an animal? Is it a mammal? human shark Is it a plant? carrot diamond yes no yes no yes no The decision tree is used by the Questioner to represent the current knowledge that the Questioner has while it is playing 20 Questions. For one round of 20 Questions, your Questioner will begin at the root, and move down the tree until it reaches a leaf. At each node, your Questioner does the following: • If the current node is an internal node, your Questioner will display to the user the question stored in the internal node. When the user answers the question, your Questioner will move to the child of the current node that matches the user’s answer. • If the current node is a leaf, then your Questioner will present the guess stored in the leaf to the user: “Are you thinking of a / an ?” At this point the Questioner ends the round. Create an A4
.java (e.g., A4CameronHelen.java) file. Create a public class with a name matching your file name — this class will contain main() and any helper methods it calls. This class will create a Questioner and initiate a round of 20 Questions (more details below), but another class will implement a round of 20 Questions (see next paragraph). Add a second class to your file, the Questioner class. The Questioner class must contain: • A private DTNode (decision tree node) class containing three public instance variables item (a String) and left and right (both DTNodes). The DTNode class should also contain two constructors: – A constructor that is passed only a String. This constructor must initialize the new DTNode to contain the String passed to it and make this DTNode into a leaf. – A constructor that is passed a String and pointers to two DTNodes. This constructor must initialize the new DTNode to contain the String passed to it and make this DTNode into an internal node whose children are the two DTNodes passed to the constructor. – An instance method isLeaf that returns true if the calling DTNode is a leaf (has no children) or false if it is an internal node. The DTNode class should not contain anything else. • A pointer to the root of a decision tree of DTNodes. This decision tree stores the knowledge that the Questioner uses to figure out what thing the Answerer (the user) is thinking of. • A constructor with no parameters that constructs a small (hardcoded) decision tree for the Questioner to use. (You can create the decision tree pictured above, or create your own. Keep it small, however.) 3 • A method playRound with no parameters. This method works its way down the decision tree in a loop, starting from the root and ending at a leaf. If it is at an internal node, the method should ask the question stored in the internal node and get the user’s response (always “yes” or “no”). If the user’s response is “yes”, then the method should move to the left child of the current node. If the user’s response is “no”, then the method should move to the right child of the current node. If it is at a leaf, the method should present the guess stored in the leaf to the user using the following phrase: “Are you thinking of a / an ?” and get the user’s response (always “yes” or “no”). Then the method should respond with an appropriate message, depending on whether it guessed correctly or not — something like “I guessed correctly!” or “I guessed wrong.” After reaching a leaf, the method should end the loop and return. To display a yes/no question in a dialog box and to get the user’s yes / no response (the user clicks on either a “yes” button or a “no” button), use JOptionPane.showConfirmDialog as follows: int currAnswer = JOptionPane.showConfirmDialog(null, "", "20 Questions", JOptionPane.YES_NO_OPTION, JOptionPane.QUESTION_MESSAGE); After this statement is executed, variable currAnswer will contain either the class constant JOptionPane.YES_OPTION or the class constant JOptionPane.NO_OPTION. Thus, you just need to compare currAnswer to the ap- propriate class constant to figure out what the user responded with (yes or no). You will need to import javax.swing.JOptionPane at the top of your file to be able to do these things. You can display a message without requiring a user response as follows: JOptionPane.showMessageDialog(null, ""); Finally, the main() method in your A4 class should do the following: • Display an appropriate opening message, such as “Let’s play 20 Questions!!!”; • Create a Questioner instance and call playRound() on it. • Display an appropriate closing message, such as “20 Questions ends”. If you want to, you can restrict the domain that the user can pick from by having method playRound() display a message such as “Think of a movie” before starting the round. Level 2: A Learning Questioner The Level 1 Questioner has only a small decision tree of knowledge and doesn’t get any better at guessing. In Level 2, the user will be allowed to play multiple rounds of 20 Questions — the program will only stop when the user wants to quit, not after only one round. Furthermore, when the Questioner does not guess the user’s thing, the Questioner will prompt the user to help improve the decision tree. Start with the Level 1 program and make the following changes: • Change the main() method (or its helper method) so that it calls playRound() on the Questioner instance in a loop. After each round, the user should be asked if they want to play another round (prompt the user for a yes / no answer with some message such as “I get better every time I play. Play again?”). The loop should continue until the user doesn’t want to play another round of 20 Questions. • Change the playRound() method in the Questioner class as follows. If the Questioner guesses incorrectly when it reaches a leaf, then the playRound() method should do the following: 4 – Ask the user what they were actually thinking of and get their reply. To display a prompt and read a user’s reply as a String, do the following: String newThing = JOptionPane.showInputDialog("What were you thinking of?"); – Then ask for a Yes/No question that would distinguish between the Questioner’s wrong guess (e.g., “human”) and what the user was thinking of (e.g., “bat”) —