Introduction to Algorithms, 2020-1
Week 10: Exercises

1. Random Queue

We'd like to implement a data structure RandomQueue with the following interface:

• q.add(x) – add an element to the queue

• q.remove() - removes a random element from the queue

• q.isEmpty() - test if a RandomQueue is empty.

All operations should be fast, i.e. not run in linear time. How can we implement this structure?

2. Hash Chain Lengths

Write a program that reads an integer N and simulates inserting (100 · N) values into a hash table with N buckets using separate chaining, assuming that hash values will be distributed randomly. The program should print the lengths of the longest and shortest chains.

3. Empty Buckets

Suppose that we insert N values into a hash table with N buckets. What fraction of the buckets do we expect will be empty? Assume that N is a large number.

4. Heap Insertion

1. A binary heap is initially empty. We call its add() operation N times to add N distinct integers to the heap. How long will this take in the worst case? In the best case?

2. A binary heap is initially full, and may contain duplicate elements. We call its removeSmallest() operation N times to remove all values from the heap. How long will this take in the worst case? In the best case?