Algorithm Design and Analysis
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.
Program 12.12 Rotations in BST's
These twin routines perform the rotation operation on a BST. A right rotation makes the old root the right subtree of the new root (the old left subtree of the root); a left rotation makes the old root the left subtree of the new root (the old right subtree of the root). For implementations where a count field is maintained in the nodes (for example, to support select, as we will see in Section 14.9), we need also to exchange the count fields in the nodes involved in the rotation.
void rotR(link& h)
{ link x = h->1; h->1 = x->r; x->r = h; h = x; }
void rotL(link& h)
{ link x = h->r; h->r = x->1; x->1 = h; h = x; }
Program 12.13 Root insertion in BSTs
With the rotation functions in Program i z. z 2, a recursive function that inserts a new node at the root of a BST is immediate: Insert the new item at the root in the appropriate subtree, then perform the appropriate rotation to bring it to the root of the main tree.
private:
void insertT(link& h, Item x)
{ if (h == 0) { h = new node(x); return;
if (x.key() < h->item.key())
{ insertT(h->l, x); rotR(h); }
else { insertT(h->r, x); rotL(h); }
}
public:
void insert(Item item)
{ insertT(head, item); }