CMPSCI 311: Theory of Algorithms

David Mix Barrington

Fall, 2003

Midterm Exam #2

Given in class Monday 10 November 2003

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.

• Question 1 (10): (true/false with 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.)

• Question 2 (10): (true/false with justification) Multiplying two BigInteger variables of length n requires time Ω(n²).

• Question 3 (10): (true/false with justification) A 2-3 tree with n leaves must have height Θ(log n).

• Question 4 (20): Suppose we are given n points in the plane, no three of them on the same line. Explain how we may put the points in an order p₁,..., p_n such that no two of the line segments p₁p₂, p₂p₃,...,p_n-1p_n cross. Give a big-O bound on the running time of your algorithm. (Hint: Use decrease-and-conquer and the Quickhull algorithm.)

• Question 5 (30): Recall the 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.

  • (a,10) Indicate how to solve this problem by reducing it to the reachability problem on a certain directed graph.

  • (b,20) Give Java code or pseudocode to solve this problem, by the reduction in (a) or otherwise. Give a big-O bound on the running time of your algorithm, assuming that apply takes O(1) time.

• Question 5 (20): Let n be a multiple of 3 and let A of be an array of n 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.)

  • (a,10) Indicate how to solve this problem in worst-case time O(n log n).

  • (b,10) Indicate how to solve this problem in average-case time O(n).

  Last modified 10 November 2003