CS61B, Summer 2000, HW4 Solutions

7/26/2000

1.

Solution by Jeff Schoner

Fragment 1 is O(n^5).  The outer loop will take n steps.  The next
loop in takes n*n steps.  The most inner loop will take in the worst
case n*n steps as well. Therefor, the solution is n * (n*n) * (n*n)

Fragment 2 is O(n^4).  The outer loop will take n steps.  The next
loop in takes n*n steps in the worst case.  The conditional statement
will evalute to true only i times though.  The worst case for i is n.
So, therefor the solution is n * (n * n) * n.

2.

Solution by Chris Shaw

a) O(f(x) * s(x)) = o(f(x)), assuming s(x) -> 0 as x -> infinity

Choose s(x) = 0, f(x) = x^2 (x squared).  Then we have O(zero) = o(x^2).  
To show equality of sets, you have to show containment in both directions 
(A and B are equal if and only if A is contained in B, and B is contained 
in A).  Note that the only element of O(zero) is zero.  zero, however, is
contained in o(x^2), so that direction is fine.  In the other direction,
note that x is contained in o(x^2), but x is not contained in O(zero).
Therefore the sets are not equal.

b) If f(x) is an element of O(x^3) and g(x) is an element of O(x), then
   f(x)/g(x) is an element of O(x^2).

Let f(x) = x^3 and g(x) = 1.  Then f(x)/g(x) = x^3 which is not in O(x^2).

c) If f(x) is and element of Omega(x) and g(x) is an element of Omega(x), 
   then f(x) + g(x) is an element of Omega(x).

Let f(x) = x and g(x) = -x.  Then f(x) + g(x) = 0, which is not an element
of Omega(x).

d) If f(100) = 1000 and f(1000) = 1000000, then f cannot be O(1).

Let f(x) = 1000 for x not equal to 1000 
           1000000 for x equal to 1000

Then f(x) is in O(1) because it can be upper bounded by a constant.

e) If f1(x), f2(x), ..., fN(x) are a bunch of functions in Omega(1), 
   then the sum is in Omega(N)

See part c).  Let N = 2, f1(x) = 1, f2(x) = -1.


3.

Solution by Chris Shaw

a) n! is an element of Omega(2^n)

Look at the ratio of n! and 2^n:

n!/2^n = (n/2) * ((n-1)/2 * ... * 1/2

For n greater than or equal to 2, n!/2^n is greater than 1/2.  Therefore, 
n! is greater than (1/2) * 2^n.  So, if K = 1/2 and M = 2, we can say that
there exists K > 0 such that abs(n!) >= K * abs(2^n) for all n > M, which is
the definition of Omega().

b) (log(n))^c is an element of O(n) for all c

Note that it doesn't matter which base this logarithm is, since they differ
only by a multiplicative constant (log_b(x) = log_a(x) / log_a(b)).  So I 
will show this for the natural logarithm (ln(n)).

Note that we know that ln(n) is an element of O(n).  Let's break this into
cases for the value of c:

If c = 1, we have (ln(n))^c = ln(n).  We know the ln(n) is in O(n).

If c = 0, we have (ln(n))^c = 1.  We know that 1 is in O(n).

If c < 0, we have (ln(n))^c = 1 / (ln(n))^(abs(c)).  For n > e (remember
that ln(e) = 1) we know that 1 / (ln(n))^(abs(c)) <= ln(n).  Since 
ln(n) is in O(n), and is an upper bound for (ln(n))^c (for c < 0), we know
that (ln(n))^c is in O(n) for c < 0.

If 0 < c < 1, we know that ln(n))^c <= ln(n) for n >= 1.  Therefore 
(ln(n))^c is in O(n) for 0 < c < 1.

If c > 1, it is harder to show.  Note that for n > 1, ln(n) and n are both
positive functions.  So showing that (ln(n))^c <= K * n is equivalent to
showing that ln(n) <= K^(1/c) * n^(1/c).  ln(n) is defined to be the 
integral of 1/t from t = 1 to t = n.  n^(1/c) can also be represented as
an integral: n^(1/c) = (1/c) * the integral of t^(1/c - 1) from t = 0 to 
t = n.  Note that for c > 1 and for t > 1 (this is the restriction we've
already placed on n), t^(1/c - 1) >= 1/t.  Therefore the integral of
t^(1/c - 1) will be greater than or equal to the integral of 1/t.
So we can say for c > 1 and n > 1, that ln(n) <= c * n^(1/c).  This meets the
definition of O().

c) n^3 belongs to Theta(n^3 + 2n^2)

We have to show that n^3 is in O() and Omega() of n^3 + 2n^2.  For all n 
n^3 is less than or equal to n^3 + 2n^2.  Therefore, let K = 1, and M = 0,
to show that the definition of O() is met.

For n greater than or equal to M = 2, and K = 1/2 we can say that
n^3 >= (1/2) * (n^3 + 2n^2) which shows that the definition of Omega() is
met.

d) 1/2 + ... + 1/n is an element of O(log(n))

