Computer Science : 24 hours

CIS 330: Algorithm Design and Analysis 2

Directions: Please complete each of the following exercises. Please read the instructions carefully.

For all “short programming assignments,” include source code files in your submission.

1. The following refer to symbol table implementations.

a. What is the benefit of using a key-indexed array implementation?

b. Give a circumstance under which a key-indexed array implementation is inappropriate.

2. Short programming assignment. Implement the array-based symbol table from program 12.5, adding a remove operation.

3. In the following sorted file we are searching for J. Show the values that would be checked at each step for both a binary search and an interpolation search. Show all calculations.

A A B E F H J M N N N N O P P P P P R R R R T T T Z Z Z Z Z Z Z

4. The following refer to binary search trees.

a. Draw the binary search tree that results when the keys I N S E R T M D (in that order) are inserted into an initially empty tree.

b. Explain why searching and insertion may still require N operations in the worst case for binary search trees.

5. The following refer to indexed implementations of symbols tables.

a. What is the advantage of an indexed implementation when table items are large?

b. When is an indexed implementation inappropriate?

6. Using the algorithm represented in Programs 12.13 and 12.12, show the BST that results from inserting D into the following:

7. The following refer to methods of providing guaranteed performance for search trees.

a. Explain how the algorithm in Program 13.1 results in a balanced tree.

b. Explain the difference between randomized, amortized, and optimized approaches to gauranteed performance.

c. Why does a randomized BST require that each node store the count of nodes in the subtree?

8. The following refer to splay BSTs.

a. What is the difference between a splay BST and an ordinary BST?

b. Draw the splay BST that results when you insert the items I N S E R T M D into an initially empty tree.

9. Convert the following 2-3-4 tree into a red-black tree:

10. The following refer to skip lists.

a. Explain the trade-offs resulting from increasing and decreasing the parameter t.

b. Draw the skip list that results from inserting the keys I N S E R T M into an initially empty list, assuming that randX returns the sequence 1 1 2 1 3 2 3.