xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

算法代写-CMPT307 21-Assignment 1

时间：2021-02-09

CMPT307 21-1 Assignment 1 Answers 1

Due 16:00 Jan 25 (Monday). There are 100 points in this assignment.

Submit your answers (must be typed) in pdf file to CourSys

https://coursys.sfu.ca/2021sp-cmpt-307-d1/.

The work you submitted must be your own. Any collaboration and consulting outside

resources must be explicitly mentioned on your submission.

1. 10 points (Ex. 1.2-2, 1.2-3 of text book)

(a) For inputs of size n, assume insertion sort runs in 8n2 steps and merge sort runs

in 64n log n steps. For which value n does insertion sort run faster than merge sort on

a same machine?

(b) What is the smallest value of n such that an algorithm of running time 100n2 runs

faster than an algorithm of running time 2n on a same machine?

Ans: (a) Find the largest of n that 8n2 < 64n log n. For n ≤ 43, 8n2 < 64n log n, and

for n ≥ 44, 8n2 > 64n log n. From this, insertion sort runs faster than merge sort for

n ≤ 43, otherwise merge sort is faster. (5 points)

(b) Find the smallest n that 100n2 < 2n. For n = 14, 100(14)2 = 19600 > 214 = 16384,

and for n = 15, 100(15)2 = 22500 < 215 = 32768. So, the answer is n = 15. (5 points)

2. 15 points (P 1-1 of text book)

Comparison of running times: For each function f(n) and time t in the following table,

determine the largest size n of a problem that can be solved in time t, assuming that

the algorithm to solve the problem takes f(n) microseconds (10−6 second).

1 1 1 1 1 1

second minute hour day month year

log n 21×10

6

26×10

7

23.6×10

9

28.64×10

10

22.592×10

12

23.1536×10

13

√

n 1× 1012 3.6× 1015 1.29× 1019 7.46× 1021 6.72× 1024 9.95× 1026

n 1× 106 6× 107 3.6× 109 8.64× 1010 2.59× 1012 3.15× 1013

n log n 6.2746× 104 2.8× 106 1.33× 108 2.755× 109 7.187× 1011 7.98× 1011

n2 1000 7745 6× 104 2.94× 105 1.6× 106 5.6× 106

n3 100 391 1532 4420 13736 31593

2n 19 25 31 36 41 44

n! 9 11 12 13 15 16

3. 10 points (Ex 2.1-3 of text book)

Consider the searching problem:

Input: A sequence of n numbers A = (a1, a2, .., an) and a value v.

Output: An index i such that v = A[i] or the special value nil if v is not in A.

CMPT307 21-1 Assignment 1 Answers 2

Write pseudocode for linear search which scans through the sequence, looking for v.

Using a loop invariant, prove your algorithm is correct. Make sure your loop invariant

fulfills the three necessary properties.

Ans:

