Questions in black, answers in blue.
Directions: Each of the first two questions is a statement that may be true or false. Please state whether it is true or false -- you will get five points for a correct boolean answer and there is no penalty for a wrong guess. Then justify your answer -- the remaining points will depend on the quality and validity of your justification.
Given a directed graph G a vertex v, and a number k, in time O(n+e) we can construct a list of all vertices x such that there is a path of length at most k from v to x. (Here n is the number of nodes in G and e is the number of edges -- G is given as an adjacency list.)
TRUE. Breadth-first search from v gives the shortest path (or at least one of the shortest paths) from v to each x. We do the BFS in O(n+e) time, then in O(n) time we loop through each of the x's checking their BFS depth and adding x to the output list if this depth is at most k. (Alternatively, we could stop the BFS at depth k and simply output all the vertices reached to that point.)
Multiplying two BigInteger variables of length n requires time
Ω(n2).
FALSE. By the recursive method presented in Discussion #5
and Levitin 4.5, which divides each number in half and does only three
recursive multiplications, we can multiply two BigInteger objects
in time O(nlog2 3) = o(n2).
TRUE. A 2-3 tree of height h has between 2h and 3h leaves, inclusive. Since n is between 2h and 3h, by taking base-2 logs we find that log n is between h and (log 3)h. Since this shows that log n is in Θ(h), we conclude that h is in Θ(log n).
Using Quickhull, find two adjacent points on the convex
hull and make them p1 and p2. Then remove p1
from the set and recurse to find a path from p2 to pn
through the nodes p3,..., pn-1. The edge
p1p2 is outside the convex hull of the other points and
so does not cross any other edges in the path. By the inductive hypothesis, no
two of the other path edges cross. The base of the recursion is n=1, where we
can set p1 and there are no edges at all (so no edge crossings).
The time is given by a recurrence with T(n) = T(n-1) + TQ(n) +
O(1), where TQ(n) is the time for Quickhull on n points. This
solves easily to give T(n) = Θ(TQ * n), which is Θ(n2
log n) average case and Θ(n3) worst case.
Another idea is to use Quickhull to get the entire convex hull, then
somehow connect all but one edge of this hull to the path obtained by
recursing on the points not in the convex hull. The timing analysis is much
the same as above, since there might be only O(1) points in the hull. The
difficulty here is to figure out how to connect the hull-path to the
non-hull-path without crossing any edges. One way to do this is as follows:
Let p1 be one point on the hull, and let p2 through
pk be the other points on the hull in order. Then find the hull of
the other n-k points. The nearest of these hull points to pk may be
connected to pk without crossing any other edges, so we let that
point be pk+1 and continue. Since finding this nearest neighbor
might take all of O(n) time, we change the recurrence to T(n) = T(n-k) +
TQ + O(n), but this turns out to have the same solutions as above.
Permutation class from
Discussion 6. An object of this class stored a function from the set {1,...,n}
to itself. Assume we have a method public int apply(int x) that
returns the value of this function on input x. (The other implementation
details of Permutation should not be relevant here.) We want to
create a new method public boolean reachable (int x, int y) in
this class. This method should return true if there is an integer k ≥ 0 such
that applying the function k times takes the element x to the element y.
Make a graph with vertices {1,...,n} and an edge from x
to apply(x) for each vertex x. Then reachable(i,j) is true iff
there is a path from i to j in this graph.
apply takes O(1) time.
The time of this is clearly O(n). The algorithm is correct because if j
is reachable at all it is reachable in at most n-1 steps. (Any sequence of n
or more steps must repeat a vertex, and cannot be the shortest sequence.)
public boolean reachable (int i, int j)
{// returns whether applying "this" to i ever eventually gives j
int current = i;
for (int count = 0; count < n; count++) {
if (current == j) return true;
current = apply(current);}
return false;}
int values, all distinct. The middle-third problem is
to create an array B of length n/3 such that the values in B consist of the
elements in A of rank n/3+1, n/3+2,..., and 2n/3, in any order. (The element
of rank i is the one that is larger than exactly i-1 of the other elements.)
Mergesort A, then fill B with the elements A[n/3] through A[2n/3 - 1]. This is O(n log n) + O(n) = O(n log n).
Use Quickselect twice to find the element x of rank n/3
and the element y of rank 2n/3. Then: The time taken is O(n) plus the time to make two Quickselects on an array
of size n. Quickselect is O(n) in the average case, so in the average case
we solve the middle-third problem in time O(n). int i=0;
for (int j=0; j < n; j++)
if ((A[j] > x) && (A[j] <= y)) {
B[i] = A[j];
i++;}
Last modified 10 November 2003