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 Compute
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
ead?
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 inte
upted 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 Questione
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 co
espond 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?
ca
ot diamond
yes no
yes no yes no
The decision tree is used by the Questioner to represent the cu
ent 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
eaches a leaf. At each node, your Questioner does the following:
• If the cu
ent 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 cu
ent node that
matches the user’s answer.
• If the cu
ent 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
your first name>.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) o
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 cu
ent node. If the user’s response is “no”, then the method should move to the right
child of the cu
ent 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 co
ectly
or not — something like “I guessed co
ectly!” 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 cu
Answe
= JOptionPane.showConfirmDialog(null,
"
",
"20 Questions",
JOptionPane.YES_NO_OPTION,
JOptionPane.QUESTION_MESSAGE);
After this statement is executed, variable cu
Answer will contain either the class constant JOptionPane.YES_OPTION
or the class constant JOptionPane.NO_OPTION. Thus, you just need to compare cu
Answer 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 A4your first name> 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 Questione
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 use
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 inco
ectly 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”) —