Description

• Submit one ZIP file per homework sheet which contains one PDF file (including pictures,computations, formulas, explanations, etc.) and your source code file(s) with one makefile and without adding executable, object or temporary files.
• The implementations of algorithms has to be done using C, C++, Python or Java.
Problem 11.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 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);
Algorithms and Data Structures Course: CH-231-A
} 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 11.2 Greedy Algorithms (7 points)
(b) (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