Final exam

May 9, 2002



Your name: ________________________________________



  Your id: ________________________________________



                      Your score: __________  / 200

There is a version of this page with solutions.

Open textbook (but no other books), open notes. No use of computers. There are 12 problems, each worth 20 points. Do only ten problems, cross out two. The first ten that are not crossed out count.

If in doing a programming problem you need some supporting functions that are as simple as, for example, the maximum of two integers, just assume you have such functions.

When asked to “put a check mark next to all correct answers; cross out all incorrect ones,” do something like:

Who is your TA?

```
Ryan ......  2:00pm- 3:15pm
```
```
Seth ......  3:30pm- 4:45pm
```
```
Sean ......  5:00pm- 6:15pm
```
```
David .....  9:30am-10:45am
```
```
Patrick ... 11:00am-12:15pm
```
```
Jayson .... 12:30pm- 1:45pm
```

Insertion into binary search trees can be made “at the root,” meaning that after the insertion creates a new leaf, that leaf node gets rotated up into the root position.
Starting with this tree:

show the tree that results when you insert 3 “at the root”:

Now insert 8 into the tree you drew, again “at the root,” and show the result:
This problem is about search trees when insertions are done at a leaf (i.e., without subsequent rotations).
Consider the tree below. Assume it was built by a series of insertions into an initially empty tree, with no deletions.

Circle the right answer:
1. Yes / No / Impossible to tell: The last key inserted was H.
2. Yes / No / Impossible to tell: The first key inserted was F.
3. Yes / No / Impossible to tell: The first key inserted was A.
4. Yes / No / Impossible to tell: K was inserted before D.
5. Yes / No / Impossible to tell: K was inserted before H.
Same question as above, same tree, but now assume it was built as a randomized binary search tree:
Circle the right answer:
1. Yes / No / Impossible to tell: The last key inserted was H.
2. Yes / No / Impossible to tell: The first key inserted was F.
3. Yes / No / Impossible to tell: The first key inserted was A.
4. Yes / No / Impossible to tell: K was inserted before D.
5. Yes / No / Impossible to tell: K was inserted before H.
In randomized binary search trees, the decision to make the new entry the root of a subtree is based on the size of the subtree: The chance of insertion at the root is 1 / (1 + the current size of the subtree).
Which of the following alternative ways of making that decision will also result in trees with fast (=logarithmic) lookups?
1. Fast | Slow: Flip a coin (i.e., use a 50% chance).
2. Fast | Slow: Never insert at the root of the subtree.
3. Fast | Slow: Always insert at the root of the subtree.
4. Fast | Slow: Roll a dice, make the new entry the root if the dice shows a six (i.e., use a 1/6 chance).
This array is organized as a heap (a priority queue):
```
  10  8  6  2  1  4  5
```
1. Show the array after insertion of a new element: 7.
2. Show the array after insertion of another new element: 3.
3. This question was removed.
4. Now delete 10 and show the resulting array.
5. This question was removed.
Assume we want to do look-ups by phone number to find a person's name that goes with a given phone number. Assume we are using open hashing with an array of size 1024; we are using the last three digits of the phone number as our hash function; and that we are handling collisions by moving down the array one step at a time.
As you know there is a need to distinguish between two kinds of locations that are currently empty: those that have never been occupied and those that have previously been occupied. Let's call them "NEVER USED" and "DELETED."
True or false ...
1. True / false: For doing insertions the difference between NEVER USED and DELETED does not matter.
2. True / false: For doing lookups the difference between NEVER USED and DELETED does not matter.
3. True / false: The number of locations marked as DELETED is always equal to the number of items that have been deleted from the table.
4. True / false: If a location that is marked as DELETED is immediately followed by one that is marked as NEVER USED then the label of that DELETED location can be changed to NEVER USED without making any future operations incorrect.
5. True / false: If a location that is marked as DELETED is immediately preceded by one that is marked as NEVER USED then the label of that DELETED location can be changed to NEVER USED without making any future operations incorrect.

This is about skiplists.

Which of the following ways to chose the height of a new node will result in linear-time lookups (as opposed to fast logarithmic lookups)?

Linear? Yes | No.
```
    height = 1 + rand () % 2;
```
Linear? Yes | No.
```
    height = 1 + rand () % 10;
```

Linear? Yes | No.

    height = 2;
    while (rand () % 2 == 0)
        height += 1;

Linear? Yes | No.

    height = 2;
    while (rand () % 2 == 0)
        height += 2;

Linear? Yes | No.

    height = 2;
    while (rand () % 2 == 0)
        height += 2;
    if (height > 5)
        height = 5;

Linear? Yes | No.

 
    height = 2;
    while (rand () % 2 == 0)
        height += 2;
    if (height > 5)
        height = 1;

Consider expressions like the ones in Assignment 4 but built only from x, 1, +, and *. Examples are
```
    ( x + 1 ) * x * ( 1 + x )
    1 + 1 + x * x
```
Complete the function below so that it returns the degree of the expression (the highest power of x if you were to multiply everything out; for the examples above the degrees are 3 and 2).
```
int Expression::degree ()
{
    if (constant ())
        return 0;




















}
```
Write a function that finds out if a tree passes the following test for being balanced: the longest and the shortest path from the root to a leaf differ in length by no more than 2. Write whatever supporting functions you need.
```
bool balanced (Node* t)

{
```
This is about trees where each node has three pointers to children (some of which may of course be NULL): left, middle, and right.
Write a function that finds out if in fact such a tree has a node with three non-NULL children.
```
    bool three (Node* t)

    {
```
Which of the following sorting algorithms need a second array in addition to the array in which the data is initially given. Check off the ones that do; cross out the ones that don't.
1. QuickSort
2. HeapSort
3. SelectionSort
4. MergeSort
5. CountingSort
Assume we are dealing with binary search trees that contain integers and that are nicely balanced, meaning that their depth is logarithmic (as a function of their size). Which of the following algorithms can be carried out in O (log n) time? Check off the ones that can; cross out the ones that can't.
1. Computing the number of leaves of the tree.
2. Finding the largest integer in the tree.
3. Finding the second largest integer in the tree.
4. Finding the tenth largest integer in the tree.
5. Finding the median integer in the tree. (The median is the entry with the property that half of the other entries are bigger and half are smaller; assume n is odd.)
6. Finding out how many entries in the tree are bigger than
7. Finding out if two given numbers are both present in the tree.
8. Finding out, for two given numbers j and k, whether or not all the numbers j through k are in the tree.

9:07 PM, Friday, December 13, 2002