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.