CS3330 Data Structures and Algorithms

Problem Set 3: Trees and Hashing
CS3330 Data Structures and Algorithms
Term 1 2016: August 15 – October 15
Dr. Jack Davault
Overview: This assignment will cover that material on trees and hashing. Provide the solutions
for the problems in this assignment within 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 an Adelson-Velskii and Landis (AVL) tree for the following nodes: 64,
28, 51, 66, 15, 36, 74, 73, 12, 78, 82, 83, 86, 99, 21.
Hint: No coding is involved with this problem. You need to draw the actual tree for this problem.

When you draw your tree, it must an AVL tree instead of just a regular binary tree or a
binary search tree (BST). 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 an AVL tree. I recommend
that you first draw the tree with links and empty nodes. Then sort the items in the list and
place them in the appropriate places within the tree so that it forms an AVL tree.
(b) [2 points] Briefly explain the differences between a binary search tree and a regular binary
tree. Which tree has a better advantage over the other? Briefly explain why.
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 based on the size of the hash table. 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. As usual, please do not hesitate to ask questions in the Ask the Instructor forum or via e-mail.

1

Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.