Description
Problem 1: Hash Tables (5+8 = 13 points)
- Given the sequence < 3,10,2,4 >, apply the double-hashing strategy for open addressing to store the sequence in the given order in a hash table of size m = 5 with hash functions h1(k) = k mod 5 and h2(k) = (7.k) mod 8. Document all collisions and how they are resolved (provide computations).
- Implement a hash table that supports insertion and querying with open addressing using linear probing. The implementation should be consistent with the following class specification:
| class Node{ public:
int key; int value; Node(int key, int value); } class HashTable{ private: Node **arr; int maxSize; int currentSize; public: HashTable(); hashCode(int key); void insertNode(int key, int value); int get(int key); bool isEmpty(); } |
5
10
15
Problem 2: Greedy Algorithms (2 + 6 = 8 points)
- Show that a greedy algorithm for the activity-selection problem that makes the greedy choice of selecting the activity with shortest duration may fail at producing a globally optimal solution.
- Assuming an unsorted sequence of activities, derive a greedy algorithm for the activity-selection problem that selects the activity with the final starting time. Your solution should not simply sort the activities and then select the activity.
