1. Add a new indexing mechanism to Programming Project #2
where instead of binary search trees you should use separate chaining with hash function
f(x) = x mod TableSize
for keeping the indexes.
Implement only the insert operation. For both the StudentNumber (S) index
and the Age (A) index, experiment with the following hash tables sizes (where size
is the number of bins) and compute the max, min, and average
number of elements in each bin (these will really be the list lengths) after all
data has been inserted:
- 20 bins
- 50 bins
- 100 bins
DO NOT TURN IN YOUR PROGRAM. Turn in your results in the form of a table as follows:
| Bins
| S_Max
| S_Min
| S_Avg
| A_Max
| A_Min
| A_Avg
|
20
|
|
|
|
|
|
|
50
|
|
|
|
|
|
|
100
|
|
|
|
|
|
|
2. (Using a second hash function) Exercise 5.1d from the book (C or C++ version)
3. (Extendible hashing) Exercise 5.14 from the book (5.19 in C++ version).
Start with one empty block of size 4. Draw a diagram each time a block splits.
4. (Binary heaps) Exercises 6.2 and 6.3 from the book (C or C++ version).
5. Write a paper-and-pencil routine to perform percolate_down(i)
as
called by the buildHeap procedure for a min-heap.
It should start at the i-th element of the array where the heap is stored, and move
its value down the tree, swapping with one of its children as necessary, until that value
finally takes its proper place.
Running your routine on a computer is optional, but your paper-and-pencil
solution should include the definitions of relevant data structures you are using.
Good luck!