Implementation in Java

1. We consider the following procedure to implement eager deletion in a hash table that uses linear probing: Deletion is done by replacing a key k with another key l, where 1 is in the same island as k, comes below it in the island, but such that the initial position that 1 is searched for (h(1, 0)) comes at or before k's position in the island. Recall that an island' is a maximum sequence of consecutive keys in the table with no interspersed empty (NIL) slots. An island can wrap around the array, that is, if the island reaches the bottom of the array, it continues at the top. For example, the hash table; 1 d 2 e 3 f 4 5 g 6 7 8 a 9 b 10 has two islands, one of size 1 and one of size 6. The island of size 6 wraps around the array. A key can come after another k in the island, but be stored in the array above it. For example, d comes after b in the island, but is stored before it in the array. The procedure to delete a key k is to start with the key immediately below k in the island, moving downward through the island. If a key 1 is found whose initial hash position, h(1, 0) comes at or before k's position in the island, then l is moved into k's slot. l's slot is filled in the same manner. The first such key found replaces k. If no such key is found (no key below the one being replaced hashes at or before the key to be replaced) and the end of the island is reached (the slot is NIL,) then the key is replaced by NIL. For example, any key 1 in the island after b (c, d, e, and f) which initially hashes to a slot in the island at b or above (slots 8 and 9) could successfully replace b. Again, iflis moved, its empty slot must be filled in the same way. The process continues until a NIL slot is reached, and then the last key is replaced by NIL. Note that for key 1 to replace key k, 1 must come after k in the island. The key 1 also always comes after h(1, 0) in the island (otherwise, I would not be found when searched for.) How long does a single deletion operation take on average? Hint: Compare deletion to insertion. Support your answer. 2. Can this procedure be used for hash tables that use quadratic probing? Can it be used for hash tables that use double-hashing? Justify your answer. 4. Phylogeny trees are binary trees that represent an evolutionary history. Leaves represent currently existing species and internal nodes represent hypothetical ancestors. Each internal node represents an evolutionary event - one species splitting into two species, 3 1 3 5 1 4 4 2 5 2 Figure 1: Phylogeny Trees and so each internal node always has two childs. The tree has n leaves, each leaf representing a species numbered from 1 to n, and so the leaves are numbered uniquely from 1 to n, but not in any particular order. The internal nodes are not numbered, and have no stored data. The problem is to read in a file of phylogeny trees (with duplicates) and count the number of occurrences of each tree. Two trees are the same if they have the same topology and the leaves are numbered in the same order. A hash table will be used to store the trees and their counts. The declaration for a Node of the tree is: struct Node { int species; // only applies to leaves Node *left, *right; }; Write a good hash function for hashing phylogeny trees and say why it is a good choice. 6. An iterator is an object that enables one to traverse a collection of elements, such as a list, an array, or a tree. A method is called to construct an iterator on a particular instance of the collection of Items. The iterator has two main operators: Item next() and boolean hasNext(). The method next() returns the next Item from the collection to be processed, if there is one, and the method hasNext() return true if and only if there is another Item to be processed. It would be an error to call next() if hasNext() is false. For example, an iterator for an array could be implemented by simply remembering the index of the next Item in a variable p. p is initialized to the position of the first element of the array. next() would return the element at p and advance p. hasNext() returns true if p is not past the end of the array. Efficiently implement an iterator for a binary tree that iterates over the elements in an in-order traversal, that is, write methods to construct a iterator object given the root of a tree, the hasNext() method which returns true if and only if there are more nodes to traverse, and the next() method which returns the next Item in the in-order traversal of the tree. One way to implement an iterator would be to traverse the tree, storing the elements, in order, into an array, and then returning an iterator for the array. But that means if an element is added to the tree which follows the current key of the iterator in the in-order traversal of the tree, the iterator is no longer valid. Find a better way to implement the iterator which is not affected by the addition of a key that is inserted after the current key of the iterator in the tree traversal. 1. We consider the following procedure to implement eager deletion in a hash table that uses linear probing: Deletion is done by replacing a key k with another key l, where 1 is in the same island as k, comes below it in the island, but such that the initial position that 1 is searched for (h(1, 0)) comes at or before k's position in the island. Recall that an island' is a maximum sequence of consecutive keys in the table with no interspersed empty (NIL) slots. An island can wrap around the array, that is, if the island reaches the bottom of the array, it continues at the top. For example, the hash table; 1 d 2 e 3 f 4 5 g 6 7 8 a 9 b 10 has two islands, one of size 1 and one of size 6. The island of size 6 wraps around the array. A key can come after another k in the island, but be stored in the array above it. For example, d comes after b in the island, but is stored before it in the array. The procedure to delete a key k is to start with the key immediately below k in the island, moving downward through the island. If a key 1 is found whose initial hash position, h(1, 0) comes at or before k's position in the island, then l is moved into k's slot. l's slot is filled in the same manner. The first such key found replaces k. If no such key is found (no key below the one being replaced hashes at or before the key to be replaced) and the end of the island is reached (the slot is NIL,) then the key is replaced by NIL. For example, any key 1 in the island after b (c, d, e, and f) which initially hashes to a slot in the island at b or above (slots 8 and 9) could successfully replace b. Again, iflis moved, its empty slot must be filled in the same way. The process continues until a NIL slot is reached, and then the last key is replaced by NIL. Note that for key 1 to replace key k, 1 must come after k in the island. The key 1 also always comes after h(1, 0) in the island (otherwise, I would not be found when searched for.) How long does a single deletion operation take on average? Hint: Compare deletion to insertion. Support your answer. 2. Can this procedure be used for hash tables that use quadratic probing? Can it be used for hash tables that use double-hashing? Justify your answer. 4. Phylogeny trees are binary trees that represent an evolutionary history. Leaves represent currently existing species and internal nodes represent hypothetical ancestors. Each internal node represents an evolutionary event - one species splitting into two species, 3 1 3 5 1 4 4 2 5 2 Figure 1: Phylogeny Trees and so each internal node always has two childs. The tree has n leaves, each leaf representing a species numbered from 1 to n, and so the leaves are numbered uniquely from 1 to n, but not in any particular order. The internal nodes are not numbered, and have no stored data. The problem is to read in a file of phylogeny trees (with duplicates) and count the number of occurrences of each tree. Two trees are the same if they have the same topology and the leaves are numbered in the same order. A hash table will be used to store the trees and their counts. The declaration for a Node of the tree is: struct Node { int species; // only applies to leaves Node *left, *right; }; Write a good hash function for hashing phylogeny trees and say why it is a good choice. 6. An iterator is an object that enables one to traverse a collection of elements, such as a list, an array, or a tree. A method is called to construct an iterator on a particular instance of the collection of Items. The iterator has two main operators: Item next() and boolean hasNext(). The method next() returns the next Item from the collection to be processed, if there is one, and the method hasNext() return true if and only if there is another Item to be processed. It would be an error to call next() if hasNext() is false. For example, an iterator for an array could be implemented by simply remembering the index of the next Item in a variable p. p is initialized to the position of the first element of the array. next() would return the element at p and advance p. hasNext() returns true if p is not past the end of the array. Efficiently implement an iterator for a binary tree that iterates over the elements in an in-order traversal, that is, write methods to construct a iterator object given the root of a tree, the hasNext() method which returns true if and only if there are more nodes to traverse, and the next() method which returns the next Item in the in-order traversal of the tree. One way to implement an iterator would be to traverse the tree, storing the elements, in order, into an array, and then returning an iterator for the array. But that means if an element is added to the tree which follows the current key of the iterator in the in-order traversal of the tree, the iterator is no longer valid. Find a better way to implement the iterator which is not affected by the addition of a key that is inserted after the current key of the iterator in the tree traversal