QuestionQuestion

Transcribed TextTranscribed Text

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]); 2 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: Dax hashCode=285 O'Brien hashCode=102 Quark hashCode=4 Dr. Bashier hashCode=450 Kira hashCode=391 B'Elanna hashCode=184 Picard hashCode=83 Riker hashCode=509 Data hashCode=378 La Forge hashCode=192 Worf hashCode=414 Dr. Crusher hashCode=480 Dr. Pulaski hashCode=477 Wesley hashCode=121 Troi hashCode=414 Error: Troi collides at hashCode=414 not inserting Tasha hashCode=497 Sisko hashCode=9 Odo hashCode=290 Bones hashCode=503 Scotty hashCode=134 Chekov hashCode=96 Uhura hashCode=5 Sulu hashCode=425 Nurse Chapel hashCode=122 Reed hashCode=384 Travis hashCode=121 Error: Travis collides at hashCode=121 not inserting Hoshi hashCode=507 Dr. Phlox hashCode=271 Kirk hashCode=401 Spock hashCode=0 Hash Table: Index Key 0 Spock 4 Quark 5 Uhura 9 Sisko 83 Picard 96 Chekov 102 O'Brien 121 Wesley 122 Nurse Chapel 134 Scotty 184 B'Elanna 192 La Forge 271 Dr. Phlox 285 Dax 290 Odo 3 378 Data 384 Reed 391 Kira 401 Kirk 414 Worf 425 Sulu 450 Dr. Bashier 477 Dr. Pulaski 480 Dr. Crusher 497 Tasha 503 Bones 507 Hoshi 509 Riker ** 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 APA format.

Solution PreviewSolution Preview

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...

By purchasing this solution you'll be able to access the following files:
HashCode.cpp and Solution.docx.

50% discount

Hours
Minutes
Seconds
$33.00 $16.50
for this solution

or FREE if you
register a new account!

PayPal, G Pay, ApplePay, Amazon Pay, and all major credit cards accepted.

Find A Tutor

View available Data Structures and Algorithms Tutors

Get College Homework Help.

Are you sure you don't want to upload any files?

Fast tutor response requires as much info as possible.

Decision:
Upload a file
Continue without uploading

SUBMIT YOUR HOMEWORK
We couldn't find that subject.
Please select the best match from the list below.

We'll send you an email right away. If it's not in your inbox, check your spam folder.

  • 1
  • 2
  • 3
Live Chats