Overview: This assignment will cover that material on trees and hashing. For problems 2(a) of
this assignment, you will need a C++ compiler. In order to receive credit, your program
must compile and run; and you must provide the actual source code file so that I can compile and
run your programs (the file ending in .cpp). Provide the solutions for the remaining parts of
this assignment a Microsoft Word document. A Power Point file or scanned handwritten drawing
for Problem 1(a) is also fine. Remember to include your name and course number within all
documents and files that you submit.
1. [5 points] Trees. Answer the following questions:
(a) [3 points] Draw a binary search tree (BST) for the following nodes: 14, 2, 1, 87, 32, 112,
68, 31, 61, 22, 44, 34.
Hint: Your tree must a BST instead of just a regular binary tree. There are a few ways that you can
arrange the layout for this tree; however, remember data within the tree must follow the rules of a
BST. I recommend that you first draw the tree with links and empty nodes. Then sort the items and
place them in the appropriate places within the tree so that it forms a BST.
(b) [2 points] Briefly explain the differences between a binary search tree (BST) and an
Adelson-Velskii and Landis (AVL) tree.
2. [5 points] Hashing. Provide solutions to the following problems:
(a) [3 points] Download the HashCode.cpp file and implement the details of the functions
called calculateHash() and insertTable(). The calculateHash() function takes a
given string and adds the ASCII value for each character in the string to produce a hash
code based on the size of the hash table. The hash code can be generated by taking the
value of the sum of the characters modulo the size of the hash table (which will be 512 in
our program). The insertTable() takes the given hash code and the key (or string) and
inserts it into the hash table. This function should print an error message if there is a
collision in the hash table. You do not have to resolve collisions.
Hint: As with the other programming assignments, you only need to provide the details for the
areas of the code that are marked with TODO comments. All of the other areas of code, including
the data strings, and function signatures will not change. For the calculateHash() function, create
a for-loop similar to the one in the displayHashTable() function, except this your function will
add the value of each character in the string based on the length of the string. For example, declare
an integer variable (sum) and add the ASCII value of each character to the integer:
sum = sum + static_cast<int>(key[index]);
After the loop return the modulus of the sum variable with the size of the hash table. Set the size of
the hash table variable size at the top of the file to 512.
For the insertTable() function, use an if-statement to check whether or not the location in the
hash table is occupied. You can use the length() or size() string function to test whether or not
the string is equal to 0. This will be similar to the check that is performed in the
displayHashTable() function, except you will use the hashCode variable instead of the variable
i. Print an error message if the position in the hash table is occupied and do not insert the string
into the hash table.
Output: The error message may be different, but the remaining output for the program after the
function is implemented should appear as follows:
Dr. Bashier hashCode=450
La Forge hashCode=192
Dr. Crusher hashCode=480
Dr. Pulaski hashCode=477
Error: Troi collides at hashCode=414 not inserting
Nurse Chapel hashCode=122
Error: Travis collides at hashCode=121 not inserting
Dr. Phlox hashCode=271
122 Nurse Chapel
192 La Forge
271 Dr. Phlox
450 Dr. Bashier
477 Dr. Pulaski
480 Dr. Crusher
** Press any key to continue **
(b) [2 points] Perform an Internet search and briefly discuss in a few paragraphs a computer
related algorithm based on hashing. Provide an example with a diagram or table to help
illustrate how the algorithm works. List your sources at the end of your paragraphs using
These solutions may offer step-by-step problem-solving explanations or good writing examples that include modern styles of formatting and construction
of bibliographies out of text citations and references. Students may use these solutions for personal skill-building and practice.
Unethical use is strictly forbidden.
1. a) The BST that can be drawn is not unique; no matter which of them is drawn it is needed to preserve BST property: the value of a node is greater than the values stored in its left child (sub-tree) and less than the values from its right child (sub-tree).
The first BST follows the recommendation to sort the values in non-decreasing order like 1, 2, 14, 22, 31, 32, 34, 44, 61, 68, 87 and 112 before arranging them in the BST from Figure 1. The requirement of the problem is not to draw a balanced BST; hence it is not necessary to worry about how the BST looks like as long as the BST property is maintained...