CH231A-Homework 10 Hash Tables and Greedy Algorithms Solved

Problem 10.1 Hash Tables                                                                                
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) = 7k mod 8. Document all collisions and how they are resolved. Write down your computations.

(b)     Implement a hash table that supports insertion and querying with open addressing using linear probing. Select an h0 function and explain why your selected h0 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);



Problem 10.2 Greedy Algorithms                                                                          
(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 latest starting time. Your solution should not simply sort the activities and then select the activity.