Name:
ID:

1. Order the following functions by growth rate. Write a 1 by the fastest, a 2 by the next fastest, etc. If two functions grow at the same rate, write the same number by both of them.

   1. N
   2. sqrt( N )
   3. N^1.5
   4. N²
   5. N log N
   6. N log log N
   7. N log² N
   8. N log ( N² )
   9. 2 / N
   10. 2^N
   11. 2^{N / 2}
   12. 37
   13. N² log N
   14. N³

2. Which recurrence best describes the work done by a typical binary search algorithm?

   1. T(n) = 2 * T(n/2) + O(1)
   2. T(n) = T(n/2) + O(1)
   3. T(n) = T(3n/2) + O(log n)
   4. T(n) = T(n/2) + O(log n)
   5. T(n) = 3 * T(n/2) + O(1)













3. For each of the following code snippets indicate the running time using Big-Oh notation (a reasonable upper bound is good enough - no need for an asymptotically tight bound).

   1. 	  sum = 0;
      	  if ( condition == true )
      	    for ( i = 0 ; i < n ; ++i )
      	      ++sum;
      	  else
      	    for ( i = n ; i > sum * 2 ; --i )
      	      ++sum;
      	  

   2. 	  sum = 0;
      	  for ( i = 0 ; i < n ; ++i )
      	    for ( j = 0 ; j < n ; ++j )
      	      ++sum;
      	  

   3. 	  sum = 0;
      	  for ( i = 0 ; i < n ; ++i )
      	    for ( j = n * n ; j > 0 ; --j )
      	      ++sum;
      	  

   4. 	  sum = 0;
      	  for ( i = 0 ; i < n ; ++i )
      	    for ( j = 0 ; j < i ; ++j )
      	      ++sum;
      	  

   5. 	  sum = 0;
      	  for ( i = 0 ; i < n ; ++i )
      	    for ( j = 0 ; j < i * i ; ++j )
      	      for ( k = 0 ; k < j ; ++k )
      		++sum;
      	  

   6. 	  sum = 0;
      	  for ( i = 0 ; i < n ; ++i )
      	    for ( j = 0 ; j < i * i ; ++j )
      	      if ( j % i == 0 )
      		for ( k = 0 ; k < j ; ++k )
      		  ++sum;
      	  










4. Suppose T₁(N) = O(f(N)) and T₂(N) = O(f(N)), which of the following are true?

   1. T₁(N) + T₂(N) = O(f(N))
   2. T₁(N) * T₂(N) = O(f(N)²)
   3. T₁(N) - T₂(N) = o(f(N)) note the small 'o'
   4. T₁(N) / T₂(N) = O(1)
   5. T₁(N) = O(T₂(N))

5. What is the Big-Oh asymptotic bound for each of the following recurrences?

   1. T(n) = T( n / 2 ) + n
      T(1) = 1
   2. T(n) = 2 T( n / 2 ) + O(1)
      T(1) = 1
   3. T(n) = T( n - 1 ) + T( n / 2 ) + O(1)
      T(1) = 1
   4. T(n) = T( 2n / 3 ) + O(1)
      T(1) = 1
   5. T(n) = T( 3n / 2 ) + O( log n )
      T(1) = 1

6. The sum of xⁱ as i goes from 0 to infinity is equal to 1 / ( 1 - x ) if and only if:

   1. -1 < x < 1
   2. x != 1
   3. 0 < x < 1
   4. x>1
   5. x = 1 / 2

7. Which of the following is not equal to a³ + 4ab²?

   1. a ( a² + ( 6ba / 3 ( ab )⁰ )² )
   2. ( ( 2^1+a+b ) ( 2^1+a-b ) a²b² + a⁴ ) / ( a4^a )
   3. ( a⁴b / ab ) + a ( 2b )²
   4. 4 ( ( ( 2ab² ) + a⁴ ) / 4a )
   5. none of these








8. Which of the following has the greatest value?

   1. log₁₀ 1024
   2. ( log₁₃ 343 ) / ( log₁₃ 7 )
   3. log₂ ( 1 / 128 )
   4. log₈ 256
   5. ( log_aa² ) + ( 2 log_asqrt( a ) )

9. Which of the choices below is a tight asymptotic bound for a function whose runtime is described by the following recurrence?

   T(n) = T( n - 1 ) + n
   T(1) = 1

   1. O(n)
   2. Theta(n)
   3. O(n³)
   4. Theta(n²)
   5. none of the above
10. Show that x⁶² can be computed with eight or fewer multiplications (and no adds, shifts or other operations).


























11. What is the flaw in the following inductive proof?

    Theorem: All dogs are the same color.

    Proof: Proof by induction. Formally, we wish to prove that, for any set of n dogs, all dogs are the same color.

    Base case: n = 1: Clearly, if we have a set of only one dog, the dog is the same color as itself.

    Induction step: We assume that the property is true for some n, and show that it is true for n + 1. We select two sets of n dogs A and B such that all of the n + 1 dogs occur in at least one of the sets A or B, and there is one dog that appears in both sets (call this dog ``Rover''). Since A and B are of size n, we know from the Induction Hypothesis that the dogs in each set are the same color. Moreover, since Rover is in both sets, both sets must be the same color. So, the property holds for n + 1 dogs. QED.

    1. The base case does not cover sets with no dogs (n = 0), so we can't conclude that all dogs are the same color for any number of dogs.
    2. We did not mention what happens for n > 1, so we have not proven the property for any number of dogs.
    3. The given Induction Step does not work when n = 1, so the property does not hold for larger n.
    4. It is just wrong! Dogs are not all the same color. If we just step outside we can prove it!
    5. None of the above.

12. I once heard a story similar to the following: A wise man in ancient China had done a great service to the ruler. The ruler wanted to express his gratitude and offered the wise man the following options

    • 1 billion tons of rice
    • a chess board with one grain of rice on the first square, two grains on the second, four grains on the third, and so on for all 64 squares.

    For the purposes of this question, assume a pound of rice has 10,000 grains, and a ton has 2,000 pounds.

    Which option would you choose? Why?

    How many grains of rice would be on square N of the chess board?

    Imagine that the chess board is infinite, what square would have G grains of rice on it? Use Big-Oh notation if you feel better about doing so.