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

  1. a) The worst-case number of nodes at level k is mk. In the worst case, the solution will be found as the last node at level s. This will require inspection of O(ms) nodes above level s and &Theta(ms) nodes at level s, and thus total time Θ(ms), since each node requires time O(1) to inspect.

    b) Using depth-first search, it may be that a solution is never found. For example, if every node has at least one child, the search will inspect only one node at each level. Since level s may have more than one node, the solution node may not be that node at level s which is inspected.

    c) In perhaps the most natural implementation, after a node is inspected and rejected, its children are enqueued. In this case, when inspecting a node N on level k, the queue will contains the nodes to the right of N on level k, and to the left of N on level k+1. In this worst case, k=s, and the queue size is Θ(ms+1). This can be reduced to Θ(ms) if the rejected node itself is placed in the queue.

    d) The stack holds a path from the root to the current node. Since in general the current node can be arbitrarily far from the root, there is no upper bound on the stack size.

    e) This case differs from (c) since we may assume that nodes at level s have no children. So the worst case is when the solution node is the leftmost node at level s. In this case the queue size will be Θ(ms).

    f) The worst-case stack size is the length of the longest path from a root to a node, which is Θ(s).

    Note that if we fix m, ms+1 is Θ(ms).

  2. a) rs = ac2n + (ad + bc)2n/2 + bd may be found as rs = ac2n + [(a+c)(b+d) - ac - bd]2n/2 + bd
    Note that the multiplications by powers of 2 needn't be explicitly performed.

    b) Assuming a function LeftShift(x,m) that shifts x m bits to the left, one pseudocode version of the algorithm is 

    Multiply(r, s)
         if length(r) = 1 then
           return rs
         else
           let a be the high order n/2 bits of r
           let b be the low order n/2 bits of r
           let c be the high order n/2 bits of s
           let d be the low order n/2 bits of s
           let j = Multiply(a,c)
           let k = Multiply(b,d)
           return  
             LeftShift(j,n) + LeftShift(Multiply((a+b),(c+d))-j-k], n/2) + k
    Note that LeftShift does not actually perform any multiplications.

    c) In time proportional to n (for the additions), we may reduce a problem of size n to 3 problems of size n/2. So in the Master Theorem (Theorem 4.1 of Cormen et al), a=3, b=2, and f(n) is Θ(n), which is O(nlg 3). So case 1 of the theorem applies, and the asymptotic time complexity for T(n), the number of bit multiplications, is Θ(nlg 3).

  3. a) The maximum flow is 11.

    b) The minimum cut divides V into S = {s,x} and T = {y,t}.

    c) Several equivalent answers are possible. One is
    sx <= 10, sy <= 4, xy <=3, xt <= 4, yt <=8
    sx - xy +xt = 0, sy + xy - yt = 0,
    sx >= 0, sy >= 0, xy >= 0, xt >=0, yt >=0,
    where the function to be maximized is sx + sy

    d) A Ford-Fulkerson algorithm could augment the null flow by the paths (s,x,t), (s,y,t), and (s,x,y,t) with respective flows 4, 4, and 3. It needn't augment in this order. Here the total flow of 4 + 4 + 3 is 11, as in (a), and the minimum cut crosses edges (s,y), (x,y), and (x,t), with respective flows 4, 3, and 4, which again total 11.

    In the linear programming case, there would be slack variables and constraints

    a=10-sx, b=4-sy, c=3-xy, d=4-xt, e=8-yt, f=0-sx+xy+xt, g=0+sx-xy-xt, h=0-sy-xy+yt, i=0+sy+xy-yt
    Writing sx in terms of f would give new equations
    sx=0-f+xy+xt, g=-f, a=10+f-xy-xt, z=0-f+xy+xt+sy
    Writing sy in terms of h would give new equations
    sy=0-h-xy+yt, i=-h, b=4+h+xy-yt, z=0-f-h+xt+yt
    Writing xt in terms of d would give new equations
    xt=4-d, sx=4-d-f+xy, a=6+d+f-xy, z=4-d-f-h+yt
    Writing yt in terms of b would give new equations
    yt=4-b+h+xy, sy=4-b, e=4+b-h-xy, z=8-b-d-f+xy
    Writing xy in terms of c would given new equations
    xy=3-c, sx=7-c-d-f, yt=7-b-c+h, a=3+c+d+f, e=1+b+c-h, z=11-b-c-d-f
    Since all coefficients in the equation for z are negative, we may stop and conclude that f(s,x)=7, f(s,y)=4, f(x,y)=3, f(x,t)=4, and f(y,t)=7. The nonzero slack values are 3 for a and 1 for e; these agree with the residual capacities for (s,x) and (y,t).

    Note that this solution is the same as that given by Ford-Fulkerson -- in fact, the last three substitutions correspond to augmentations. In particular, it is consistent with (a) and (b). Also, this solution may be obtained in many different ways, since variables may be rewritten in many different orders.