===========================================
DS221: INTRODUCTION TO SCALABLE SYSTEMS
===========================================
ASSIGNMENT 2
POINTS: 150
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-----------------------
PART B
POSTED: 25 SEP, 2018
DUE DATE: 14 OCT, 2018, 11:59PM
-----------------------
-----------------------
SEARCHING [75 points]
-----------------------
1) You need to implement a Dictionary abstract data type that supports insert and fast lookup operations. You may assume that the keys being inserted are unique. You will implement this using a Hashtable, where a hash function maps the given key to an array index. Each item in the array is an unbounded bucket containing pairs. You should use the "list" data structure available as part of C++ STL for the bucket implementation. The signature for the Dictionary interface and Hash Table class you will implement are given below. [25 points]
class IDictionary {
virtual void insert(int key, char* value);
virtual char* lookup(int key);
}
class HashTableImpl : public IDictionary {
HashTableImpl(int capacity); // Constructor. Capacity is the table size for the hash range.
}
2) Perform insert and lookup operations on the HashTable for different input sizes (10^4, 10^5, 10^6, ...), key distributions, and capacities. What is the most number of items you can insert? Compare the empirical performance with the analytical time complexity. Discuss your results. [25 points]
3) Give two other implementations of the dictionary ADT: using an unsorted array (ArrayDictImpl) and a sorted array (BSearchDictImpl), with signatures as given below. For the unsorted array, you may insert an item in the last unused location and do a linear scan for the key lookup. For the sorted array, you should call a sort function after all inserts are done, and for the lookup by key, you should perform a binary search. You should use the qsort Quick Sort function that is part of the C++ STP for the sorting. Compare the performance of the three Dictionary implementations, using both experiments and complexity analysis. [25 points]
class ArrayDictImpl : public IDictionary {
ArrayDictImpl(int capacity);
}
class BSearchDictImpl : public IDictionary {
BSearchDictImpl(int capacity); // Constructor. Capacity is the array size.
sort(); // this sorts the items in the array by their key
}