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

代做CMPS 102课程、代写C++，Java编程
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.
如有需要，请加QQ：99515681 或邮箱：99515681@qq.com 微信：codehelp