This program is a Big-\"O\" notation, linked lists, hash tables, trees, collecti
ID: 3837947 • Letter: T
Question
This program is a Big-"O" notation, linked lists, hash tables, trees, collections, sets, lists example problem. This is a pretty beginner class so we haven’t discussed any major topics. We are using abstract methods and exception handling to deal with this problem/ arrays and other basic java topics binary object files.I will include an example as reference to how much we have used. Essentially this is an excersie on Big-"O" notation, linked lists, hash tables, trees, collections, sets, lists
Project 1: The “minus” operation on sets
In the lecture on linked lists and sets, we saw code which performed the intersection of two sets A and B (written as A B) and the union of two sets (written as A U B). Both of these operations return a new set (i.e., they do not change the original sets A or B).
Another common relationship between two sets is A minus B (written as A – B). In this operation, a new set is created which contains each element in set A unless that same element is also in set B.
As you can see from the picture, two interesting relationships exist:
(A – B) U (A B) = A
(A – B) U (A B) U (B – A) = A U B
In this project, enhance the Set class on Blackboard in two ways:
1.Create a new method named minus with the following heading:
public Set<T> minus(Set<T> otherSet)
It should perform the minus operation described above, where the new set returned from the method contains all of the elements in calling object minus any element also in otherSet.
2.Create an equals method which returns true if all of the elements in the calling object are in the set passed as a parameter, and vice versa. The method should have a heading of:
public boolean equals(Set<T> otherSet)
In a different class containing main, test your new minus and equals methods with the following four test casess:
Case 1: calling object = {“C”, “E”, “G”, “A”} and otherSet = {“E”, “C”, “F”}
Case 2: calling object = {“Carlos”, “John”, “Alice”} and
otherSet = {“John”, “Henry”, “Maria”}
Case 3: calling object = {5, 1, 3} and otheSer = {1, 3, 5, 7, 9}
Case 4: calling object = {5} and otherSet = {}
In each case, print the contents of 5 sets: A, B, (A – B), (A B), and
(A – B) U (A B). Notice that the last set should have the same elements as set A. Use the equals method to prove this point.
Along with a printout of your program containing main and your enhanced version of the Set class, submit PrintScreen(s) for each test case showing the results of the 5 required sets and the test for equality of the last set with the first set listed.
EXAMPLE OF CODE NOT PART OF THE QUESTION FOR CONTEXT
Explanation / Answer
public class HashTable {
private LinkedList[] hashArray = null ;
private int hashTableSize = 0 ;
public HashTable(int size) {
hashTableSize = size ;
if (hashTableSize <= 0) {
System.out.println("Error - size must be non-negative: " + size) ;
System.exit(0) ;
}
hashArray = new LinkedList[hashTableSize] ;
for (int i=0 ; i < hashTableSize ; i++)
hashArray[i] = new LinkedList() ;
HashTableTester.debug("Hash table created with size: " + hashTableSize) ;
}
private int computeHash(String stringToHash){
int hash = 0 ;
for (int i = 0 ; i < stringToHash.length() ; i++) {
hash += stringToHash.charAt(i) ;
}
hash = hash % hashTableSize ;
HashTableTester.debug("Hash for String "" + stringToHash + "": " + hash) ;
return hash ;
}
public boolean contains(String target) {
int hash = computeHash(target) ;
LinkedList list = hashArray[hash] ;
return list.contains(target) ;
}
public void add(String stringToStore) {
int hash = computeHash(stringToStore) ; // Get hash value
if (hashArray[hash].contains(stringToStore)) {
HashTableTester.debug("String "" + stringToStore +
"" is already in the list -- not added") ;
} else {
HashTableTester.debug("String "" + stringToStore +
"" added to list " + hash) ;
hashArray[hash].addToStart(stringToStore) ;
}
}
public boolean remove(String stringToRemove) {
int hash = computeHash(stringToRemove) ;
LinkedList.Iterator iterator = hashArray[hash].iterator() ;
while (iterator.hasNext()) {
if (iterator.peek().equals(stringToRemove)) {
iterator.delete() ; // deleted
HashTableTester.debug("String "" + stringToRemove +
"" deleted from list " + hash) ;
return true ;
} else {
iterator.next() ;
}
}
HashTableTester.debug("String "" + stringToRemove +
"" could not be deleted from list " + hash) ;
return false ;
}
public String toString() {
String stringOfLists = "" ;
for (int i = 0 ; i < hashTableSize ; i++) {
stringOfLists += " table " + i + ": " + hashArray[i] + " " ;
}
return stringOfLists ;
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.