Data Structures Lab#4 :computer Solution

Description

Instructions

In the previous project (lab), you implemented an algorithm to find the anagrams of a word. For a vocabulary size v, it took O(v logv) to build a BST to store valid words in *english_words*. The purpose of this assignment is to improve the running time of the algorithm by using a hash table instead of a BST.

Your hash table must use chaining to solve collisions. For comparison purposes, you must write multiple hash functions. Also, write a method to determine the average number of comparisons required to perform a successful retrieve operation, and a method to compute the table’s load factor.

In the previous project, we used a BST, so on average, the retrieve operation needed to perform log (354,984) ≈ 18 comparisons. Your hash table (to be successful) needs to perform significantly fewer operation than that (in the ideal case, you’d need exactly 1 comparison per access).

**Hint 1:** The choice of table size and hashing function has a large impact in the number of collisions and thus running time.

**Hint 2:** There are 354,984 English words in words.txt

**Hint 3:** You can think of a word in the English language as a base-26 number.

What you need to do

Part 1 calendar:

Implement the program described above and upload your code to GitHub.

Part 2  :calendar:

Add your team members as collaborators to your GitHub repo. They will add you to their projects as a collaborator as well. Read their code and give them feedback. Use pull requests and/or the Issues section to do so.