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