HOMEWORK9
ALGORITHMS AND DATA STRUCTURES (CH08-320201)
Problem 1: Hash Tables (5+8 = 13 points)
(a) 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).
(b) 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)
(a) 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.
(b) 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.
