[SOLVED] Cs2134 homework 9

1. Implement a hash table where collisions are resolved by linear probing. You will implement the methods
find, insert, and rehash for the class below. Your class will rehash when the load factor is greater or
equal to 0.5. The hash function, hf, will be created when you instantiate a member of this class. But
hf will returna positive integer whose range is much larger than the table size. The book says, “you will
need to perform a final mod operation internally after the” hash function.template< class HashedObj >
class HashTable
{
public:
explicit HashTable( int size = 101 ):currentSize(0){ array.resize(size); }
std::hash hf; // create a hash function object
bool find( const HashedObj & x ) const;
void makeEmpty( );
bool insert( const HashedObj & x );
bool remove( const HashedObj & x);
enum EntryType { ACTIVE, EMPTY, DELETED };
private:
struct HashEntry
{
HashedObj element;
EntryType info;
HashEntry( const HashedObj & e = HashedObj(), EntryType i = EMPTY )
: element( e), info(i) {}
};
vector array;
int currentSize;
void rehash( );
};
∗
10% extra credit will be given if you turn this assignment in on Tuesday April 26, 2016 at 11:00 p.m.
12. Create an adjacency list for the graph of the NYC subway station. You will consider a subway station sa
adjacent to subway station sb if there is a subway train that goes from sa directly to sb without going
through any other stops, or you can transfer from sa to sb. You find what subway stations are adjacent
to other subway stations by using the information in the files transfers.txt and MTA train stop data.The file transfers.txt is a bit confusing! Here are some of the entries:
from_stop_id,to_stop_id,transfer_type,min_transfer_time
101,101,2,180
103,103,2,180
104,104,2,180
106,106,2,180
107,107,2,180
108,108,2,180
109,109,2,180
110,110,2,180
111,111,2,180
112,112,2,180
112,A09,2,180
113,113,2,180
…In the file transfers.txt, observe you can transfer from subway station 112 to subway station A09. Thus
A09 is adjacent to (a neighbor of ) 112. You will create an adjacency list as an unordered map<string,
list> instead of a vector<list>. In the next homework assignment, you will use this
adjacency list in the shortest path algorithm.1. Using big-oh notation, what is the worst case running time for your algorithm to create the adjacency
list?2. First add 12, then 50, and finally 44, to this red-black tree (i.e. first insert 12 and perform any operations necessary (using only the algorithm presented in class) so the tree is again a red-black tree, then
insert 50 and perform any necessary operations (using only the algorithm presented in class) so the tree is
again a red-black tree, and then insert 44and perform any operations necessary (using only the algorithm
presented in class) so the tree is again a red-black tree.)Show the following:
• Show the tree after inserting a value. If a violation occurred, state what the violation was (i.e. case
1, 2 or 3).
• If the tree is not a red-black tree, use the algorithm we used in class to turn it into a red-black tree.
Show each step.
22 b
17 b
14 r 18 r
30 b
23. Do not turn in. Please do this on your own. I will expect you to know how to do this for the exam.
You can check your solution at https://www.cs.usfca.edu/~galles/visualization/RedBlack.html.
Show the result of inserting (15, 4, 2, 8, 16, 9, 5, 10) into an initially empty red-black tree as
described in class. Include the color of each node. Show the tree before and after each violation, and state
which violation has occurred (i.e. case 1, case 2, or case 3).4. Write the code needed to perform the method rightRotateRecolor for the RedBlackNode class. The
method has the following prototype:
template
void RedBlackTree::rightRotateRecolor( Node * & k2 )5. When inserting an item into a Red-Black tree, what is the maximum number of pointer changes needed
to adjust the tree? Explain your answer.6. If your hash table size, n, was equal to 20 (or 40, or 2000), why might the following hash function not be
a good idea: h(k) = 4k mod n?7. For the following questions: Let the hash function be H(x) = x mod M, where the table size (M) is initially5.
(a) if the collision strategy was linear probing, what would the hash table look like
• after inserting 4371, 6173
• then removing 6173
• then inserting 3327 and 26
• after resizing1
to a table size of M = 11
• then inserting 4199, 4340, 9679, 1323(b) if the collision strategy was separate chaining, what would the hash table look like
• after inserting 4371, 1323, 6173, 4199, 4344, 9679
• then removing 6173
• then inserting 3324
• then resizing2
to a table size of M = 11
• inserting 21
1where all the items must be inserted into the table by rehashing
2using the algorithm on the slides
3