Starting from:

$29

Problem Set 3: Trees and Hashing

1
Problem Set 3: Trees and Hashing
Overview: This assignment will cover that material on trees and hashing. Provide the solutions
for the problems in this assignment a single Microsoft Word document. However, a Power Point
file or scanned handwritten drawing for Problem 1(a) is fine. Remember to include your name and
course number within all documents and files that you submit.
1. [5 points] Trees. Read the assigned chapter and notes for Week 5 located in the Learning
Activities area in Blackboard. Then answer the following questions:
(a) [3 points] Draw a binary tree that produces the inorder traversal for the nodes in the
following order: 19, 24, 39, 77, 11, 76, 84, 71, 29, 34, 53, 36, 22.
Hint: Your tree must a binary tree and not a binary search tree. The tree must produce the
inorder traversal for the nodes listed in the order provided above. There are several ways
that you can draw the tree for this. I recommend that you first draw the tree with links and
empty nodes. Then fill in the nodes with the correct values to produce the inorder traversal
for the list of nodes in the order provided above.
(b) [2 points] Briefly explain the advantages of a binary tree in comparison to a linked list.
2. [5 points] Hashing. Read the assigned chapter and notes for Week 6 located in the Learning
Activities area in Blackboard. Then provide solutions to the following problems:
(a) [2 points] Briefly explain the purpose of quadratic probing and provide an example of a
mathematical function used to implement it. Also, briefly explain the problem associated
with quadratic probing in terms of the number of items within the hash table.
(b) [3 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.
Other Notes: Submit your solutions using the Problem Set 3 link provided in the Assignments
area. 

More products