Midterm Solutions
 March 14, 2001 Computer Science 226

1. (25 points) Match each of the given sorting algorithms with one or more of the given characteristics. Write as many letters as apply in the blank to the left of the name of the sorting method.
```
CDE     insertion sort         A. linear extra space

DG      selection sort         B. optimal average running time

BF      heapsort               C. linear best-case running time

D       bubblesort             D. quadratic worst-case running time

ABF     mergesort              E. linear for nearly-ordered files

BD      quicksort              F. optimal worst-case running time

shellsort              G. quadratic best-case running time

```

2. (7 points) What is the largest key that could be at the bottom level of a heap built from the keys 1 through 64?

58. Heap has depth 7. All nodes on path from bottom node to root must be greater than bottom node, but path could be 64-63-62-61-60-59-58.

3. (7 points) Draw the binomial queue that results when you insert the keys

```          A  F  E  D  C  B  G  H  I
```
in that order into an initially empty queue. Use left-heap-ordered power-of-2 trees.

```
H    I
/
F
/   \
E     C
/ \   / \
D   A B   G

```

4. (7 points) Draw the red-black tree that results when you perform top-down insertion of the keys

```          A  F  E  D  C  B  G  H  I
```
in that order into an initially empty tree.
```
E
// \\
C     G
/ \   / \
A   D F   H
\\        \\
B         I

```
5. (7 points) Draw the binary search tree that results when you insert the keys
```          A  F  E  D  C  B  G  H  I
```
in that order into an initially empty tree, using the root insertion method.

```
I
/
H
/
G
/
B
/ \
A   C
\
D
\
E
\
F

```
6. (7 points) Draw the splay tree that results when you insert the keys
```          A  G  F  E  D  C  B  H  I  J
```
in that order into an initially empty tree.
```
J
/
I
/
H
/
C
/ \
B   E
/   / \
A   D   G
/
F

```
7. (7 points) Draw the binary trie that results when you insert the keys
```    1101  0100  0011  0010  0001  1000  1001
```
in that order into an initially empty trie.
```
...........
/           \
.            .
/ \          / \
.   0100     .  1101
/ \          / \
0001   .        .
/ \      / \
0010 0011 1000 1001

```
8. (7 points) Draw the Patricia trie that results when you insert the keys
```    1101  0100  0011  0010  0001  1000  1001
```
in that order into an initially empty trie.
```           _______
1101(0)       \
/           \     \
/             \     \
0100(1)      -> 1000(1)  |
/  / \      /   /     \__/
/   \_/     /   /
0011(2)_ _ _   /  1001(3)
/  \        \  |   / / \
/    \        | |__/  \_/
0001(3)  0010(3) |
/  / \   / \  \  |
/   \_/   \ /   \_|
.

```
9. (5 points) Why not use a hash function like h2(v) = v % 97 for the second hash function in double hashing?

If the first hash function hashes to a filled slot and h2(v) = 0, then you get stuck in an infinite loop.

10. (10 points)
a. (3 points) Circle the sequences from the following list that produce the same BST as

```          C  E  A  G  B  D  F

C
/   \
A     E
\    / \
B  D   G
/
F

```
when inserted in the order given into an initially empty tree.
```          C  A  B  E  G  D  F
C  A  E  G  D  B  F
C  E  B  G  A  D  F     No. B comes before A.
C  E  G  A  F  D  B
C  E  G  D  F  A  B
E  A  G  B  D  F  C     No. E comes before C.
```
b. (7 points) How many of 7! = 5040 orders in which to insert the keys produce the same tree as
```          C  E  A  G  B  D  F
```
when inserted into an initially empty tree?

The first node is C. We first consider the number of ways to build the two subtrees EDGF and AB independently. There are 3 ways to construct the subtree EDGF and 1 way to construct the subtree AB. Instead, let's consider what happens if we fix the ordering of the two subtrees, e.g, AB and EGDF. Then, we can build the whole BST by interleaving these two orderings in any way, e.g., ABEGDF, AEGDFB, EABGDF, etc. If you've taken a probability course, you might remember that the formula for the number of ways is 6! / (2! * 4!) = 15. (Alternatively, you could enumerate them all.) Since there is only 1 legal ordering of the subtree AB and 3 legal orderings of the subtree EDGF, the total number is 15 * 3 * 1 = 45.

11. (10 points)
Match each of given search-tree structures with the function that best describes the absolute value of the difference between the depths of two leaves in the tree. Write the letter corresponding to your answer in the blank to the left of the name.

```
C   splay tree                  A. O(1)

B   red-black tree              B. O(log N)

C   BST                         C. O(N)

```