[Solved] CH08-320201-Homework 9 Hash Tables and Greedy Algorithms

Problem 1: Hash Tables

• 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) = (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

• 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.