Problem 10.1 Hash Tables (11 points)
(a) (4 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) = 7k mod 8. Document all collisions and how they are resolved. Write down your computations.
(b) (7 points) Implement a hash table that supports insertion and querying with open address-ing using linear probing. Select an h0 function and explain why your selected h0 is well-suited 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 (7 points)
(a) (2 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 glob-ally optimal solution.
(b) Bonus (5 points) 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.
How to submit your solutions
You can submit your solutions via Grader at https://grader.eecs.jacobs-university.de as a generated PDF file and/or source code files.
If there are problems with Grader (but only then), you can submit the file by sending mail to k.lipskoch@jacobs-university.de with a subject line that starts with CH-231-A.
Please note, that after the deadline it will not be possible to submit solutions. It is useless to send solutions by mail, because they will not be graded.
