CS 14 - Question Tree

CS 14 Question Tree

In this assignment you will be writing a program that "learns" how to guess what object you are thinking of. Unfortunately it starts out quite dumb, but it never makes the same mistake twice, which is at least better than some humans.

To begin with, your program is only aware of two possible things you could guess: an elephant or a mouse. It knows a very good question to initially differentiate between these two: "Is it bigger than a breadbox?" If the answer is yes, it will guess "an elephant" if no it will guess "a mouse." If the program's guess is wrong, you can tell it what you were thinking of, along with how to differentiate between what it guessed and the right answer.

How It Works

To implement this program, you will want to implement a binary tree. (This is actually a special form of binary tree called the Binary Decision Tree.) Leaves of the tree are guesses. At each non-leaf node there is a question. Every guess for which the answer to a question is "yes" will fall on the "yes" side of that question. Keeping in mind the properties of binary trees, this means that there is always one more guess than question.

Your program will thus repeatedly traverse the tree, asking questions at each node. When a leaf is reached, it makes a guess. If it guessed correctly (the guess at that leaf was what the user was thinking of) then nothing needs to happen. If not, then the tree needs to have a new question added, and the computer's guess and the user's correct answer need to be added as children of that question. (This is a little bit complicated, it probably helps if you draw it out on paper to see what we are talking about.)

The Spec

For this assignment, rather than giving you a complete specification, we are providing you a "black box:" the sample solution for the assignment in compiled form. Your job is to write source code that when compiled behaves exactly the same as this binary sample. Most of the rubric points will be given to things with the same basic functionality, but some points will be reserved for duplicating our error handling and such.

The sample can be found here: questiontree

To run this, download it to your Linux account, and run the following commands:

chmod +x questiontree
./questiontree

(you only need to change the permissions by using chmod the first time you run the program.)

Your assignment is to duplicate the above program as accurately as possible. This includes error handling, punctuation, spacing, prompts and the like. Ideally we should be able take your solution and our solution, feed any arbitrary input into both of them, and get the exact same results.

Since this requires some fairly extensive time spent tinkering with the sample, we are breaking this assignment into two parts, as follows:

Phase 1: Test cases (25%)

By Sunday, November 16th at 8pm you must submit a set of test cases that rigorously test the program. You may turn in as many or as few tests as you like. We will be using a program called "gcov" (information readily available online) to see what percentage of our code you tested with your tests, and award points accordingly. Note that this is a large fraction of the grade for this assignment: you cannot score higher than a C if you do not do this well.

The idea here is called "test coverage": you want to make sure that as much of the program as possible is tested by the inputs you give it. Just like it doesn't count to "test" your linked list code by only ever calling insert at head, we want to give the program as varied input as possible. You want to test what happens when the input is in a form that wasn't expected. You want to test what happens when the user enters duplicate questions, you want to test what happens when everything goes well. You want to test everything that can possibly happen. A million monkeys at a million keyboards typing for a million years will probably generate all of the useful tests for this program, your goal is to cut out the randomness, the useless repetitions, and hone it down to just writing a good, basic set of tests. This is a skill you NEED to pick up, especially those of you that have turned in assignments this quarter thinking that they work and then gotten startlingly low grades on them. Complicated tests, and testing as you go, are the only way to know that you are doing the right thing.

If you have additional questions about testing and coverage, ask the mailing list, or check Google.

Your test cases should be simple text files. Each test should have an input and an output file for it. You can create the input files in a basic text editor, and generate the output files as follows:

./questiontree < myTest1.input > myTest1.output

If you have created myTest1.input this will create the proper contents for myTest1.output. All tests must have a .input and a .output. Files named incorrectly will be ignored, NO EXCEPTIONS.

The files for a sample test can be found here: test1.input test1.output

Phase 2: Implementation (75%)

By Sunday, November 23rd at 8pm you must submit your implementation of this program. PLEASE SUBMIT ONLY 1 SOURCE FILE.

Bonus Credit

You may earn 15% bonus credit for providing a second version (that is, another file, very similar to the first) of your program that does not restart with a single-question tree every time the program is started up (that is, it does saving and loading of the tree to a file).