Problem 1
A binary tree has n nodes. What is the maximum height of the tree? What is the minimum height? Explain your answers.
Problem 2
A tree (not necessarily a binary tree) has n nodes. What are the minimum and maximum possible heights of the tree? Explain your answer.
Problem 3 (4.6 from text)
For each of the operations and each of the implementations in Exercises 4.4 and 4.5, give the order of magnitude for the running time of the operations
on sets of size n.
Problem 4 (4.7 from text)
Suppose we are hashing integers with a 7-bucket hash table using the hash function h(i) = i mod 7.
a. Show the resulting open hash table if the perfect cubes 1, 8, 27, 64, 125, 216, 343 are inserted.
b. Repeat part (a) using a closed hash table with linear resolution of collisions.
Problem 5
Following are several hash functions. None of them are very good as hash functions. Explain why they are not good hash functions.
Hash keys are character strings. The hash function h1(x) computes the length of the string.
The function h2(x) computes a random number r with 1 ≤ r ≤ B, where B is the number of buckets. It returns r.
Problem 6
Design an efficient data structure for representing a subset S of the integers from 1 to n. The operations we wish to perform are these:
Select an integer i from the set and delete it.
Add an integer i to the set
Problem 7
Write a procedure (in pseudocode!) to increase the number of buckets in a (closed) hash table. Analyze its time and space complexity.
