=========================preview======================
(COMP3711)[2011](f)midterm~rahuja^_30403.pdf
Back to COMP3711 Login to download
======================================================
Fall 2011 midterm solutions

Q1.
(a) .

(b) O, .,

(c) O

(d) O

(e) .



Q2.
(a) O(n log n)

(b) O(n log n)



Q3. We view each number as having d digits of log n bits each. The total running time is then O(dn). When d is a constant, it's O(n), and each number has d log n = O(log n) bits.

Q.4
We can use divide and conquer to solve it.
1. Find the median of the array and partition it into two sub-arrays (or 2 blocks): O(n)
2. Recursively solve two sub problems until we have k blocks

So T(n) = 2T(n/2) + cn. The base case is T(n/k)=1.

If we use recursion tree to solve it, the height of the tree will be log (k) and at each level the summation will be cn. If we add them together, we should get O(nlogk).

Q.5
(a) If S1[n/2] > S2[n/2], there must be at least n/2-1 + n/2 = n -1 elements smaller than S1[n/2]. This means that the n-th element in S1 \union S2 must be in S1[1..n/2] or S2[n/2+1..n]. In particular, it is exactly the n/2-th element in S1[1..n/2] \union S2[n/2+1..n]. Note that this is exactly the same problem as before, except that the array size is now n/2. So we can recursively solve the problem.


Similarly, if S1[n/2] < S2[n/2], there must be at least n-1 elements smaller than S2[n/2]. This means that the n-th element in S1 \union S2 must be in S1[n/2+1..n] or S2[1..n/2]. Then we recursively solve the problem on S1[n/2+1..n] and S2[1..n/2].
We reach the base case when the array size is 1. Since we reduce the problem size by half each time, the running time is O(log n)
(b) Notice that the k-th element must be from S1[1..k] and S2[1..k]. Then we apply the solution in (a) on these two arrays. The running time is thus O(log k).



Q.6
Let Yi =1 if the i-th voter votes for candidate 1, and Yi =0 if he/she votes for candidate 2. We have E[Xi] = 0.99, for i=1,,800, and E[Xi] =0.01 for i=801,,1000. Then E[X] = sum E[Xi] = 800*99% + 200*1% = 794.

Q.7
Please also refer to:
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.84.3173&rep=rep1&type=pdf


(a) The minimum element is at the root. The maximum element is the larger one of the two elements on level 1.

(b) We first insert the new element x on the bottom level.


First suppose x is on a min level. If x is greater than its parent y, we bubble up x only in the
max levels, that is, we repeatedly compare x with the elements on the max levels on the path from the root to x, and swap until we reach an element greater than x. Since the elements on the min levels are smaller than y, which is smaller than x, we dont need to compare x with them, and the min-max heap property is maintained.
If x is smaller than y, we will bubble up x on the min levels, that is, we repeatedly compare x with the elements on the min levels on the path from the root to x, and swap until we reach an element smaller than x. Since the elements on the max levels are greater than y, which is greater t