I am working on this assignment and i find it's pretty hard for me. Please help me to solve it!

 

 

CSC 225 - SPRING 2017
ALGORITHMS AND DATA STRUCTURES I
PROGRAMMING ASSIGNMENT 3
UNIVERSITY OF VICTORIA 1 Programming Assignment The assignment is to implement a hash table for strings of characters which uses
open addressing and quadratic probing to resolve collisions. The data structure used
to represent the hash table must be an array.
Your implementation must be be able to insert an arbitrary number of strings into
the hash table as well as remove strings from the hash table. (Hint. you cannot use a
special indicator string to represent a deleted location in the hash table. Instead, each
location will have to maintain a status and a value.) Furthermore, the load factor of
your hash table must remain in the range [0.25, 0.75] at all times. Therefore, when
inserting or removing a string that would move the load factor outside this range,
the hash table will need to be resized. You may use any resizing scheme you choose.
Note, the size of the hash table must be prime after each resize operation.
A Java template has been provided containing empty functions hash insert,
find, remove, and resize. Your task is to write the body of each of the functions.
You must use the provided Java template as the basis of your submission, and put
your implementation inside the provided functions in the template. You may not
change the name, return type or parameters of any of the provided functions. You
may add additional functions and classes as needed. Since you are are only permitted
to submit one file, any extra classes must be contained in the HashTable.java file.
The main function in the template contains code to help you test your implementation by entering test data or reading it from a file. You may modify the
main function, but only the contents of the provided functions (and any functions
or classes you have added) will be marked, since the main function will be deleted
before marking begins. Please read through the comments in the template file before
starting.
1 2 Test Datasets The dataset for this assignment will be a collection of place names (cities, towns, etc.).
A set of input files containing test data are available on conneX. You should ensure
that your implementation behaves correctly on these test files before submitting. It
may also be helpful to test your implementation on a variety of other inputs, since
the posted data may not cover all possible cases. 3 Evaluation Criteria The programming assignment will be marked out of 20, based on a combination of
automated testing (using test data similar to the ones posted on conneX) and human
inspection.
Score
0-5 Description
Submission does not compile or does not conform to the
provided template.
6 - 10 The implemented hash table is substantially inaccurate
on the tested inputs.
11 - 16 The implemented hash table is partially complete, with
some of the required functions not working correctly.
17 - 20 The implemented hash table is complete and implements
each of the required functions correctly.
To be properly tested, every submission must compile correctly as submitted, and
must be based on the provided template. If your submission does not compile
for any reason (even trivial mistakes like typos), or was not based on the
template, it will receive at most 5 out of 20. The best way to make sure
your submission is correct is to download it from conneX after submitting and test
it. You are not permitted to revise your submission after the due date, and late
submissions will not be accepted, so you should ensure that you have submitted the
correct version of your code before the due date. conneX will allow you to change
your submission before the due date if you notice a mistake. After submitting your
assignment, conneX will automatically send you a confirmation email. If you do not
receive such an email, your submission was not received. If you have problems with
the submission process, send an email to the instructor before the due date. 2

 

