The code must produce the edit.txt file to be imported into DSWB to produce a graph.

Modify this code where it says to in the comment lines:

#include \"stdafx.h\" using namespace std; #include #include #include

#include #include void genData(int *, int); int radixSort(int *, int);

void genData(int *dta, int n) {// generate numerical equivalents of 5 character strings (examples, \"ABCDE\" ) for(int i=0; i { int sum = 0; for(int j = 0; j sum = sum + rand()%26 * (int)pow(26., j); dta[i] = sum; } }

// *********************** bool isPrime(int x) // you write this function { // this is just a stub, you have to write it. I had to put something here else it won't link. return false; // this is here to satisfy the compiler. Your can change it. }

int ComputeNearestPrime(int x) { // return the nearest prime number larger than 2 * x + 1 // don't call this with an even number or if you do, then check the argument and if it's even, add 1 to it. // don't return a zero return 3; // ** TAKE THIS STATEMENT OUT WHEN YOU START WRITING YOUR OWN CODE - IT IS ONLY HERE SO WHEN YOU RUN THE CODE (BEFORE YOU CHANGE ANYTHING) IT WILL NOT HANG ** } // *************************

void Hash(int *dta, int n, int &counter, int *&HashTable, int &TableSize, int swch) { // It is important that you use the arguments as follows since the values get returned to the main program.

// dta is the numerical data to hash // n is the amount of data in dta // counterinear is the variable you use for counting probes and stores // HashTable is the variable you use as the hash table // TableSize is the variable you use for the TableSize // swch is either 0 or 1, depending on whether you are doing linear or quadratic probing // The shell calls this function twice for every data set. The first time, swch will be zero (linear probing) // the second time it will be 1 for quadratic probing. Write your code to handle this. // compute TableSize (prime number > 2 * n)

TableSize = ComputeNearestPrime(2*n + 1); // you write this function - computes nearest prime closest but greater than 2 * n

try { HashTable = new int [TableSize]; if(HashTable == NULL)throw \"allocation error\"; } catch (...) { cout } for(int i = 0; i counter = 0; int R; if (TableSize / 3 => else R = ComputeNearestPrime(TableSize/3); // for use in double hashing (this is the for the second hash h(x) = (x%Ts + i * (R - x%R))%Ts // you write the code that does the hashing // *********************** // YOUR CODE GOES HERE // ************************

return; }

The rest of the code that doesn't need to be changed:

Obreak; if( / Main program to run the hash function // This code produces a csv (excel) spread sheet for graphing. // It also produces a graphng file for SDIAPP.exe if you dont want to use Excel // Debug files containing the hash tables are also produced. These can be disabled. #define limit 1000 Il increase this if you get zeroes in the timing data Fint _tmain(int argc, TCHAR* argv[]) { int *data;// pointer to where data will be stored int N = 2;// initial size of the SSN data set. int count_linear = 0; // return argument holding value of linear probe count int count_quadratic = 0;// return argument holding value of quadratic probe count int count_double_hashing = 0;// return argument holding value of double hashing probe count 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 int tablesize = 0; int *hashtable_1 = NULL; // holds hash table created by the Hash function (for debug printout ) for linear probing int *hashtable_q = NULL; // holds hash table created by the Hash function (for debug printout ) for quadratic probing int *hashtable_d = NULL; // holds hash table created by the Hash function (for debug printout ) for double hashing int Nalues[15]; // holds values of N for creating a data file that can be read by SDIAPP.exe int LC[15]; // holds values of linear probe count for creating a data file that can be read by DSWB int QC[15]; // holds values of quadratic probe for creating a data file that can be read by DSWB int DC[15]; // holds values of double hashing for creating a data file that can be read by DSWB double D[16]; // holds times double E[16]; // holds times double F[16]; // holds times _mkdir(\"data\"); // already there, it won't do anything ofstream f; ofstream f1; f.open(\"output.csv\", ios::out);// open the output excel file if(f.is_open())// if it opened, proceed, else issue error and quit { for(int i = 0; i @break; if(i @)break; if(i Obreak; if( ;>