As in b) it doesn't matter which base we use for the logarithm, because
they will only differ by a multiplicative constant.  Therefore we will use
the natural logarithm (ln(n)) here.

Note that ln(n) equals the definite integral of 1/i from i = 1 to i = n.
This is the area under the curve 1/i from i = 1 to i = n.  Remember back to
calculus where you saw that integrals of positive functions can be lower
bounded by inscribed rectangles.  Drawing the graph of 1/i, note that 
the inscribed rectangles have heights of 1/2, 1/3, ..., 1/n.  Adding together
the area of these rectangles gives 1/2 + ... + 1/n, which is obviously less
than the area of 1/i from i = 1 to i = n.  Therefore K = 1, and n > M = 1
allow the definition of O() to be met.

e) O(abs(f) + abs(g)) = O(max(abs(f),abs(g)))

Once again, to show set equality, we have to show containment in both 
directions (see 2.a above).  So we have to show that any arbitrary function
from the left set has to be in the rights set, vice-versa.  I will omit
the dependent variable x in writing out the functions f(x) and g(x).

Begin by taking a function from O(abs(f) + abs(g)).  Call this function
h1.  Because it is in the set, we know the definition of O() has to be met:
there exists a K1 > 0 such that abs(h1) <= K1 * abs(abs(f) + abs(g)) for
all x > M1.  Note that abs(f) + abs(g) <= 2 * max(abs(f),abs(g)), for all x.
Therefore, abs(h1) <= 2 * K1 * max(abs(f),abs(g)) for x > M1.  Therefore
all functions from the left set appear in the right set.

In the other direction, take a function from O(max(abs(f),abs(g))).  Call
this function h2.  Because it is in the set, we know there exists a K2 > 0
such that abs(h2) <= K2 * max(abs(f),abs(g)) for all x > M2.  Note however, 
that max(abs(f),abs(g)) <= abs(f) + abs(g) for all x.  Therefore, 
abs(h2) <= K2 * (abs(f) + abs(g)) for all x > M2, which shows that all
functions from the right set must appear in the left set.


4. 

Solution by Jeff Schoner

/* The key to this problem is that you cannot PERMANENTLY alter L.  You're
allowed to change it as long as you change it back.
*/

class ReversePrinter {
      public static void reverse(List L, PrintStream str) {
	     L = reverseList(L);
	     List p = L;
	     while (p != null) {
		   str.out.println(p.obj);
	     }

	     L = reverseList(L);
      }

      /* reverses list L, returning the new head of this list
         in O(n) time */
      public static List reverseList(List L) {
	List prevL = L;
	if (prevL == null) return null;
	List currentL = L.next;
	if (currentL == null) return L;
	prevL.next = null;
	List nextL = currentL.next;
	List temp;
	while (currentL != null) {
	    currentL.next = prevL;
	    prevL = currentL;
	    currentL = nextL;
	    if (nextL != null) {
		nextL = nextL.next;
	    }
	}
	return prevL;
      }
}

5.

Solution by Jeff Schoner

The idea is that you have two pointers, one traveling at one
speed and the other a different one.  The most trivial case is
where the first pointer steps one at a time and the second two at a
time.

class LoopTester {
      public static boolean isLoop (List L) {
        List p1 = L;
	List p2prev = null;
	List p2 = L;
	while(true) {
	    /* if we ever encounter a list end, there's no loop */
	    if ((p1 == null) || (p2 == null)) return false;

	    /* advance p2 once, check for equality, then advance it one
	       more */
	    p2prev = p2;
	    p2 = p2.next;
	    if (p2 == p2prev) return false; // knot check
	    if (p1 == p2) return true;

	    /* end of list if this occurs, but we must test for null
	       because p2 is traveling twice as fast through the list
	    */

	    if (p2 == null) return false;
	    p2prev = p2;
	    p2 = p2.next;
	    if (p2 == p2prev) return false; // knot check
	    if (p1 == p2) return true;
	    
	    /* advance p1 one */
	    p1 = p1.next;
	}	     
      }
}
 
6.

Solution by Michael Brudno

/* We go from left to right, and save the indecies on the stack
   It is also possible to do it from right to left while saving 
   the numbers.
*/

class Shadow {
static int[] shadow(int[] A) {
   IntStack s = new IntStack(A.length);
   for(int i = 0; i < A.length; i++){
     while (true) {
       if (s.isEmpty()) {
         s.push(i);
         break;
       }
       else if (A[s.peek()] >= A[i]) {
         s.push(i);
         break;
       }
       else {
         A[s.pop()] = A[i];
       }
    }
  }
  while(!s.isEmpty())
    A.[s.pop()] = 0;
  return A;
}
}

/* Simple wrapper for the Stack */

class IntStack() {
  Stack s = new Stack();
  int peek() { return ((Integer) s.peek()).intValue(); }
  int pop() { return ((Integer) s.pop()).intValue(); } 
  int push(int i) { s.push(new Integer(i)); }
  boolean isEmpty() { return s.isEmpty(); }
}