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)













































































































































学霸联盟