Analysis of Algorithms, part 1
CS 288
April 27, 2005

  1. Suppose that we are given a state space T and asked to find a solution node in T. Suppose further that T is a tree with infinitely many nodes, but that each node has a maximum of m children (this behavior is fairly common for state spaces). Next, suppose that for each node, the node may be generated from its parent and inspected to see whether is is a solution, all in time O(1). Finally, suppose that T contains a solution node at level s (that is, at distance s from the root), and that no solution nodes that are any closer to the root. Asymptotically, as a function of m and s,

    a) What is the worst-case time to find a solution using breadth-first search?
    b) What is the worst-case time to find a solution using depth-first search?
    c) What is the worst-case space required for the queue in breadth-first search?
    d) What is the worst-case space required for the stack in depth-first search?
    e) Suppose T is not infinite, and that level s is the highest-numbered level in T. Then what is the worst-case space required for the queue in breadth-first search?
    f) Suppose T is not infinite, and that level s is the highest-numbered level in T. Then what is the worst-case space required for the stack in depth-first search?

     

  2. The naive algorithm for multiplying two n-bit integers requires n2 bit multiplications. One divide-and-conquer approach would observe that if n is a power of 2, and r and s are n-bit integers, then r and s may be written in the form
    r = a2n/2 + b, s = c2n/2 + d
    where a, b, c, and d are n/2-bit integers, and that rs may be computed as
    rs = ac2n + (ad + bc)2n/2 + bd
    thus reducing a multiplication problem of size n to four problems of size n/2 (corresponding to finding the products ab, ad, bc, and cd. Unfortunately, this algorithm still requires &Theta(n2) bit multiplications.

    a) Consider the following Strassen-like divide-and-conquer approach: Instead of finding the four products ac, ad, bc, and bd, find the three products ac, bd, and (a+b)(c+d). Show that if these three products can be found, no other multiplications are necessary.

    b) Sketch the resulting divide-and-conquer algorithm in pseudocode. You may assume that n is a power of 2 and that r and s are exactly n bits long.

    c) Asymptotically, how many bit multiplications are necessary for your algorithm? Don't worry about the fact that the sum of two n-bit numbers might have n+1 bits instead of n bits.

     

  3. Consider the instance of the maximum flow problem given by G = ({s,x,y,t}, {(s,x), (s,y), (x,y), (x,t), (y,t)}), where c(s,x) = 10, c(s,y) = 4, c(x,y) = 3, c(x,t) = 4, and c(y,t) = 8. Here the source vertex is vertex s and the sink vertex is vertex t.

    a) What is the value of the optimal flow for this instance? You needn't use any particular solution algorithm here.

    b) What is the minimum cut corresponding to this solution?

    c) What linear programming instance corresponds to the given maximum flow instance?

    d) Trace either a Ford-Fulkerson algorithm on the given minimum flow instance, or the simplex algorithm for the instance of (c). What are the nonzero values of the flow function f(u,v)? Does the value of the flow f equal the value that you gave in (a)? Does this value equal the flow across the cut that you gave in (b)?