CS 61B: Data Structures (Spring 2002)
Midterm II

### Solutions

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 kth node visited immediately upon visiting it, without completing the traversal. (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++) {
}
}
}
}
```
b. Theta(v2) time.

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 c1, N1 such that

f(n) >= c1 j(n)
for all n >= N1.

Similarly, because g(n) is in Theta(j(n)), g(n) is in O(j(n)), so there exist positive constants c2, N2 such that

g(n) <= c2 j(n)
for all n >= N2.

Putting the two facts together, we find that

alpha f(n) - beta g(n) >= (alpha c1 - beta c2) j(n)
for all n >= max{N1, N2}.

If you choose alpha and beta so that

alpha c1 - beta c2 > 0,
it follows by the definition of big-Omega that alpha f(n) - beta g(n) is in Omega(j(n)). For example, you could choose alpha = 2/c1 and beta = 1/c2.
Mail inquiries to cs61b@cory.eecs