Midterm II

**Problem 1.** (6 points) **Quickies.**

**a.** Theta(1) best-case time.

**b.** Theta(*n*) worst-case time.

**c.** Nodes J and P are pruned.

**d.**

**Problem 2.** (7 points) **Binary Search Trees.**

**a.** 3, 4, 5, and 6.

**b.** Advantages of a binary search tree over a hash table (any one
will suffice):

- Finding the smallest key greater than or equal to
*x*is often faster. - So is finding the smallest key, period.
- So is finding the largest key.
- So is finding the largest key less than or equal to
*x*. - Binary search trees don't need to be resized.
- A binary search tree allows you to print its contents in sorted order in linear time. A hash table doesn't really. (You can sort the contents of a hash table with a linear-time sort, but that's obviously a lot more trouble.)

**c.** Do an inorder traversal of the tree. Return the *k*th node
visited. (Note: we won't give full marks for a correct algorithm
that isn't as asymptotically fast as this one.)

**d.** Theta(k + h) time. (Your answer may differ if you gave a slower
algorithm for 2c. In that case, you may lose points on 2c for
slowness but get full points here if you analyze
your algorithm correctly.)

**e.** Do a standard BST findElement() operation, but use
`position` fields in place of keys.
(P.S. note that the `position` fields satisfy the
binary search tree invariant.)

**Problem 3.** (7 points) **Converting Directed Graphs to Undirected
Graphs**.

**a.**

public static void directedToUndirected(boolean[][] adjMatrix) { for (i = 0; i < adjMatrix.length; i++) { for (j = 0; j < adjMatrix.length; j++) { if (adjMatrix[i][j]) { adjMatrix[j][i] = true; } } } }

**c.** There are many possibilities. Here's the simplest one.

**Problem 4.** (5 points) **Asymptotic Analysis**.

Because *f*(*n*) is in Theta(*j*(*n*)),
*f*(*n*) is in Omega(*j*(*n*)), so
there exist positive constants *c*_{1}, *N*_{1}
such that

for allf(n) >=c_{1}j(n)

Similarly, because *g*(*n*) is in Theta(*j*(*n*)),
*g*(*n*) is in O(*j*(*n*)), so
there exist positive constants *c*_{2}, *N*_{2}
such that

for allg(n) <=c_{2}j(n)

Putting the two facts together, we find that

alphafor allf(n) - betag(n) >= (alphac_{1}- betac_{2})j(n)

If you choose alpha and beta so that

alphait follows by the definition of big-Omega that alphac_{1}- betac_{2}> 0,

Mail inquiries to cs61b@cory.eecs