/* HashTable.java
CSC 225 - Spring 2017
Template for string hashing
=================
Modify the code below to use quadratic probing to resolve collisions.
Your task is implement the hash, insert, find, remove, and resize methods for
the hash table.
The load factor should always remain in the range [0.25,0.75] and the
tableSize should always be prime.
=================
This template includes some testing code to help verify the implementation.
To interactively provide test inputs, run the program with
java HashTable
Input data should consist of a list of strings to insert into the hash table,
one per line,
followed by the token "###" on a line by itself, followed by a list of
strings to search for,
one per line, followed by the token "###" on a line by itself, followed by a
list of strings to remove,
one per line.
To conveniently test the algorithm with a large input, create
a text file containing the input data and run the program with
java HashTable file.txt
where file.txt is replaced by the name of the text file.
*/
import
import
import
import
import java.util.Scanner;
java.util.Vector;
java.util.Arrays;
java.io.File;
java.lang.Math; public class HashTable{
//The size of the hash table.
int TableSize;
//The current number of elements in the hash table.
int NumElements;
//The variable T represents the array used for the table.
// DECLARE YOUR TABLE DATA STRUCTURE HERE
public HashTable(){
NumElements = 0;
TableSize = 997;
// INITIALZE YOUR TABLE DATA STRUCTURE HERE
}
/* hash(s) = ((3^0)*s[0] + (3^1)*s[1] + (3^2)*s[2] + ... + (3^(k-1))*s[k1]) mod TableSize
(where s is a string, k is the length of s and s[i] is the i^th
character of s)
Return the hash code for the provided string. The returned value is in the range [0,TableSize-1].
NOTE: do NOT use Java's built in pow function to compute powers of 3.
To avoid integer
overflows, write a method that iteratively computes powers and uses
modular arithmetic
at each step.
*/
public int hash(String s){
return 0;
}
/* insert(s)
Insert the value s into the hash table and return the index at
which it was stored.
*/
public int insert(String s){
return 0;
}
/* find(s)
Search for the string s in the hash table. If s is found, return
the index at which it was found. If s is not found, return -1.
*/
public int find(String s){
return 0;
}
/* remove(s)
Remove the value s from the hash table if it is present. If s was
removed,
return the index at which it was removed from. If s was not removed,
return -1.
*/
public int remove(String s){
return 0;
}
/* resize()
Resize the hash table to be a prime within the load factor
requirements.
*/
public void resize(int newSize){
}
/* **************************************************** */
/* main()
Contains code to test the hash table methods.
*/
public static void main(String args){
Scanner s;
boolean interactiveMode = false;
if (args.length > 0){
try{
s = new Scanner(new File(args[0]));
} catch(java.io.FileNotFoundException e){
System.out.printf("Unable to open %s\n",args[0]);
return;
}
System.out.printf("Reading input values from %s.\n",args[0]);
}else{
interactiveMode = true; s = new Scanner(System.in);
}
s.useDelimiter("\n");
if (interactiveMode){
System.out.printf("Enter a list of strings to store in the
hash table, one per line.\n");
System.out.printf("To end the list, enter '###'.\n");
}else{
System.out.printf("Reading table values from %s.\n",args[0]);
}
Vector<String> tableValues = new Vector<String>();
Vector<String> searchValues = new Vector<String>();
Vector<String> removeValues = new Vector<String>();
String nextWord;
while(s.hasNext() && !(nextWord = s.next().trim()).equals("###"))
tableValues.add(nextWord);
System.out.printf("Read %d strings.\n",tableValues.size());
if (interactiveMode){
System.out.printf("Enter a list of strings to search for in
the hash table, one per line.\n");
System.out.printf("To end the list, enter '###'.\n");
}else{
System.out.printf("Reading search values from %s.\n",args[0]);
}
while(s.hasNext() && !(nextWord = s.next().trim()).equals("###"))
searchValues.add(nextWord);
System.out.printf("Read %d strings.\n",searchValues.size());
if (interactiveMode){
System.out.printf("Enter a list of strings to remove from the
hash table, one per line.\n");
System.out.printf("To end the list, enter '###'.\n");
}else{
System.out.printf("Reading remove values from %s.\n",args[0]);
}
while(s.hasNext() && !(nextWord = s.next().trim()).equals("###"))
removeValues.add(nextWord);
System.out.printf("Read %d strings.\n",removeValues.size());
HashTable H = new HashTable();
long startTime, endTime;
double totalTimeSeconds;
startTime = System.currentTimeMillis();
for(int i = 0; i < tableValues.size(); i++){
String tableElement = tableValues.get(i);
long index = H.insert(tableElement);
}
endTime = System.currentTimeMillis();
totalTimeSeconds = (endTime-startTime)/1000.0;
System.out.printf("Inserted %d elements.\n Total Time (seconds):
%.2f\n",tableValues.size(),totalTimeSeconds);
int foundCount = 0;
int notFoundCount = 0;
startTime = System.currentTimeMillis(); for(int i = 0; i < searchValues.size(); i++){
String searchElement = searchValues.get(i);
long index = H.find(searchElement);
if (index == -1)
notFoundCount++;
else
foundCount++;
}
endTime = System.currentTimeMillis();
totalTimeSeconds = (endTime-startTime)/1000.0;
System.out.printf("Searched for %d items (%d found, %d not found).\n
Total Time (seconds): %.2f\n",
searchValues.size(),foundCount,notFoundCount,totalTimeSeconds);
int removedCount = 0;
int notRemovedCount = 0;
startTime = System.currentTimeMillis();
for(int i = 0; i < removeValues.size(); i++){
String removeElement = removeValues.get(i);
long index = H.remove(removeElement);
if (index == -1)
notRemovedCount++;
else
removedCount++;
}
endTime = System.currentTimeMillis();
totalTimeSeconds = (endTime-startTime)/1000.0;
System.out.printf("Tried to remove %d items (%d removed, %d not
removed).\n Total Time (seconds): %.2f\n", } removeValues.size(),removedCount,notRemovedCount,totalTimeSeconds);
}

Attachments:

• 1493263048-225_PROGRAMMING_3.pdf