Answer To: LinkedList.java LinkedList.java public class LinkedList { protected ListNode head, tail;...
Rushendra answered on Jun 09 2021
coding-task-with-helpful-files-included-w0ttqcat/(1) Description.pdf
1
(Hashing and BST)
1: Preface
This project has two parts. In part 1, you will solve the dictionary problem using the three
methods – BST, Hashing with Chaining, and Hashing with Probing. In part 2, you will use BST to
solve some additional problems. The next two sections outline what files you need to modify and
what functions you need to use. The project also contains additional files (which you do not need
to modify).
Use TestCorrectness.java to test your code. For each part, you will get an output that you
can match with the output I have given to verify whether or not your code is correct. Output is
provided separately in the ExpectedOutput file. Should you want, you can use
www.diffchecker.com to tally the output.
You can use TestTime.java for the bulk test in each part. It showcases how the choice of a
good data structure/algorithm vastly improves your performance.
2: Part 1: Dictionary Problem
We will solve the Dictionary problem using Hashing and Binary Search Tree, and compare their
performance. Specifically, given a set of integers, we want to support the following operations:
● Search a number. Returns true if the number is in the collection, else returns
false.
● Insert a number. Returns true on successful insertion, else returns false.
● Delete a number. Returns true on successful deletion, else returns false.
We have seen three techniques to solve this problem:
● Hashing with Chaining: You are going to implement the search, insert, and remove
functions in HashingWithChaining.java.
● Hashing with Probing: You are going to implement the resize, search, insert, and
remove functions in HashingWithProbing.java.
● Binary Search Tree: You are going to implement the insert, remove, removeLeaf,
and removeNodeWithOneChild methods in BST.java.
2
2.1: Hashing With Chaining
We search/insert/delete in a hashtable in the following way. First use the getHashValue method
to get the hash value. Now use this hash value to get hold of a hash table entry, which is a linked
list. Finally, use appropriate linked list functions as described below.
getHashValue
Uses the hash function ( )%TABLE_SIZE. For search, insert, and delete37 • ??? + 61
you must use this method; DO NOT change this method.
Search
● First obtain the hash value for the key using getHashValue(key).
● Get the linked list from the hashTable[ ] for this hash value. Recall that hashTable[ ]
is just an array of linked lists. So, if the hash value is h, the desired linked list (which
can contain key) is given by hashTable[h].
● Now, use a loop to search this linked list, and return true if the linked list contains
the key, else return false. This search process will be very similar to the getNodeAt
method that you have seen for linked lists – while looping over the list check if the
placeholder’s value equals key to determine if key is present in the list.
Insert
● Remember that your hash table should contain a number only once. Otherwise, it
occupies too much space, and it may also lead to unexpected results. So, before
inserting, make sure that the number already does not exist on the linked list.
Therefore, first use search to check if the hash table already contains val. If it does,
then simply return false to indicate that insertion was not needed.
● Obtain the hash value for val using getHashValue function.
● Get the linked list from the hashTable[ ] for this hash value.
● Now, use insertAtEnd function of the linked list to insert the value.
● Finally, return true to indicate a successful insertion.
3
Delete
● First obtain the hash value for val using getHashValue function.
● Get the linked list from the hashTable[ ] for this hash value.
● Now, we have to remove the occurrence (if any) of val in the linked list. If the
list is empty, then return false (indicating val is not in the table).
● If the value in the head of the list equals val, then call deleteHead and return true.
● Otherwise, we have to delete a value somewhere inside the list. Note that
you have used deleteAfter method previously to this end. Here, you will do
the same. Just traverse through the list and if you find that the next node’s
value equals val, then call a deleteAfter on the current node. The deleteAfter
method in the LinkedList class is empty; use your code from PA2 to fill this
part and then use it.
Use a curr variable to traverse the linked list. Initially, curr = the head of the
list.
● As long as curr’s next is not null, do the following:
○ If the value of curr’s next equals val, then deleteAfter(curr) and
return true
○ Else move curr to the next node.
● Once the loop terminates, return false (indicating val is not in the table).
4
2.2: Hashing With Probing
The hashing with probing uses the exact same hash function as the chaining method, with one
key difference. Whereas in the chaining method, TABLE_SIZE is fixed to 7 for our experiments,
for probing, we have to allow the table to grow when the table is full (or shrink when the table has
too many tombstones). This is achieved by the resize method which works as follows:
Resize
● First create an array keys[ ] of length size; here, the class variable size reflects the
actual number of values that are present in the hash table.
● Now go through hashTable[ ] (whose length is given by TABLE_SIZE) and collect
the values that are ≥ 0 into the keys[ ] table. Thus, if hashTable[ ] contains [9, 15,
−1, 0, −9, 3], then size = 3 and keys[ ] will be populated as [9, 15, 0, 3].
● Now, set TABLE_SIZE = newTableSize, and allocate TABLE_SIZE many cells for
hashTable[ ]. Then, use a loop to fill up hashTable[ ] with EMPTY. Refer to the
constructor for something similar.
●
● Set oldSize = size, size = 0, and garbage = 0. Here, garbage reflects the number of
Tombstones in the table, which is set to 0 because resizing will ignore tombstones.
● Finally run a loop and insert every value in the keys[ ] array back into the
hashTable[]; use the insert method to this end. Note that size will be restored to the
initial value by the insert method.
Next comes in the search method, which returns the index where key is found. If key is not
found, then the method returns −1.
Search
● Obtain the hashValue for the key using the getHashValue method.
● Run a loop TABLE_SIZE many times. Within the loop, do the following:
○ If hashTable[hashValue] equals key, then we have found key at index
hashValue; so, return hashValue
○ If hashTable[hashValue] equals EMPTY , then we have reached an empty
slot; so, return −1
○ Increment hashValue; this means we are essentially probing to the next slot.
○ If hashValue equals TABLE_SIZE, we have reached the end of the array in
the probe sequence; so, reset hashValue = 0.
● If the loop terminates, we have traversed the entire table and never found key; so,
return −1
5
Now, comes in the insert method, which essentially works in the same way as search, but
kind of in the opposite way. In a probe sequence, if we find the value, then we return −1, else we
write the value in the first empty slot that we find. Also, we have to worry about the scenario
when the table is full. More specifically,
Insert
● If the table is full (i.e., size+garbage equals TABLE_SIZE), then we resize the hash
table by calling the resize method with .2 • ???? ?? ????????
● Obtain the hashValue for the key using the getHashValue method.
● Run a loop TABLE_SIZE many times. Within the loop, do the following:
○ If hashTable[hashValue] equals val, then we have found val at index
hashValue; so, return −1 (insertion is not needed)
○ If hashTable[hashValue] equals EMPTY , then we have reached an empty
slot; so, break away from the loop (no further probe is needed)
○ Increment hashValue; this means we are essentially probing to the next slot.
○ If hashValue equals TABLE_SIZE, we have reached the end of the array in
the probe sequence; so, reset hashValue = 0.
● set hashTable[hashValue] = val and increment size
● return hashValue, the index at which the insertion was carried out
Finally, we tackle deletion in the remove method, which utilizes the search method.
Remove
● Obtain index by calling the search method with val as argument. If index is less
than 0, then val is not present in the table; so, there is nothing to delete and we
return −1.
● Set hashTable[index] = TOMBSTONE, increment garbage, and decrement
size
● return index, the index at which the deletion was carried out
6
2.3: Binary Search Tree
Let’s understand the class structure. BSTNode.java contains the BSTNode class that represents
a node in a binary search tree. The class has 4 variables – left & right (which respectively
represent the left & right children of a node), value (stores the value of the node), and parent
(which represents the parent of a node). BST.java contains the BST class that represents the
tree; it has two variables – root (which represents the root of the tree) and a size (which captures
the number of nodes in the tree). Note the types – value and size are integers, whereas the other
is a BSTNode reference (in Java) because it points to a BSTNode.
The search and insert methods work as their names suggest. The remove method first
searches for the node containing val, the value to be deleted. If val does not exist, there is
nothing to delete. Otherwise, if the node has both children (Case 3), then a reduction to Case 1
or 2 is carried out; to this end, use the findMax method that accepts a node as argument and
finds the node with the maximum value in the subtree of the node. Now, either the removeLeaf
method or the removeNodeWithOneChild method is called.
● A node is the root if it equals root or its parent is null
● A node is a leaf if its left child and right child are both null. A node has a left child if its left
child is not null. A node has a right child if its right child is not null.
● A node is a left child if its parent’s value is larger or equal, else it is a right child.
The code for the search function has been provided to you so that you can use it as a guide
to fill up the other functions. In any case, the pseudo-code is given below so that you can identify
how the code is aligned to the pseudo-code.
Search
● Assign a temporary variable tmp to the root
● while tmp is not null, repeat the following:
○ if value of tmp equals key then return tmp
○ else if value of tmp < key, move tmp to tmp’s right child
○ else move tmp to tmp’s left child
● return null
7
Insert
● If size is 0, then allocate memory for the root (via a constructor call to the BSTNode
class), increment size, and return the root.
● Set a temporary variable tmp to the root and a temporary variable parent to null
● while tmp is not null, repeat the following:
○ if value of tmp equals val then return null (indicating no node was created)
○ else if value of tmp < val, set parent to tmp and move tmp to tmp’s right
child
○ else set parent to tmp and move tmp to tmp’s left child
● Create a new BSTNode, named newNode with value val. Assign newNode’s parent
field to the local variable parent.
● If parent’s value is larger than val, then newNode is the left child of parent, else
newNode is the right child of parent.
● Increment size and return newNode.
remove
● Find the node to be deleted, say nodeToBeDeleted, by calling search with val
● if nodeToBeDeleted is null, there’s nothing to be deleted; so, return false
● if nodeToBeDeleted has a left child and a right child, then do the following:
○ find the node having the maximum value in nodeT oBeDeleted’s left
subtree – set nodeT oBeDeleted’s value to the maximum node’s value
○ set nodeT oBeDeleted to the maximum node
● if nodeToBeDeleted is a leaf, call removeLeaf with nodeToBeDeleted as argument,
else call removeNodeWithOneChild with nodeToBeDeleted as argument
● decrement size and return true;
removeLeaf
8
removeLeaf
● if leaf is the same as root, then
○ set root to null
● else, do the following:
○ Assign a temporary variable parent to leaf’s parent
○ if leaf is a left child, then set parent’s left to null, else set parent’s right to null
○ set leaf’s parent to null
removeNodeWithOneChild
● declare a temporary variable child (of type BSTNode)
● if node has a left child,
○ set child to node’s left and set node’s left to null
● else, do the following:
○ set child to node’s right and set node’s right to null
● if node is the same as root, then
○ set root to child and set child’s parent to null
● else, do the following:
○ if node is a left child, then set node’s parent’s left to child, else set node’s
parent’s right to child
○ set child’s parent to node’s parent and set node’s parent to null
9
2.4: Comparative Analysis: Hashing With Chaining vs BST
Fig. 1 shows the search time performances for the three methods, under various table sizes. We
see that as hash table size increases, the number of collisions go down (as one would expect),
and Hashing behaves increasingly well. However, at small table sizes, the performance of BST is
significantly better. Fig. 2 shows that if you have a large hash table (close to the size of the
universe), then even a simple hashing with linked list will outperform BST almost always. Hence,
if you have enough space for a large hash table, use a simple hashing with linked list
implementation.
In “real-world” applications, one has to worry about the data, as data is not truly random. So
simple hash functions are often not good and neither are unbalanced binary search trees. One
has to either choose better hashing schemes or implement balanced binary search trees.
I have omitted the results for Hashing with Probing as they are similar to that for chaining.
Figure 1: Search time performances for various table sizes when 1 million values are randomly
inserted and then another 1 million values are randomly searched.
___________________________________________________________________________
Figure 2: Comparison of search performances using hashing with linked lists and BST 7
10
3: Part 2: Other BST Applications
Using the pseudo-codes given for each, your task is to complete the getPredecessor,
getSuccessor, and nearestNeighbour in BST.java
The following BST has been used for testing the correctness of your code.
Figure 3: Binary Search Tree Used for Correctness Test
3.1: Predecessor and Successor
Given a set of numbers N , predecessor(x) is the highest number y in N such that y ≤ x, and successor(x) is the
smallest number z in N such that z ≥ x. Thus, if for the set {6, 9, 10, 13, 22, 31, 34, 88}, the predecessor of 31 is
31 itself, whereas the predecessor of 30 is 22, and the predecessor of 5 is not defined. Likewise, the successor
of 31 is 31 itself, whereas the successor of 15 is 22, and the successor of 89 is not defined.
Implement the getPredecessor method. Here is how you find predecessor using BST:
● Assign a temporary variable tmp to the root of BST
● Assign an integer variable pred to −∞ (use Integer.MIN_VALUE in Java)
● while tmp is not null, repeat the following:
○ if value of tmp equals key then tmp is the predecessor; so, return key
○ else if value of tmp < key, then tmp is a candidate for being the predecessor; so, do
the following:
■ store tmp’s value as a predecessor candidate by setting pred to tmp’s value
■ now you want to get a better predecessor (i.e., something which is larger
than tmp but still smaller than key); so, set tmp to the right node of tmp
○ else set tmp to the left node of tmp
● Finally return pred
Use similar ideas to implement the getSuccessor method for finding the successor. You will use a
successor variable succ, which is initially (use Integer.MAX_VALUE in Java). The variable succ will be∞
modified when key is smaller than tmp’s value. I’ll leave the rest of the details to you.
11
3.2: Nearest Neighbor Search
Nearest neighbour search (NNS) is one the most important problems in Computer Science. It
can be defined simply as follows: given a set P of points and a query point q, find the point in P
that is closest to q (breaking ties arbitrarily). It’s importance is not only limited to algorithms and
data structures, but can be traced into numerous other areas such as (but not limited to):
Machine Learning, Security, Artificial Intelligence, Data Mining and Analytics, Databases, DNA
sequencing, and etc.
Observe that the nearest neighbour is either the predecessor or the successor. Thus,
the nearest neighbour of 30 is 31 and that of 24 is 22. So, our approach is to find both, and
simply pick the one which is closer to the number (breaking ties arbitrarily).
Implement the nearestNeighbour method for find the closest value to key as follows:
● Find the predecessor and the successor of key
● If predecessor is −∞, then return successor as the nearest neighbor
● Else If successor is ∞, then return predecessor as the nearest neighbor
● Else return predecessor or successor whichever is closer to key
3.3 Comparative Analysis
Note that we can also find nearest neighbour by scanning through the entire list of numbers and finding the
closest one. This, however, is going to have O(N) complexity as opposed to the O(H) complexity using
BST. Although H is N in the worst case, Figure 4 clearly depicts the difference
○ BST is much faster!
Figure 4: Nearest Neighbour Search Comparison
Caution: For the BST methods, you must achieve a complexity of O(H), where H is the height of the tree.
For hashing, your code must achieve complexity proportional to the length of the linked list being scanned
for the particular value concerned. Otherwise, (say when your code ends up scanning the entire tree/hash
table), you’ll get partial credits (even if your code is correct).
You should test your methods thoroughly, and it is a good idea to use other test-cases (other
sequence of numbers than the one I have given).
coding-task-with-helpful-files-included-w0ttqcat/(2) ExpectedOutput.pdf
****************** Test Hashing With Chaining ******************
Inserting the following numbers: [11, 12, 15, 17, 12, 19, 4, 5, 11, 19, 20, 32, 77, 65, 66, 88, 99, 10, 8, 19,
15, 66, 11, 19, 0, 3, 2, 55, 67, 78, 39]
*** Hash Table Structure (after insertion) ***
Slot 0: [15 -> 99 -> 8 -> 78]
Slot 1: [12 -> 19 -> 5]
Slot 2: [65 -> 2]
Slot 3: [20 -> 55]
Slot 4: [17 -> 66 -> 10 -> 3]
Slot 5: [77 -> 0]
Slot 6: [11 -> 4 -> 32 -> 88 -> 67 -> 39]
Size of hash table: 23
*** Searching Hash Table ***
Found: [3 -> 19 -> 12 -> 4 -> 5 -> 19 -> 20 -> 32 -> 99 -> 8 -> 12]
Did not find: [29 -> 27 -> 34 -> 45 -> 37 -> 25 -> 25 -> 24 -> 16]
*** Deleting Hash Table ***
Deleted: [11 -> 12 -> 15 -> 5 -> 17 -> 19 -> 4 -> 20 -> 32 -> 39 -> 99 -> 10 -> 8 -> 0 -> 55]
Did not find: [16 -> 5 -> 17 -> 19 -> 19 -> 15 -> 21]
*** Hash Table Structure (after deletion) ***
Slot 0: [78]
Slot 1: []
Slot 2: [65 -> 2]
Slot 3: []
Slot 4: [66 -> 3]
Slot 5: [77]
Slot 6: [88 -> 67]
Size of hash table: 8
****************** Test Hashing With Probing ******************
Inserting the following numbers: [11, 12, 15, 17, 12, 19, 4, 5, 11, 19, 20, 32, 77, 65, 66, 88, 99, 10, 8, 19,
15, 66, 11, 19, 0, 3, 2, 55, 67, 78, 39]
*** Hash Table Structure (after insertion) ***
[39, 20, 65, 78, -1, 8, -1, 66, 15, 2, -1, -1, 99, 3, 67, 10, 55, 4, 17, -1, 11, 88, 5, -1, -1, 12, -1, -1, 19, 32, 77,
0]
Size of hash table: 23
*** Searching Hash Table ***
Found: [3 -> 19 -> 12 -> 4 -> 5 -> 19 -> 20 -> 32 -> 99 -> 8 -> 12]
Did not find: [29 -> 27 -> 34 -> 45 -> 37 -> 25 -> 25 -> 24 -> 16]
*** Deleting Hash Table ***
Deleted: [11 -> 12 -> 15 -> 5 -> 17 -> 19 -> 4 -> 20 -> 32 -> 39 -> 99 -> 10 -> 8 -> 0 -> 55]
Did not find: [16 -> 5 -> 17 -> 19 -> 19 -> 15 -> 21]
*** Hash Table Structure (after deletion) ***
[-9, -9, 65, 78, -1, -9, -1, 66, -9, 2, -1, -1, -9, 3, 67, -9, -9, -9, -9, -1, -9, 88, -9, -1, -1, -9, -1, -1, -9, -9, 77, -9]
Size of hash table: 8
****************** Test BST ******************
Inserting the following numbers: [11, 12, 15, 17, 12, 19, 4, 5, 11, 19, 20, 32, 77, 65, 66, 88, 99, 10, 8, 19,
15, 66, 11, 19, 0, 3, 2, 55, 67, 78, 39]
*** BST Structure (after insertion) ***
<11, null> <4, 11> <0, 4> <3, 0> <2, 3> <5, 4> <10, 5> <8, 10> <12, 11> <15, 12> <17, 15> <19, 17> <20,
19> <32, 20> <77, 32> <65, 77> <55, 65> <39, 55> <66, 65> <67, 66> <88, 77> <78, 88> <99, 88>
Size of BST: 23
*** Searching BST ***
Found: [3 -> 19 -> 12 -> 4 -> 5 -> 19 -> 20 -> 32 -> 99 -> 8 -> 12]
Did not find: [29 -> 27 -> 34 -> 45 -> 37 -> 25 -> 25 -> 24 -> 16]
*** Deleting BST ***
Deleted: [11 -> 12 -> 15 -> 5 -> 17 -> 19 -> 4 -> 20 -> 32 -> 39 -> 99 -> 10 -> 8 -> 0 -> 55]
Did not find: [16 -> 5 -> 17 -> 19 -> 19 -> 15 -> 21]
*** BST Structure (after deletion) ***
<3, null> <2, 3> <77, 3> <65, 77> <66, 65> <67, 66> <88, 77> <78, 88>
Size of BST: 8
****************** Clean up ******************
Size of chaining: 0
Size of probing: 0
Size of BST: 0
****************** Test BST Applications ******************
Numbers in BST: [25, 17, 10, 23, 36, 34, 48, 40, 54]
key = 10: predecessor = 10; successor = 10; nearest neighbor = 10
key = 54: predecessor = 54; successor = 54; nearest neighbor = 54
key = 34: predecessor = 34; successor = 34; nearest neighbor = 34
key = 9: predecessor = -infty; successor = 10; nearest neighbor = 10
key = 57: predecessor = 54; successor = infty; nearest neighbor = 54
key = 44: predecessor = 40; successor = 48; nearest neighbor = 48
key = 47: predecessor = 40; successor = 48; nearest neighbor = 48
key = 43: predecessor = 40; successor = 48; nearest neighbor = 40
coding-task-with-helpful-files-included-w0ttqcat/.classpath
coding-task-with-helpful-files-included-w0ttqcat/.project
coding-task-with-helpful-files-included-w0ttqcat
org.eclipse.jdt.core.javabuilder
...