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
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
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.
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;
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
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.
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;
C = carry
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
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)
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
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
• 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) 学霸联盟