Algorithms B-Exam
January, 1996

  1. Give an asymptotically tight solution (big Theta) for each of the following recurrences. You may assume that T(1) = 1. You need not prove your solution correct.

    (a)

    T(n) = T(n/7) + T(2n/3) + n.

    (b)

    T(n) = 3T(n/2) + nlgn.

    (c)

    T(n) = 3T(n/2) + n2.

  2. Consider a set S of n >= 2 distinct numbers given in unsorted order. Each of the following four problem parts ask you to give an algorithm to determine two distinct numbers x and y in the set that satisfy a stated condition. In as few words as possible, describe your algorithm and justify its running time. To keep your algorithms brief, use algorithms described in lectures and the book as subroutines.

    1. In O(n) time, determine x, y (elements of) S such that

      |x - y| >= |w - z|

      for all w, z (elements of) S.

    2. In O(nlgn) time, determine x, y (elements of) S such that x <> y and

      |x - y| <= |w - z|

      for all w, z (elements of) S such that w <> z.

    3. In O(n) time, determine x, y (elements of) S sucth that

      |x - y| <= (1/(n-1))(max(S) - min(S))

      i.e., determine any two numbers that are at least as close together as the average distance between consecutive numbers in the sorted order.

  3. Recall that the most efficient implementation of MAKESET, FINDSET, and UNION involved maintaining a forest of trees. If the trees in this forest are created using the union by size heuristic, then prove using induction that for all tree roots x,

    size(x) >= 2height[x]

    where size(x) and height[x] denote the number of nodes and height, respectively, of the tree rooted at x.

  4. An Euler circuit for an undirected graph is a path which starts and ends at the same vertex and uses each edge exactly once. A connected, undirected graph G has an Euler circuit if and only if every vertex is of even degree. Give an O(e) algorithm to find an Euler circuit in a graph with e edges provided one exists. (Hint: Use depth-first search.)

[UP] [CSGSA]