Description
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;
5 Node(int key, int value);
}
class HashTable{
private:
Node **arr;
10 int maxSize;
int currentSize;
public:
HashTable();
hashCode(int key);
15 void insertNode(int key, int value);
int get(int key);
bool isEmpty();
}
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.
Remarks
• Solutions have to be handed in via Moodle by the due date. For late submissions you need to get in
contact with the TAs directly. You need to upload one zip-file that contains a PDF-file for the theoretical
parts and source files (no executables or object files) for the programming assignments. The source
files need to include a makefile. Programming assignments need to be handed in as C++ or Python
code. Please write your own code. It is ok to take snippets from online resources, but they need to
be clearly marked.
• Exercises marked with a * are bonus problems. These count towards your number of points for this
homework. The maximum number of official points can not be exceeded.
2