Here is a solution to last year's midterm, along with explanations,
and a couple additional problems you can try to help you study.

....YOU SHOULD PROBABLY FIRST LOOK OVER THE MIDTERM BY YOURSELF BEFORE
READING FURTHER....


Question 1, A:
--------------
  A good way to solve these problems is to use the method given in the
  notes for recitation 2/14.   It is also helpful to think of O() as
  meaning "at most proportional to" and to think of Omega() as "at least
  proportional to".  Theta() means O() AND Omega().

  1. True.  [The limit of (3n^2 - 4n - 1)/n^2  is 3.]
  2. True.  [The limit of (3n^2 - 4n - 1)/n^3  is 0.]
  3. False.  [2^n grows much faster than n^3.]
  4. True.  [log base 10 of n  = (log base 2 of n)/(log base 2 of 10)]


Here are some more questions:
  a. use Theta() notation to describe 0.5*n^3 - 17*n + 12 as simply as
     possible. 
  b. How are n*log(n) and n^2 related using this notation?


Question 1, B:
--------------
  delete_letter:
        Theta(n). there is one loop that runs n times.  Each iteration takes
	only constant time.

  foo:
	Theta(n^2).  When p == L, the inner loop runs 0 times. When 
	p == L->next, the inner loop runs 1 time.  When p == L->next->next,
	the inner loop runs 2 times, etc.  The total running time is
	1 + 2 + 3 + ... + n  = Theta(n^2).


  c. Here's a question: how long does this take?
	for(i=0; i < n; ++i) {
	  for(j=0; j < i; ++j) {
	    for(k=0; k < j; ++k) {
		++foo;
	    }
          }
        }

        Hint: in at least half of the iterations of the outer loop, i > n/2.


Question 2, A:
--------------
  Well, we had better insert the number 4 first so that we get the
  same number on both sides.  Continue recursively. There are many
  solutions. One is: 		4 2 6 1 3 5 7


  d. Question: What would the tree look like if we inserted the
     numbers in this order? 
	4 1 2 3 5 6 7 
 
Question 2, B:
--------------
  Yes
  No  (when you hit 55, you would have gone right, not left)
  No  (the tree is illegal since 223 is on the left side of the
       subtree rooted at 219)


Question 3
----------
  See the notes for recitation 2/7.

Question 4
----------
  Remember, the preorder traversal visits the root first, so T is the
  root.  Now, looking at the inorder traversal, you can see that "YUO"
  is on the left side of the root and "HIAEV" is on the right side.
   
  The tree is                           T
                                    U       I
                                   Y O    H   E
                                             A V
  Postorder is "youhaveit"


Question 5, A
----------
[Don't worry about this one since we haven't talked about mergesort yet]

Question 5, B
----------
  Step 0 takes time Theta(n).
  Step 1 takes time 2*T(n/2).
  Step 2 takes time Theta(n)
  So, we can describe the running time as:
	T(n) = c*n + 2*T(n/2), for constant c.
  which solves to Theta(n*log n).

Question 6
----------
   The change we need to make to the code is to consider the fact that
   we may want to use item i several times.   We might use it up to
	t/time[i] 
   times.  Here's one way to do it:

	for(int uses=1; uses*time[i] <= t; ++uses) {
	  varr[i][t] = MAX(varr[i][t], 
                           varr[i-1][t - uses*time[i]] + uses*value[i]);
        }

   e. question: suppose you can only use any given item an even number
   of times? How would you change the code?

=============================================================================
answers:
a. Theta(n^3)
b. n*log(n) is O(n^2) but not Omega(n^2).
c. Theta(n^3)
d.            4
             / \
            1   5
             \   \
              2   6
               \   \
                3   7

e. for(int uses=2; uses*time[i] <= t; uses = uses +2)

===========================================================================

		Avrim Blum