Question

implement the above in c++, you will write a test program named create_and_test_hash.cc . Your programs should run from the terminal like so:
./create_and_test_hash <words file name> <query words file name> <flag> <flag> should be “quadratic” for quadratic probing, “linear” for linear probing, and “double” for double hashing. For example, you can write on the terminal:
./create_and_test_hash words.txt query_words.txt quadratic You can use the provided makefile in order to compile and test your code. Resources have been posted on how to use makefiles. For double hashing, the format will be slightly different, namely as follows:
./create_and_test_hash words.txt query_words.txt double <R VALUE> The R value should be used in your implementation of the double hashing technique discussed in class and described in the textbook: hash2 (x) = R – (x mod R). Q1. Part 1 (15 points) Modify the code provided, for quadratic and linear probing and test create_and_test_hash. Do NOT write any functionality inside the main() function within create_and_test_hash.cc. Write all functionality inside the testWrapperFunction() within that file. We will be using our own main, directly calling testWrapperFunction().This wrapper function is passed all the command line arguments as you would normally have in a main. You will print the values mentioned in part A above, followed by queried words, whether they are found, and how many probes it took to determine so. Exact deliverables and output format are described at the end of the file. Q1. Part 2 (20 points) Write code to implement double_hashing.h, and test using create_and_test_hash. This will be a variation on quadratic probing. The difference will lie in the function FindPos(), that has to now provide probes using a different strategy. As the second hash function, use the one discussed in class and found in the textbook hash2 (x) = R – (x mod R). We will test your code with our own R values. Further, please specify which R values you used for testing your program inside your README. Remember to NOT have any functionality inside the main() of create_and_test_hash.cc
You will print the current R value, the values mentioned in part A above, followed by queried words, whether they are found, and how many probes it took to determine so. Exact deliverables and output format are described at the end of the file. Q1. Part 3 (35 points) Now you are ready to implement a spell checker by using a linear or quadratic or double hashing algorithm. Given a document, your program should output all of the correctly spelled words, labeled as such, and all of the misspelled words. For each misspelled word you should provide a list of candidate corrections from the dictionary, that can be formed by applying one of the following rules to the misspelled word: a) Adding one character in any possible position b) Removing one character from the word c) Swapping adjacent characters in the word Your program should run as follows: ./spell_check <document file> <dictionary file>

You will be provided with a small document named document1_short.txt, document_1.txt, and a dictionary file with approximately 100k words named wordsEN.txt. As an example, your spell checker should correct the following mistakes. comlete -> complete (case a) deciasion -> decision (case b) lwa -> law (case c)

Correct any word that does not exist in the dictionary file provided, (even if it is correct in the English language). Some hints: 1. Note that the dictionary we provide is a subset of the actual English dictionary, as long as your spell check is logical you will get the grade. For instance, the letter “i” is not in the dictionary and the correction could be “in”, “if” or even “hi”. This is an acceptable output. 2. Also, if “Editor’s” is corrected to “editors” that is ok. (case B, remove character) 3. We suggest all punctuation at the beginning and end be removed and for all words convert the letters to lower case (for e.g. Hello! is replaced with hello, before the spell checking itself).

Do NOT write any functionality inside the main() function within spell_check.cc. Write all functionality inside the testSpellingWrapper() within that file. We will be using our own main, directly calling testSpellingWrapper(). This wrapper function is passed all the command line arguments as you would normally have in a main

Answer 1

Firstly write the source code as mentioned below:-

/*
 * First C++ program that says hello (hello.cpp)
 */
#include <iostream>    // Needed to perform IO operations
using namespace std;
 
int main() {                        // Program entry point
   cout << "hello, world" << endl;  // Say Hello
   return 0;                        // Terminate main()
}                                   // End of main function

Build and Run the Executable code :-

// Windows (CMD shell) - Run "hello.exe" (.exe is optional)
> hello
hello, world
 
// UNIX/Linux/Mac (Bash shell) - Run "hello" (./ denotes the current directory)
$ ./hello
hello, world

A hash table is a data structure which is used to store key-value pairs. Hash function is used by hash table to compute an index into an array in which an element will be inserted or searched.

Double hashing is a collision resolving technique in Open Addressed Hash tables. Double hashing uses the idea of using a second hash function to key when a collision occurs.

This is a C++ program to Implement Hash Tables chaining with double hashing.

#include <iostream>
#include <cstdlib>
#define T_S 5
using namespace std;
enum EntryType {Legi, Emp};
struct HashTableEntry {
   int e;
   enum EntryType info;
};
struct HashTable {
   int s;
   HashTableEntry *t;
};
int HashFunc1(int k, int s) {
   return k % s;
}
int HashFunc2(int k, int s) {
   return (k * s - 1) % s;
}
HashTable *initiateTable(int s) {
   HashTable *ht;
   if (s < T_S) {
      cout<<"Table Size is Too Small"<<endl;
      return NULL;
   }
   ht= new HashTable;
   if (ht == NULL) {
      cout<<"Out of Space"<<endl;
      return NULL;
   }
   ht->s = s;
   ht->t = new HashTableEntry[ht->s];
   if (ht->t== NULL) {
      cout<<"Table Size is Too Small"<<endl;
      return NULL;
   }
   for (int i = 0; i < ht->s; i++) {
      ht->t[i].info = Emp;
      ht->t[i].e=NULL;
   }
   return ht;
}
int SearchKey(int k, HashTable *ht) {
   int hashVal= HashFunc1(k, ht->s);
   int stepSize= HashFunc2(k, ht->s);
   while (ht->t[hashVal].info != Emp &&
      ht->t[hashVal].e != k) {
         hashVal = hashVal + stepSize;
         hashVal = hashVal % ht->s;
      }
      return hashVal;
}
void Insert(int k, HashTable *ht) {
   int pos = SearchKey(k, ht);
   if (ht->t[pos].info != Legi ) {
      ht->t[pos].info = Legi;
      ht->t[pos].e = k;
   }
}
void display(HashTable *ht) {
   for (int i = 0; i < ht->s; i++) {
      int v= ht->t[i].e;
      if (!v)
         cout<<"Position: "<<i + 1<<" Element: Null"<<endl;
      else
         cout<<"Position: "<<i + 1<<" Element: "<<v<<endl;
   }
}
HashTable *Rehash(HashTable *ht) {
   int s = ht->s;
   HashTableEntry *t= ht->t;
   ht = initiateTable(2*s);
   for (int i = 0; i < s; i++) {
      if (t[i].info == Legi)
         Insert(t[i].e, ht);
   }
   free(t);
   return ht;
}
int main() {
   int v, s, pos, i = 1;
   int c;
   HashTable *ht;
   while(1) {
      cout<<"1.Initialize size of the table"<<endl;
      cout<<"2.Insert element into the table"<<endl;
      cout<<"3.Display Hash Table"<<endl;
      cout<<"4.Rehash Hash Table"<<endl;
      cout<<"5.Exit"<<endl;
      cout<<"Enter your choice: ";
      cin>>c;
      switch(c) {
         case 1:
            cout<<"Enter size of the Hash Table: ";
            cin>>s;
            ht = initiateTable(s);
         break;
         case 2:
            if (i > ht->s) {
               cout<<"Table is Full, Rehash the table"<<endl;
               continue;
            }
            cout<<"Enter element to be inserted: ";
            cin>>v;
            Insert(v, ht);
            i++;
         break;
         case 3:
            display(ht);
         break;
         case 4:
            ht= Rehash(ht);
         break;
         case 5:
            exit(1);
         default:
         cout<<"\nEnter correct option\n";
      }
   }
   return 0;
}