**NAME:**
**MAKEUP Final Exam** |
**September 10, 1998**
**Computer Science 226
** |

This test is 17 questions, weighted as indicated. Do all of your work on
these pages (use the back for scratch space), giving the answer in the
space provided. Put your name on every page (*now*), and write out
and sign the Honor Code pledge before turning in the test.

*``I pledge my honor that I have not violated the Honor Code during
this examination.''*

**1.** (45 points)
Fill in the following table. Express running times as a function of the
number of items, N, to within a constant factor for large N. Assume that
the items in the symbol table are 64-byte records with 64-bit keys.
insert time delete time
worst best average worst best average
BST
Key-Indexed Search
Red-Black Tree
Splay Tree
Separate Chaining
Linear Probing
Binary Trie

**2.** (5 points)
Draw the union-find forests for the edges BC AB AD CE DF EG FH GI HJ IK JL KM,
using path compression without weight balancing.

#### NAME:

**3.** (5 points)
Draw the red-black tree that results when the keys
X R A N D O M K E Y S

are inserted in that order into an initially empty tree.

**4.** (5 points)
Draw the splay tree that results when the keys
X R A N D O M K E Y S

are inserted in that order into an initially empty tree.

#### NAME:

**5.** (5 points)
Give the KMP FSA for the string `1101111`.

**6.** (5 points)
Draw a NDFSA for the string `a((b + c)* + d)*e`.

#### NAME:

**7.** (5 points)
Show the Patricia trie that results when you insert keys
defined by all suffixes of the string
10010010

(in decreasing order of their length, or moving left to right)
into an initially empty trie. Ignore those suffixes that are
prefixes of other suffixes.

**8.** (5 points)
Show the existence TST that results when you insert keys
defined by suffixes of the string
randomstring

(in decreasing order of their length, or moving left to right)
into an initially empty tree.

#### NAME:

**9.** (5 points)
Show the B-tree that results when you insert the octal keys
020 000 001 002 003 004 005 006 007 010 011 012 013 014 015 016 017

in that order into an initially empty tree, with M = 4.
Use the style of Figures 16.5 through 16.7 in the book.

**10.** (5 points)
Show the extendible hash table that results when you insert the octal keys
020 000 001 002 003 004 005 006 007 010 011 012 013 014 015 016 017

in that order into an initially empty table, with M = 4.
Use the style of Figures 16.11 through 16.13 in the book.

#### NAME:

**11.** (5 points)
Consider the graph on seven nodes, labelled A through G, with 11 directed
edges
AB EB AE AC CD GD DC EF FG BC FC.

Give the maximum and minimum possible
values for the maximum depth of the recursion when this graph is searched
with depth-first search, starting at A.

**12.** (10 points)
Consider the graph on eight nodes, labelled A through H, with 16 edges
AB(3) EB(1) AE(4) AC(1) CD(5) GD(9) DC(2) EF(6) FG(2) BC(5) FA(3) AH(7)

where the numbers in parentheses are edge weights. Give a minimal
spanning tree and a shortest path tree from `A` for the graph.

#### NAME:

**13.** (5 points)
Draw the 3D tree that is constructed when
the points
(0, 3, 2) (1, 4, 5) (0, 1, 1) (3, 0, 2) (4, 3, 1) (4, 0, 2)

are inserted in that order into an initially empty tree.

**14.** (5 points)
Suppose that we have a graph like Figure 1.2 in the book (points on
a grid, with connections among adjacent points present with a fixed
probability), but with the additional proviso that
edges to diagonally adjacent points also allowed. Which minimal spanning tree
method would be preferred (PFS, Prim, or Kruskal) for a huge graph
of this type? Explain your answer.

#### NAME:

**15.** (5 points)
Give an optimal BST for the following keys, with the access frequencies
given in parentheses.
A(3) B(1) C(4) D(1) E(5) F(2) G(6) H(2) I(4)

What is the average cost of a search hit in your tree?

**16.** (5 points)
Suppose that you have a huge array with N 64-bit words, and only a tiny
amount of extra memory available.
Describe an algorithm for determining which 64-bit
value occurs most often. Estimate the running time of
your algorithm, as a function of N and M, the frequency of occurrence of the
most popular value.

#### NAME:

**17.** (5 points)
Consider the following function takes two arguments, an integer `x`
and a function `f` that takes an integer as an argument and
returns an integer. Assume that `f` is like a mathematical
function (whenever we call it twice with the same argument value,
we get the same return value)
that is defined for all integers.
void loop(int (*f)(int), int x)
{
a = x, b = f(x);
while (a != b)
{ a = f(a); b = f(f(b)); }
}

Of the following statements, which best describes the behavior of
this function?

** A.** Always gets in an infinite loop

** B.** Always returns

** C.** Whether or not it returns depends on f, not x

** D.** Whether or not it returns depends on x, not f

** E.** Whether or not it returns depends on both x and f