Homework Assignment #2

Due Friday, October 4, 11:59 pm
55 points total

1. (20 pts) Binary Search Trees

1. Write a program that fills an array with 20 random ints in the range 0-100, inclusive. Insert each integer into a binary search tree (you must write the BST implementation, don't use a pre-built class). Then delete the first and last numbers that are in the array from the BST. Output the contents of the BST in sorted order after the two elements have been deleted.


2. Write a function that returns true if a tree is a BST, and false otherwise. Test the function with a tree that is a BST and a tree that is not a BST (you might generate the non-BST by making a BST first and then corrupting the data somehow to break the binary search tree property).

2. (15 pts). Dictionary Hashing.

Use C++ to write a simple spell checker using a hash table. You are free to choose your own hash function but effort should be made to use a good hash function. Describe how your hash function works and why you think it is good in the comments for the function. Your program should:

1. Read in this file of 45407 words: words.txt. Insert each word, converted to lowercase, into a hash table that uses chaining with a list to handle collisions. (You may want to start with a smaller word file for testing)
2. Allow the user to type in a word and output whether or not the word is in the dictionary.

1. Hash table size = 60,331 with chaining
2. Hash table size = 120,721 with chaining

1. Hash table size = 60,331 with linear probing
2. Hash table size = 120,721 with linear probing

3. (15 pts). Mind Reader.

The theme of this program is to write a program in C++ that will "read" the mind of the player. You should be able to re-use your hash table code from the previous problem with some minor revisions. The program interaction is as follows:

The user needs to pick either heads or tails. Before the user makes his/her pick the program will make a prediction as to whether the user is going to pick head or tail. The programs prediction is hidden from the user until he makes his actual pick. Once the user makes his pick the programs prediction is revealed. If the program correctly predicted the users pick it gets a point otherwise if the program misses the user gets a point. Who ever (program or user) gets 25 points first is deemed the winner.

Welcome to MindReader

Guess heads or tails and I'll predict your guess.
What is your pick [h/t] ? t
No. I predicted h
Score = Comp: 0 | Player: 1

Guess heads or tails and I'll predict your guess.
What is your pick [h/t] ? h
Yes!. I too predicted h
Score = Comp: 1 | Player: 1

Guess heads or tails and I'll predict your guess.
What is your pick [h/t] ? t
No. I predicted h
Score = Comp: 1 | Player: 2

Guess heads or tails and I'll predict your guess.
What is your pick [h/t] ?

...

The "AI" of the program should use a hash table. The lookup string should consist of the last 1-4 picks made by the player. For example, if the first pick is "t" then the lookup in the hash table is "" because there is no previous pick. If the second pick is "h" then the lookup string is "t" which is the past pick. If the third pick is "h" then the lookup in the hash table is "th" which is the first "t" and the second pick of "h". If the fourth pick is "t" then the lookup in the hash table is "thh" which is the first-third picks. If the fifth pick is "t" then the lookup in the hash table is "thht". If the sixth pick is "t" then the leftmost "t" is lost and the lookup becomes "hhtt". From this point on the lookup key is always 4 characters.

Rather than store the key in the hash table, for a given key the hash table should store two integers (or an object with two integers). One of the integers should count the number of times the next pick in the sequence for that key was heads, and how many times the next pick for that key was tails. For each pick made by the player you should update the counters for up to 4 entries in the hash table: For the last 4, last 3, last 2, and last 1 picks made. In the example above:

• First pick of "t" past key = "". Nothing updated since no previous key.
• Second pick of "h" past key = "t". Update hash table entry for "t" with 1 heads, 0 tails.
• Third pick of "t" past key = "th". Update hash table entry for "h" with 0 heads, 1 tails. Update hash table entry for "th" is updated to indicate 0 heads, 1 tails.
• Fourth pick of "t" past key = "tht". Update hash table entry for "t" with 1 heads, 1 tails. Update hash table entry for "ht" with 0 heads, 1 tails. Update hash table entry for "tht" with 0 heads, 1 tails.
• Fifth pick of "t" past key = "thtt". Update hash table entry for "t" with 1 heads, 2 tails. Update hash table entry for "tt" with 0 heads, 1 tails. Update hash table entry for "htt" with 0 heads, 1 tails. Update hash table entry for "thtt" with 0 heads, 1 tails.
• Sixth pick of "h" past key = "httt". Update hash table entry for "t" with 2 heads, 2 tails. Update hash table entry for "tt" with 1 heads, 1 tails. Update hash table entry for "ttt" with 1 heads, 0 tails. Update hash table entry for "httt" with 1 heads, 0 tails.

To make a prediction the program picks whichever option appeared more times. If there is a tie, randomly pick heads or tails. If there is no hash table entry for the key, try with a key of length 3 (use only the previous three picks). If there is still no hash table entry, try a key of length 2, then a key of length 1. If there is no entry for a key of length 1 then randomly pick heads or tails.

4. (5 pts). Mind Reader Again.

Re-do the same program but use a C++ map to implement the program. The behaviour should otherwise be the same.