ECS 122A Midterm Exam I (April 25, 2014) — Solutions

1. (20 points) Define O(n2 ).

Answer: O(n2 ) = {f (n) : ∃ c, n0 such that 0 ≤ f (n) ≤ cn2 for all n ≥ n0 }.

2. (20 points) True or False, with brief justification

1
(a) Let H(n) = 1 + 2 + . . . + n1 . Then H(n) = Θ(n lg n)
Answer: False, H(n) = Θ(lg n)
√ √
(b) log(c n) ∈ O(log n) for all c > 0
√ √
Answer: True, observe that log(c n) = log c + log n.

3. (30 points) Solve the following recurrence relations. Give your answer in Θ(·) notation. Assume
that T (n) ∈ Θ(1) for sufficiently small n.
(a) T (n) = 2 · T (n − 2)
Answer: By the iteration

m
T (n) = 2 · T (n − 2) = 22 T (n − 2 · 2) = · · · = 2k T (n − 2 · k) = Θ(2k ) = Θ(2n/2 )

er as
co
√

eH w
n


(b) T (n) = 2 · T 4 + 10 n

o.
Answer. Since √ √
10 n n
rs e log
n 4 2
= 1/2 = 10.
n
ou urc
√
By case 2 of the master theorem, we have T (n) = Θ(nlog4 2 lg n) = Θ( n lg n).

4. (20 points) Suppose we use Huffman coding to compress a 50,000-symbol file containing 5
o

different symbols, each of which occurs equally often. What will the output size be, measured
aC s

in the number of bits?

vi y re

Answer: 120,000 bits.

5. (30 points) Consider a set of S of n ≥ 2 distinct numbers given in unsorted order. Each of the
following problem asks you to give an algorithm to determine two distinct numbers x, y ∈ S
ed d

satisfying a stated condition. In as few words as possible, by using algorithms from lectures
ar stu

and homeworks as subroutines (no pseduocodes necessary), describe your algorithm and justify
its running time.
(a) In O(n) time, determine x, y ∈ S such that |x − y| ≥ |w − z| for all w, z ∈ S.
sh is

Answer: x and y are two farthest apart.

Th

Find min and max, each in O(n) time.

(b) In O(n lg n) time, determine x, y ∈ S such that x 6= y and |x − y| ≤ |w − z| for all w, z ∈ S
such that w 6= z.
Answer: x and y are the two closest numbers.
First sort with MergeSort; then scan the sorted numbers for the two adjacent numbers with
the minimum differences. Total cost: O(n lg n) + O(n) = O(n lg n)
Alternatively, use the divide-and-conquer algorithm to find the closest pair of points – O(n lg n).

https://www.coursehero.com/file/22386754/midtermIsol2014/
 6. (30 points) Consider the following algorithm that given an array A[1, 2, . . . , n] and a value x
checks whether there is an index i such that A[i] = x. Assume for simplicity that n is a power
of 2.
Initially, we call Find(A,0,n,x). When we call Find(A,start,end,x), we get TURE if and
only if there is an index i such that start < i ≤ end and A[i] = x.

Find(A,start,end,x)
if end - start == 1
if A[end] == x then
return TRUE
else
return FALSE
endif
else
middle = start + ( end - start )/2
return Find(A,start,middle,x) OR Find(A,middle,end,x)
endif

m
er as
co
eH w
(a) Write the recurrence relation that defines the running time of Find(A,0,n,x).
(b) Solve it with the master method.

o.
rs e
Answer: (a) The important part of this question is figuring out what the OR operation does
ou urc
in the worst case. If the first FIND returns FALSE, then the second FIND must be run to
determine the final value returned. In the worst case, both FIND functions are executed. The
if-else statement is a constant time operation for each iterations
o

T (n) = 2T (n/2) + c
aC s
vi y re

(b) By the master method, T (n) = Θ(n).

ed d
ar stu
sh is
Th

https://www.coursehero.com/file/22386754/midtermIsol2014/

Powered by TCPDF (www.tcpdf.org)