首页 >
> 详细

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.

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp2

- Csse1001 Assignment 3 2021-01-10
- Comp3506/7505 Homework 4 – Graph Algo 2021-01-10
- Unix & C Programming (Comp1000) Assign... 2021-01-10
- Ece 209 Program 3: Market 2021-01-10
- Informatics 1 — Functional Programming 2021-01-10
- Cisc/Cmpe 452/Cogs400 Assignment 2 2021-01-10
- Fit2100 Operating Systems Assignment #... 2021-01-10
- Csci 1100 — Homework 5 2021-01-10
- Comp9444 Neural Networks And Deep Lea... 2021-01-10
- Assignment Case: German Credit 2021-01-10
- 48024 Applications Programming Assign... 2021-01-10
- Cs 405/805-001: Computer Graphics Ass... 2021-01-10
- Cse 434, Sln 70608 — Computer Networks 2021-01-10
- Corpfin 2503 - Business Data Analytics 2021-01-10
- Cis 455 / 555: Internet And Web System... 2021-01-10
- Cs110留学生编程代写、代做c++程序实验、Program程序语言调试帮做 2021-01-10
- Csc8021程序代做、代写networks编程语言、代做c/C++，Jav 2021-01-10
- 代写program编程语言、代做python，C++，Java程序设计帮做j 2021-01-10
- R编程课程代写、代做program程序语言、R程序实验代做代写databas 2021-01-09
- Data编程设计代做、代写java程序语言、Java程序实验调试代写r语言程 2021-01-09