[10] Problem 4.2-2 pg 60
When looking at the lower bound, we should consider the minimum
depth of the tree. This represented by T(n/3) which results in log3(n).
At each level of the tree, n operations occur. Therefore you get a
minimum of nlog3(n). log3(n) = Omega(lg n). Therefore nlog3(n) =
Omega(nlgn).
[10] Problem 4.3-1 pg 64
a) T(n) = 4T(n/2) + n
n/n^lg4 = n/n^2
T(n) = theta(n^2)
b) T(n) = 4T(n/2) + n^2
n^lg4 = n^2
T(n) = theta(n^2lgn)
c) T(n) = 4T(n/2) + n^3
= theta (n^3)
[10] Problem 6.2-3 pg 109
You should concern yourself with only the permutations of the three
cards. So there are 3*2*1= 6 orderings of the three cards.
Only 1 out of the 6 is in increasing order. So probability is 1/6
[10] Problem 6.3-2 pg 114
Since each number is equally likely, the probability for each is 1/n.
Therefore the expected value is:
E(x) = 1/n (sum i=1 to n of i)
= 1/n (n(n+1)/2) = n+1/2
This holds for both min and max numbers.
[10] Problem 6.3-3 pg 114
E[0] = -1 * (5/6)^3
E[1] = 1 * (1/6)(5/6)^2 * 3
E[2] = 2 * (1/6)^2 (5/6) * 3
E[3] = 3 * (1/6)^3
E[X] = E[0] + E[1] + E[2] + E[3] + E[4]
= -17/216
[10] Problem 8.3-2 pg 163
a) In the worst case there are n-1 calls made to randomized
quicksort.
b) The average case random is called 2^lgn -1 ==> n-1 times
sum of i=0 to logn-1 of 2^i = (2^lgn-1+1/2-1)-1
= 2^lgn -1
= n-1
[10] Problem 8.3-4 pg 163
shuffle(var array A[1..n])
{
for(i=1; i<=n, i++)
{
k= random(1,n)
exchange(A[i], A[k]);
}
}
[10] Problem 8-1 pg 168
a)Let's assume that i and j reference elements outside the interval
[p..r]. If this is ture, i either references an element less than
p or greater than r. Since i is incremented once before an array access,
i never references an element < p. The same holds for j. Since j is
decremented before the first array access, j never references an element
> r. Since i is incremented until i>=j and j is decremented until
j<=i, j is always >= p and i<=r.
b) j=r only if A[j] <= x, If this is the case, A[i] and A[j] are exchanged.
The loop is then executed again. Therefore, j is guaranteed to be
less than r.
c)Every element of A[p..j] is less than or equal to every element of
A[j+1 ..r] because as the i and j are incremented and decremented
respectively, if A[j] is <= x and i < j, the ith and jth elements are
swapped.
[10] Problem 31.2-1 pg 744
|1 3| |8 4| = |r s| = |26 10|
|5 7| |6 2| |t u| |82 34|
P1 = 1*(4-2) = 2
P2 = (1+3) *2 = 8
P3 = (5+7) *8 = 96
P4 = 7*(6-8) = -14
P5 = (1+7)*(8+2) = 80
P6 = (3-7)*(6+2) = -32
P7 = (1-5)*(8+4) = -48
r = P5 + P4 - P2 + P6 = 26
s = P1 + P2 = 10
t = P3 + P4 = 82
u = P5 + P1 - P3 - P7 = 34
[10] Problem 31.2-3 pg 744
T(n) = KT(n/3) + theta(n^2)
n^log3k
Consider the case where n^log3k dominates theta(n^2), k>9.
T(n) = o(n^lg7) when log3k < lg7
i.e when k < 3^lg7 ~ 21.85
k= 21
theta(n^log3k) = theta(n^log3 21) = o(n^2.77)