Exercises A#

Note

You must complete these exercises by Wednesday of W6.

Exercise 3.1.1#

Which of the two implementations, SequentialSearchST or BinarySearchST, would you use for an application that performs \(10^3\) put() and \(10^6\) get() operations in random order? Justify your choice.

Exercise 3.1.3#

Exercise 3.1.24 of the book.

Assume the keys are doubles or integers. Write a version of binary search that assumes a uniform distribution of keys and will thus first look at the beginning of a dictionary for a word that begins with a letter close to the beginning of the alphabet.

More precisely, if the searched key is \(k_x\), the smallest key is \(k_{lo}\), and the largest key is \(k_{hi}\), interpolation search will first probe at the key at index fraction \(\lfloor (k_x-k_{lo})/(k_{hi}-k_{lo}) \cdot (\text{length}-1) \rfloor\) of the array instead of probing the middle (50th percentile) first.

Implement InterpolationSearchST and compare this on FrequencyCounter.

Exercise 3.1.4#

Exercise 3.1.25 of the book.

It is very common to first test the presence of a key before adding or modifying the corresponding entry. That practice generates several consecutive searches for the same key.

The idea of caching is to store the last accessed key internally and to use it opportunistically if it is still valid. Modify BinarySearchST to incorporate this idea.

Exercise 3.1.5#

Exercise 3.2.31 of the book.

Write an isBST() method that takes a Node as an argument and returns true if the argument is the root of a valid BST, and false otherwise (i.e., verify that all properties of a BST are satisfied).

Do you think that testing (locally) for each node the property « the left child has a smaller key and the right child has a greater key » is sufficient? If not, give a counterexample.

What is the time complexity of your algorithm?

Exercise 3.1.6#

Exercise 3.2.4 of the book.

Suppose a certain search tree has keys between 1 and 10 and we are looking for key 5. Which sequence(s) cannot match the sequence of the examined keys?

10,9,8,7,6,5
4,10,8,6,5
1,10,2,9,3,8,4,7,6,5
2,7,3,8,4,5
1,2,10,4,8,5

Exercise 3.1.7#

Exercise 3.3.33 of the book.

Write a method is23() in RedBlackBST that checks that no node is connected to two red links and that there is no red link to the right. Also write a method isBalanced() that checks that any path from the root to a null link has the same number of black links. Finally, combine isBST(), is23(), and isBalanced() to implement isRedBlackBST().

Exercise 3.1.8#

How can you enumerate all stored keys in ascending order in a binary search tree? What is the time complexity of this operation? Justify your answer.

Exercise 3.1.9#

Starting from an initially empty binary search tree, what does the tree look like after inserting the keys 12, 5, 10, 3, 13, 14, 15, 17, 18, 15? For the same data, what would the tree look like for a 2-3 tree?

Does this example illustrate the advantages or disadvantages of these different data structures? Why?