Please make sure you are familiar with the resources and policies outlined in the syllabus and the take-home assessments page.

A7 - 20 Questions

Due by Thursday 03/03 at 11:59 pm.

Specification Intro Video Submit Code on Ed

You may submit any part of the assignment as many times as you want before the initial submission. To submit on EdStem, you should use the Mark button to submit your code. You can view your past submissions using the “Submissions” button.

Please make sure you are familiar with the late work policy on the syllabus

Code Files

All files can also be downloaded here: a7.zip

Developing at Home

You are welcome to use Ed as your environment to work on the homework, but we recommend setting up a local environment following our Desktop Software instructions. This will allow you to work offline, and access the great debugger provided by jGrasp! You can download the code from Ed and when you want to submit, upload it again and then pressing Mark to submit.

Useful Resources

Frequently Asked 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, which internally, is 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 tree. 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 tree. 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 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 the code for write/read?

A: These can be tough! Tackle write before read, even though they’re presented in the opposite order. Another useful resource for this is writeTree/readTree from section handout.

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. You might find it very helpful to try to come up with a small Q/A file and try to rebuild a tree from that with pencil and paper. As a hint, there’s no recursive backtracking involved here.

Q: Any tips for development strategy?

A: The spec has an example of one such strategy!