Description

•  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 h₁(k) = k mod 5 and h₂(k) = 7k mod 8. Document all collisions and how they are resolved. Write down your computations.
•  Implement a hash table that supports insertion and querying with open addressing using linear probing. Select an h⁰ function and explain why your selected h⁰ is wellsuited for your test data. The implementation should be consistent with the following or equivalent class specifications:

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();

}

Problem 10.2 Greedy Algorithms

•  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.
• Bonus  Assuming an unsorted sequence of activities, derive a greedy algorithm for the activity-selection problem that selects the activity with the latest starting time. Your solution should not simply sort the activities and then select the activity.