CMPS 102 — Spring 2020 – Homework 3

Updated Ver. 1(25-Oct)

This assignment comprises of five questions and is worth fifty points. It is due on November 09 (10 a.m.)

on Gradescope.

Before you begin the assignment, please read the following carefully.

? Read the Homework Guidelines.

? Every part of each question begins on a new page. Do not change this.

? This does not mean that you should write a full page for every question. Your answers should be short

and precise. Lengthy and wordy answers will lose points.

? Do not change the format of this document. Simply type your answers as directed.

? You are not allowed to work in teams.

? A subset of the questions may be graded due to limited resources.

I have read and agree to the collaboration policy.

Collaborators:

1. (Total: 5 points) Prove that if h1(n) = Θ(f(n)) and h2(n) = Θ(g(n)), then h1(n)h2(n) =

Θ(f(n)g(n)).

Solution.

1

2. (Total: 15 Points) The following recursive algorithm determines whether an array is sorted. Variables

B1,B2 and B3 are Boolean, and ∧ represents the Logical And operator.

1: function FOO(A, p, r) . takes as input an array A[p..r]; precondition r ≥ p

2: if r=p then

3: return TRUE

4: else

5: q ← b(p + r)/2c

6: B1 ← F OO(A, p, q)

7: B2 ← F OO(A, q + 1, r)

8: B3 ← (A[q] ≤ A[q + 1])

9: return (B1 ∧ B2 ∧ B3)

10: end if

11: end function

(a) (1 points) Describe precisely, in a few sentences, what the above algorithm, FOO, does.

Solution.

2

(b) (7 points) Prove, using induction, that the algorithm does what you claimed in (a).

Solution.

3

(c) (2 points) Let T(n) be the number of array comparisons (discussed in lecture) the algorithm

does on an array of size n. Write a recurrence relation of T(n).

Solution.

4

(d) (2 points) Use Masters Theorem to find a tight bound for T(n).

Solution.

5

(e) (3 points) Obtain an exact solution of T(n) and verify the bound.

Solution.

6

3. (Total: 5 pts) Rank the following functions based on their asymptotic growth rate with the SLOWEST

growing function on the TOP and the FASTEST-growing function on the BOTTOM.

If some functions have the same asymptotic growth rate (i.e. they are Θ() of each other), then put

the tied functions on the same line separated by ‘=’. Otherwise, each line should have exactly one

function.

4. (Total: 5 points) Use the c and n0 style definition to prove that that n

3 is not in O(n2).

Solution.

8

5. (Total: 8 points) Determine the largest integer k such that if there is a way to multiply 3 × 3 matrices

using k multiplications (not assuming commutativity of multiplication of matrix elements), then there

is an algorithm to multiply n×n matrices (where n is an exact power of 3) in time o(n

log7

). State your

reasoning clearly. What would the run time of this algorithm be? (Hint: Proceed as in the analysis of

Strassen’s algorithm,

6. (Total: 12 points) In lecture, you saw Karatsuba’s algorithm for integers in base 2 (binary).

(a) (5 points) Now modify and write the algorithm Karatsuba(X,Y) for integers in base 10.

Write a recurrence and compare it with the one we obtained in lecture.

Solution.

10

(b) (2 points) If the input to the algorithm are 1042 and 4200, i.e., Karatsuba(1042, 4200)

list the sub-calls and the corresponding values of the parameters X and Y.

Solution.

11

(c) (5 points) Find the product of 1042 and 4200 using the Karatsuba(1042, 4200) algorithm.

Clearly state the algebra and result for every subcall.

12

版权所有：留学生程序辅导网 2019 All Rights Reserved 联系方式：QQ:99515681 电子信箱：99515681@qq.com

免责声明：本站部分内容从网络整理而来，只供参考！如有版权问题可联系本站删除。