Implement an open hash table
Course:- Data Structure & Algorithms
Reference No.:- EM13412

Assignment Help
Expertsmind Rated 4.9 / 5 based on 47215 reviews.
Review Site
Assignment Help >> Data Structure & Algorithms

In this programming assignment you will implement an open hash table and compare the performance of four hash functions using various prime table sizes.

You will use the table to compare two Shakespeare plays: Hamlet and As You Like It. You will report the number of words that Shakespeare used in both plays.  Have your program read the file hamlet.txt and insert each word into the table. For this assignment, a word will be delimited by a white space, so simple input with >> can be used.  Some of the words will, of course, be nonsense, but we will ignore this.  After inserting all the words from Hamlet, do a lookup for words from the file asyoulikeit.txt.  Store and count the words that are duplicated in the two plays (i.e. words for which the search is successful).  Your count may be slightly less than accurate in reality, since we will not strictly parse the words.  However, each student should come up with the same list of words and the same count.  For each word you insert, compute the number of elements in the bucket that are searched.  Likewise, compute the number of unsuccessful searches.  Report the average number of elements inspected during a search (average number per bucket).   Determine if this is close to the expected size based on the load factor after all words have been inserted.

Repeat your experiment with table sizes of 27691, 55381 and 83,077 using each of the four hash functions.

Data Structures:

  • The hash table must be a template class which uses a linked list to store collisions
  • The underlying physical structure can be a simple, dynamically allocated array or a vector.  
  • The hash table will use an abstract hashing class and four subclasses

Put your comment

Ask Question & Get Answers from Experts
Browse some more (Data Structure & Algorithms) Materials
Heap This question is designed to help you get a better understanding of basic heap operations. You will be given queries of 3 types:• "1 v" -Add an element v to the heap.• "2
Question 1: Declare a double array of size 100. Question 2: Fill out the array with 1 if a random value is greater than 0.5 else 0 Question 3: print the number of 0's in the a
Create a form that lists possible potatoes and toppings in a manner that is easy for counter servers and kitchen crew to scan, and can also be used as input for the inventory
The Binary Tree is one of best ways to organize information when you require fast access. For this project, we will organize a list of names and perform many operations on tho
Discuss when you think a hash table should be used and when you think it should it be avoided. Reply to others with support for or arguments against the use of hash tables in
Running time analysis Given T(n) = 5T(n/2) + n2. Find out its asymptotic tight bound using the Master Theorem. Prove the previous asymptotic tight bound using either substitut
COSC 2007 -Data Structures - The backtracking algorithm helps the mouse by systematically trying all the routes through the maze until it either finds the exit or exhausts a
Two CSMA/CD stations are each trying to transmit long documents. After each frame is sent, they contend for the channel using the binary exponential backoff algorithm.