Midterm I – Version B

Oct. 9, 2020, Solution

9:00am - 11:15am
Total Points: 33

• You must follow the rules and procedures posted at course website.

• You must support your answer.

1. (4 points) Relate the following functions by using Θ, ω or o notations:

g1 (n) = n/ log n, g2 (n) = n1.5 log n, g3 (n) = 4log2 n .

Answer:

g1 (n) = o(g2 (n)), g2 (n) = o(g3 (n))

Proof:
n/ log n 1
1. limn→∞ n1.5 log n
= limn→∞ n0.5 log2 n
=0
⇒ n/ log n = o(n1.5 log n)

1 1
n1.5 log n 1.5 ·
2. limn→∞ 4log2 n
= limn→∞ n nlog
2
n
= limn→∞ log n
n0.5
= limn→∞ n ln 2
0.5n−0.5
=
limn→∞ ln22 · n0.51
=0
⇒ n1.5 log n = o(4log2 n )

2 (3 points). Suppose that we have the following algorithm for solving the matrix multiplication
problem. We divide each of the matrices A and B into 9 submatrices with size n/3 × n/3
each. The matrix C = A × B is obtained by using 25 multiplications and 30 additions of the
submatrices. What is the recursive formula of the running time function T (n) of this algorithm?
What is the running time of this algorithm (in Θ notation)?

Answer:
The recursive formula of the running time function is:
(
Θ(1) n=1
T (n) =
25T ( n3 ) + Θ(n2 ) n > 1

By using Master Theorem,

a = 25, b = 3
logb a = log3 25 > 2 = k
Thus
T (n) = Θ(nlog3 25 )

0
3. (4 points) Let f (n) and g(n) be two positive functions. State true or false for each of the
following statements. If the statement is true, briefly prove it. If the statement is false, provide
a counter example.
(a) f (n) = O(g(n)) implies 2f (n) = O(2g(n) ).

(b) f (n) + g(n) = Θ(min{f (n), g(n)}).

Answer:
FALSE
Counter example:
let f (n) = 2n, g(n) = n
f (n) = O(g(n)), but 22n = ω(2n ). Thus 2f (n) 6= O(2g (n))

(b) f (n) + g(n) = Θ(min{f (n), g(n)}).

Answer:
FALSE
Counter example:
let f (n) = n, g(n) = n2
f (n) + g(n) = n2 + n = Θ(n2 ) 6= Θ(n) = Θ(min{f (n), g(n)})

4 (4 points). Find the solution of the following linear recurrence equation.


 1
 if n = 0
an = 6 if n = 1 (1)
n−1 − 9an−2 if n ≥ 2

 6a

Answer:
The characteristic equation is:
x2 − 6x + 9 = 0
(x − 3)2 = 0
the roots of the equation are:
x1 = x2 = 3
thus the solution has the form:

an = A · 3n + B · n · 3n

1
plug in the initial values for n = 0 and n = 1, we have
a0 = 1 = A + 0
a1 = 6 = 3A + 3B
solve it, we have A = 1 and B = 1. Thus
an = 3n + n · 3n = (n + 1)3n

In the following problems, you may need to call algorithms discussed in class or in homework
assignment. If so, you only need to state precisely which algorithms you are calling. You don’t
have to give the details of the called algorithms.

5. (8 points) Let A[1..n] be an unsorted array. All elements in A are distinct. A reversal of A
is a pair of indices i, j such that i < j and A[i] > A[j]. The problem is to calculate the number
of reversals in A[1..n]. For example consider the following array:

i→ 1 2 3 4 5
A[i] → 3 2 1 4 0

The reversals in A are: (3,2), (3,1), (3,0), (2,1), (2,0), (1,0), (4,0). The number of the
reversals in A is thus 7, which is the answer for this particular array.
Describe a DaC algorithm for calculating the number of reversals in A[1..n]. You may assume
n is a power of 2. The runtime of the algorithm must be O(n log n) (or less).
Hint: Modify the Merge Sort algorithm.

Answer: We modify the MergeSort algorithm (which we call FindPair) as follows. In

addition to sort the input array, it also returns the number of reversals in S:

Pseudo-code:
FindPair(S[p, r])
1 if r == p
2 then return 0 and STOP
3 q = (p + r)/2;
4 N1 ← F indP air(S[p, q])
5 N2 ← F indP air(S[q + 1, r])
6 N3 ← M odif iedM erge(S, p, q, r)
7 return {N1 + N2 + N3 }

The ModifiedMerge function called within the FindPair algorithm is a modification of the
original Merge function called within MergeSort. Its high level description is as follows.

• When ModifiedMerge(S, p, q, r) is called, the left sub-array S1 = S[p..q] and the right
sub-array S2 = [q + 1..r] have been sorted. The ModifiedMerge will merge S1 and S2 into
a single sorted array. It also finds and returns the number of reversions (S[i], S[j]) where
S[i] is in S1 and S[j] is in S2.

2
• During the merging process, for each entry S[j] (q + 1 ≤ j ≤ r) in S2 , we find the index
ij (in the range l ≤ ij ≤ q) such that S[ij ] is the largest entry in S1 that is smaller than
S[j]. Namely S[ij ] ≤ S[j] < S[ij + 1]. In other words, when we merge S1 and S2, S[j]
will be inserted right after S[ij ].

• Since all elements in S[ij + 1..q] are larger than S[j], the number of reversals that involves
S[j] is then xj = q − ij .

• Thus the total number of reversals is: X = xq+1 + xq+2 + . . . xr . This sum can be
accumulated during the merging process. The function returns X to FindPair.

Running time analysis:

(
Θ(1) if n = 1
T (n) =
2T ( n2 ) + Θ(n) if n > 2

By using Master Theorem (with a = 2, b = 2), we have T (n) = Θ(n log n).

6. (8 points) Let A[1..n] be an unsorted array of n integers. A may contain repeated

elements. For each i (1 ≤ i < n), we have |A[i] − A[i + 1]| ≤ 1. Suppose u = A[1], w = A[n]
and u < w.
We are given A satisfying above conditions, and another integer v such that u ≤ v ≤ w. We
want to search for v in A[1..n]. Namely, we want to find an index i such that A[i] = v.
Describe an algorithm for solving this problem. The runtime of the algorithm must be
O(log n) (or less).
Hint: There must be an index i such that A[i] = v. Think why this is true. This might help
you to find the solution.

Answer:

• Idea: Imagine you scan array A from A[1] to A[n]. Since, for any i (1 ≤ i < n), |A[i] −
A[i + 1]| ≤ 1, and all entries of A[1..n] are integers, you will see every integer v between
u = A[1] and w = A[n]. This suggests we can solve the problem by using a binary-search
approach, as follows:

• Pseudo-code:
Find(A[1, n], n, v)
1 if A[n/2] = v
2 then return {n/2}
3 if A[n/2] > v
4 then return {F ind(A[1, n/2], n/2, v)}
5 else return {F ind(A[n/2, n], n/2, v)}

• Running time analysis: (

Θ(1) if n = 2
T (n) =
T ( n2 ) + Θ(1) if n > 2

3
By using Master Theorem,
a = 1, b = 2

Thus
T (n) = Θ(log n)