CS2134 Homework 10 Solved

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 return a 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<HashedObj hf; // create a hash function object bool contains( 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<HashEntry array; int currentSize; void rehash( );

};

2. 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[2] to other subway stations by using the information in the files transfers.txt and MTA train stop data.txt. 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.

In the file MTA train stop data.txt you can observe that subway stop 112 is one stop away from subway stop 111, and that subway stop 112 is one stop away from subway stop 113. Thus subway stops A09,111, and 113 are the stops adjacent to (neighbors of) subway stop 112.

You will create an adjacency list as an unordered map<string, list<string instead of a vector<list<string In the next homework assignment, you will use this adjacency list in the shortest path algorithm.

Written Part

1.   Using big-oh notation, what is the worst case running time for your algorithm to create the adjacency list?

2.   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?

3.   For the following questions: Let the hash function be H(x) = x mod M, where the table size (M) is initially

5.

(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 resizing[3] 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 resizing[4] to a table size of M = 11

•   inserting 21