Linear-Search(A, v) /* assume A has n elements

i = nil;

for j = 1 to n do

if A[j] = v then i = j and return i;

return i

On each iteration of the for loop, the invariant upon entering is that there is no index

k < j so that A[k] = v. In order to proceed to the next iteration of the loop, we

need that for the current value of j, we do not have A[j] = v. If the loop is exited by

A[j] = v, then the value of i returned is the answer. If the loop is exited by searching

all A[j] for j = 1, .., n but no index j such that A[j] = v, then i remains nil which is

the correct answer.

4. 15 points (Ex. 2.1-4)

Consider the problem of adding two n-bit binary integers, stored in two n-element

arrays A and B. The sum of the two integers is stored in binary form in an (n + 1)-

element array C. State the problem formally and write pseudocode for adding the two

integers.

Ans: Input: two n-element arrays A and B containing the n binary digits of two

numbers a and b.

Output: an (n+ 1)-element array C containing the binary digits of a+ b.

(5 points)

Adding n-bit Binary Integers

carry = 0;

for i=n to 1 do

C[i+ 1] = (A[i] +B[i] + carry)(mod2);

if A[i] +B[i] + carry ≥ 2 then carry = 1 else carry = 0;

end for

C[1] = carry

(10 points)

5. 10 points (Ex 2.3-5 of text book)

Referring back to the searching problem in (Ex 2.1-3), observe that if the sequence A

is sorted, we can check the midpoint of A and eliminate half of the elements of A from

further consideration. The binary search algorithm repeats this procedure, halving the

size of the remaining portion of A each time. Write pseudocode, either iterative or

recursive, for binary search. Argue that the worst-case running time of binary search

is Θ(log n).

CMPT307 21-1 Assignment 1 Answers 3

Ans:

The following code is for A sorted in in ascending order ai ≤ aj for i < j.

Binary-Search(A, a, b, v) /* Initial call of Binary-Search with l = 1 and r = n

if l > r then return nil;

m = b(l + r)/2c;

if A[m] = v then return m;

if A[m] > v then return Binary-Search(A, l,m, v)

else return Binary-Search(A,m+ 1, r, v)

(5 points)

Each call results in a constant number of operations plus a call to a problem instance

where the quantity l − r falls by at least a factor of two. So, the runtime satisfies the

recurrence T (n) = T (n/2) +O(1). So, T (n) is Θ(log n) (5 points)

6. 15 points (P 3-2 of text book)

Relative asymptotic growths: Indicate, for each pair of expressions (A,B) in the table

below, whether A is O, o, Ω, ω, or Θ of B. Assume that k ≥ 1, > 0, and c > 1 are

constants. Your answer should be in the form of the table with yes or no written in

each box.

A B O o Ω ω Θ

logk n n yes yes no no no

nk cn yes yes no no no

2n 2n/2 no no yes yes no

nlog c clogn yes no yes no yes

log(n!) log(nn) yes no yes no yes

7. 15 points

Implement the brute-force and divide-and-conquer algorithms for the maximum subar-

ray problem, and compare the running times of the two algorithms on a same machine.

Submit the source codes of your implementations, report the running times of your im-

plementations for n = 10, 20, 50, 100, 200, 500, 1000 and the minimum n0 that for every

n ≥ n0, the divide-and-conquer algorithm runs faster than the brut-force algorithm.

Ans: Source codes (5 points). Running times for n = 10, .., 1000 (5 points). Minimum

n0 (5 points).

8. 10 points (Ex 4.5-1 of text book)

Use the master method to give tight asymptotic bounds for the following recurrences.

(a) T (n) = 2T (n/4) + 1. (b) T (n) = 2T (n/4) +

√

n. (c) T (n) = 2T (n/4) + n. (d)

T (n) = 2T (n/4) + n2.

CMPT307 21-1 Assignment 1 Answers 4

Ans: Master Theorem: Let a ≥ 1, b ≥ 1 be constants, f(n) be a function, and T (n) be

defined on n ≥ 0 by recurrence T (n) = aT (n/b)+f(n). T (n) is bounded asymptotically

as follows:

• If f(n) is O(n(logb a)−) for some constant > 0, then T (n) is Θ(nlogb a).

• If f(n) is Θ(n(logb a)), then T (n) is Θ(nlogb a log n).

• If f(n) is Ω(n(logb a)+) for some constant > 0, and if af(n/b) ≤ cf(n) for some

constant c > 0 and all sufficiently large n, then T (n) is Θ(f(n)).

(a) f(n) is O(n(log4 2)−) for some > 0. So, T (n) = Θ(n(log4 2)) = Θ(

√

n). (3 points)

(b) f(n) = Θ(n(log4 2)). So T (n) = Θ(n(log4 2) log n) = Θ(

√

n log n). (2 points)

(c) f(n) is Ω(n(log4 2)+) for some > 0. So T (n) = Θ(f(n)) = Θ(n). (3 points)

(d) f(n) is Ω(n(log4 2)+) for some > 0. So T (n) = Θ(f(n)) = Θ(n2). (2 points)

学霸联盟

Due 16:00 Jan 25 (Monday). There are 100 points in this assignment.

Submit your answers (must be typed) in pdf file to CourSys

https://coursys.sfu.ca/2021sp-cmpt-307-d1/.

The work you submitted must be your own. Any collaboration and consulting outside

resources must be explicitly mentioned on your submission.

1. 10 points (Ex. 1.2-2, 1.2-3 of text book)

(a) For inputs of size n, assume insertion sort runs in 8n2 steps and merge sort runs

in 64n log n steps. For which value n does insertion sort run faster than merge sort on

a same machine?

(b) What is the smallest value of n such that an algorithm of running time 100n2 runs

faster than an algorithm of running time 2n on a same machine?

Ans: (a) Find the largest of n that 8n2 < 64n log n. For n ≤ 43, 8n2 < 64n log n, and

for n ≥ 44, 8n2 > 64n log n. From this, insertion sort runs faster than merge sort for

n ≤ 43, otherwise merge sort is faster. (5 points)

(b) Find the smallest n that 100n2 < 2n. For n = 14, 100(14)2 = 19600 > 214 = 16384,

and for n = 15, 100(15)2 = 22500 < 215 = 32768. So, the answer is n = 15. (5 points)

2. 15 points (P 1-1 of text book)

Comparison of running times: For each function f(n) and time t in the following table,

determine the largest size n of a problem that can be solved in time t, assuming that

the algorithm to solve the problem takes f(n) microseconds (10−6 second).

1 1 1 1 1 1

second minute hour day month year

log n 21×10

6

26×10

7

23.6×10

9

28.64×10

10

22.592×10

12

23.1536×10

13

√

n 1× 1012 3.6× 1015 1.29× 1019 7.46× 1021 6.72× 1024 9.95× 1026

n 1× 106 6× 107 3.6× 109 8.64× 1010 2.59× 1012 3.15× 1013

n log n 6.2746× 104 2.8× 106 1.33× 108 2.755× 109 7.187× 1011 7.98× 1011

n2 1000 7745 6× 104 2.94× 105 1.6× 106 5.6× 106

n3 100 391 1532 4420 13736 31593

2n 19 25 31 36 41 44

n! 9 11 12 13 15 16

3. 10 points (Ex 2.1-3 of text book)

Consider the searching problem:

Input: A sequence of n numbers A = (a1, a2, .., an) and a value v.

Output: An index i such that v = A[i] or the special value nil if v is not in A.

CMPT307 21-1 Assignment 1 Answers 2

Write pseudocode for linear search which scans through the sequence, looking for v.

Using a loop invariant, prove your algorithm is correct. Make sure your loop invariant

fulfills the three necessary properties.

Ans:

Linear-Search(A, v) /* assume A has n elements

i = nil;

for j = 1 to n do

if A[j] = v then i = j and return i;

return i

On each iteration of the for loop, the invariant upon entering is that there is no index

k < j so that A[k] = v. In order to proceed to the next iteration of the loop, we

need that for the current value of j, we do not have A[j] = v. If the loop is exited by

A[j] = v, then the value of i returned is the answer. If the loop is exited by searching

all A[j] for j = 1, .., n but no index j such that A[j] = v, then i remains nil which is

the correct answer.

4. 15 points (Ex. 2.1-4)

Consider the problem of adding two n-bit binary integers, stored in two n-element

arrays A and B. The sum of the two integers is stored in binary form in an (n + 1)-

element array C. State the problem formally and write pseudocode for adding the two

integers.

Ans: Input: two n-element arrays A and B containing the n binary digits of two

numbers a and b.

Output: an (n+ 1)-element array C containing the binary digits of a+ b.

(5 points)

Adding n-bit Binary Integers

carry = 0;

for i=n to 1 do

C[i+ 1] = (A[i] +B[i] + carry)(mod2);

if A[i] +B[i] + carry ≥ 2 then carry = 1 else carry = 0;

end for

C[1] = carry

(10 points)

5. 10 points (Ex 2.3-5 of text book)

Referring back to the searching problem in (Ex 2.1-3), observe that if the sequence A

is sorted, we can check the midpoint of A and eliminate half of the elements of A from

further consideration. The binary search algorithm repeats this procedure, halving the

size of the remaining portion of A each time. Write pseudocode, either iterative or

recursive, for binary search. Argue that the worst-case running time of binary search

is Θ(log n).

CMPT307 21-1 Assignment 1 Answers 3

Ans:

The following code is for A sorted in in ascending order ai ≤ aj for i < j.

Binary-Search(A, a, b, v) /* Initial call of Binary-Search with l = 1 and r = n

if l > r then return nil;

m = b(l + r)/2c;

if A[m] = v then return m;

if A[m] > v then return Binary-Search(A, l,m, v)

else return Binary-Search(A,m+ 1, r, v)

(5 points)

Each call results in a constant number of operations plus a call to a problem instance

where the quantity l − r falls by at least a factor of two. So, the runtime satisfies the

recurrence T (n) = T (n/2) +O(1). So, T (n) is Θ(log n) (5 points)

6. 15 points (P 3-2 of text book)

Relative asymptotic growths: Indicate, for each pair of expressions (A,B) in the table

below, whether A is O, o, Ω, ω, or Θ of B. Assume that k ≥ 1, > 0, and c > 1 are

constants. Your answer should be in the form of the table with yes or no written in

each box.

A B O o Ω ω Θ

logk n n yes yes no no no

nk cn yes yes no no no

2n 2n/2 no no yes yes no

nlog c clogn yes no yes no yes

log(n!) log(nn) yes no yes no yes

7. 15 points

Implement the brute-force and divide-and-conquer algorithms for the maximum subar-

ray problem, and compare the running times of the two algorithms on a same machine.

Submit the source codes of your implementations, report the running times of your im-

plementations for n = 10, 20, 50, 100, 200, 500, 1000 and the minimum n0 that for every

n ≥ n0, the divide-and-conquer algorithm runs faster than the brut-force algorithm.

Ans: Source codes (5 points). Running times for n = 10, .., 1000 (5 points). Minimum

n0 (5 points).

8. 10 points (Ex 4.5-1 of text book)

Use the master method to give tight asymptotic bounds for the following recurrences.

(a) T (n) = 2T (n/4) + 1. (b) T (n) = 2T (n/4) +

√

n. (c) T (n) = 2T (n/4) + n. (d)

T (n) = 2T (n/4) + n2.

CMPT307 21-1 Assignment 1 Answers 4

Ans: Master Theorem: Let a ≥ 1, b ≥ 1 be constants, f(n) be a function, and T (n) be

defined on n ≥ 0 by recurrence T (n) = aT (n/b)+f(n). T (n) is bounded asymptotically

as follows:

• If f(n) is O(n(logb a)−) for some constant > 0, then T (n) is Θ(nlogb a).

• If f(n) is Θ(n(logb a)), then T (n) is Θ(nlogb a log n).

• If f(n) is Ω(n(logb a)+) for some constant > 0, and if af(n/b) ≤ cf(n) for some

constant c > 0 and all sufficiently large n, then T (n) is Θ(f(n)).

(a) f(n) is O(n(log4 2)−) for some > 0. So, T (n) = Θ(n(log4 2)) = Θ(

√

n). (3 points)

(b) f(n) = Θ(n(log4 2)). So T (n) = Θ(n(log4 2) log n) = Θ(

√

n log n). (2 points)

(c) f(n) is Ω(n(log4 2)+) for some > 0. So T (n) = Θ(f(n)) = Θ(n). (3 points)

(d) f(n) is Ω(n(log4 2)+) for some > 0. So T (n) = Θ(f(n)) = Θ(n2). (2 points)

学霸联盟