CSE 143: Computer Programming II, Summer 2017

Homework 7 (20 Questions) FAQ

Q: What does this program do?

A: Briefly, this program allows you to play the game 20 Questions, where you think of an object and the computer tries to guess it by asking you yes or no questions. When the computer fails to guess your object, it will remember the object along with a new question about it to help it guess correctly in the future.

Q: But how does that translate into Java?

A: The yes/no structure of the game 20 questions lends itself well to a binary tree. This program will use a QuestionsGame made up of QuestionNodes. It is up to you to create the QuestionNode, as well. It may help to think of a QuestionNode like the nodes in a normal binary tree. In this case, QuestionNodes keep track of a piece of data and have two pointers to other QuestionNodes. This is so that the QuestionNode can keep track of a question and then a pointer for the yes direction and a pointer for the no direction. When the game is played, the computer can ask a question by starting with the question stored in the root of the QuestionsGame. Then, the user answers yes or no, and you can go deeper into the tree by following the appropriate yes or no pointer in that QuestionNode. Then, you can repeat the process until you find a potential answer. If the answer is not what the user was thinking then you can add a new node to the QuestionsGame. This node will have a new question in it (that the user provides) and it points to the object that the user was thinking of and the answer you guessed that was incorrect. If you are still having trouble understanding this process, take some time to understand the diagrams on the first two pages of the writeup.

Q: My play method doesn't modify the tree! Why not?

A: Remember you have to use the model x = change(x)! Put another way, you have to pass in a node's old state, change it, then return its new state. Take a look at the BST add and remove code from lecture, or the Thursday section problems that modify a tree.

Q: I think my tree is getting corrupted. How do I see for sure and fix it?

A: One of your best tools for this is the jGRASP debugger. It is a powerful visualization tool for binary trees.

Q: How do I write load/save?

A: These are tough. Tackle save before load, even though they're presented in the opposite order. Another useful resource for this is writeTree/readTree from section handout #16.

Q: I don't really see the relationship between the Q/A file and the tree. How do you know the tree's structure just from that 'flat' file?

A: Focus on saving, first, to get familiar with how the file is created. It may help to draw simple trees and write out the corresponding file. As a hint, there's no recursive backtracking involved here. Having faith in recursion is definitely necessary. Hopefully, after a little practice, you'll be a little more familiar with the concept and understand the principles enough to implement them.

Q: Any tips for development strategy?

A: A couple:

• Start with a really small test file (even smaller than spec-questions.txt). Try just a leaf answer. Then try one question with two answer leaves under it. Etc.
• Look at examples from lecture and section to relate to the problems you need to solve on this assignment