Midterm II

If you want to relive taking the midterm, here it is in PostScript or PDF.

**Problem 1.** (8 points) **A Miscellany.**

**a.** 20 microseconds.

**b.** Because for all *n* > 101,
1 / (*n* - 100) ≤ *n*.
(Here, *c* = 1.)

**c.**

3 6 / | \ 1 2 5 7 9 / | \ / \ / | \ a b c d e f g h

**d.** Θ(log *n* log log *n*).
That's read (log *n*) (log log *n*).

**Problem 2.** (8 points) **Binary Trees.**

**a.**

6 / \ / \ 4 8 / \ / \ 2 5 7 9 / \ 1 3

**b.** Yes. In the following example, the preorder traversal changes
from `5 3 9 7` to `7 3 9`.

5 7 / \ / \ 3 9 ==delete(5)==> 3 9 / 7

**c.**

7 2 5 9 3 4 1 8 7 2 5 8 3 4 1 9 7 2 1 8 3 4 5 9 1 2 7 8 3 4 5 9 1 2 4 8 3 7 5 9

**d.**

I would choose to be binary,

Balanced, big, and written in C.

**Problem 3.** (9 points) **Directed Graphs.**

**a.**

public void contract(int x, int y) { adj[x].union(adj[y]); adj[y] = new Set(); for (int i = 0; i < size; i++) { if (adj[i].remove(y)) { adj[i].insert(x); } } }

For problems b-d, the union operation always takes O(*s*) time,
so the running time is dominated by the cost of performing one query and
update on each of *s* data structures that together contain a total of
*e* items.

**b.** Θ(*s* + *e*).

**c.** Θ(*s*).

**d.** There are (at least) three answers we will accept for this question.
The most likely reasonable answer we expect is Θ(*s* log *e*).
But the *truly* smallest correct bound that can be given
is Θ(max {*s*, *s* log (*e* / *s*)}).
We'll also accept Θ(*s* + *s* log (*e* / *s*)),
but it's technically wrong because it can become negative when
*e* < *s*.

Mail inquiries to cs61b@cory.eecs