Description
Problem 1. (20 points)
You have n coins, exactly one of which is counterfeit. You know counterfeit coins weigh more than authentic
coins. Devise an algorithm for finding the counterfeit coin using a balance scale1
. Express your algorithm
in pseudocode. For n = 12, how many weighings does your algorithm use?
Solution.
procedure counterfeit coin(a1 + a2 + a3 + … + an: coin weights)
n = 12
for i = 1 to n
ai−1 → lef t scale
ai → right scale
if right scale < lef t scale
counterfeit location = i
else if lef t scale > right scale
counterfeit location = i − 1
return counterfeit location
1A balance scale compares the weight of objects placed on it. The result of the comparison is either left side heavier, right
side heavier, or both sides equal.
1
Problem 2. (20 points)
Devise an algorithm that takes as input a list of n integers in unsorted order, where the integers are not
necessarily distinct, and outputs the location (index of first element) and length of the longest contiguous
non-decreasing subsequence in the list. If there is a tie, it outputs the location of the first such subsequence.
Express your algorithm in pseudocode. For the list 9, 7, 9, 4, 5, 8, 1, 0, 5, 9, what is the algorithm’s output?
How many comparison operations between elements of the list are used?
Solution.
procedure non-decreasing(a1, a2, a3, …, an: integers)
starting location = 1
length = 0
j = 1
for i = 2 to n
if ai−1 < ai then
length(j) = i − 1 − starting location
location(j) = i
j = j + 1
k = location of first instance of max(length) in array length
length subsequence = length(k)
location subsequence = location(k)
return {length subsequence, locationsubsequence}
The algorithms output would be 3. 9 comparison operators would be used between elements in the list.
2
Problem 3. (20 points)
Arrange the following functions in order such that each function is big-O of the next function: 2 · 3
n, 3n!,
2019 log n,
n
3
106
, n log n,
√
n, 3 · 2
n. Prove your answer is correct by giving the witnesses for each pair of
consecutive functions.
Solution. The following functions are arranged such that that each function is a big-O of the next function.
1. 2019 log n
2019 log n ≤ C
√
n
2019 log n ≤ 2019√
n C = 2019
log n ≤
√
n
0.0 ≤ 1 k > 1
2019 log n is O(
√
n) by taking C = 2019 and k = 1 as witnesses.
2. √
n
√
n ≤ C(n log n)
√
1
n ≤ log n C = 1
1
2 ≤ log 4 k > 4
0.5 ≤ 1. 386 3
√
n is O(n log n) by taking C = 1 and k = 4 as witnesses.
3. n log n
n log n ≤ C(
n
3
106
)
n log n ≤
n
3
106
C = 1
6044 ≤ 6332 k > 1850
n log n is O(
n
3
106
) by taking C = 1 and k = 1850 as witnesses.
4. n
3
106
n
3
106
≤ C(3 · 2
n)
n
3
106
≤ 3 · 2
n C = 1
0 ≤ 3 k > 0
n
3
106
is O(3 · 2
n) by taking C = 1 and k = 0 as witnesses.
5. 3 · 2
n
3 · 2
n ≤ C(2 · 3
n)
3 · 2
n ≤
3
2
(2 · 3
n) C =
3
2
3 · 2
n ≤ 3 · 3
n
2
n ≤ 3
n
2 ≤ 3 k > 1
3 · 2
n is O(2 · 3
n) by taking C =
3
2
and k > 1 as witnesses.
3
6. 2 · 3
n
2 · 3
n ≤ C(3n!)
2 · 3
n ≤
2
3
(3n!) C =
2
3
2 · 3
n ≤ 2 · n!
3
n ≤ n!
2187 ≤ 5040 k > 7
2 · 3
n is O(3n!) by taking C =
2
3
and k > 7 as witnesses
7. 3n!
3n! is O(n!) with C = 4 and k > 0 as witnesses
4
Problem 4. (20 points)
For each of the following functions, give a big-O estimate, including witnesses, using a simple function g(n)
of the smallest order:
1. (n
2 + 8)(n + 1)
2. (n log n + 1)2 + (log n + 1)(n
2 + 1)
3. n
2
n
+ n
n
2
4. n
4 + 5 log n
n3 + 1
5. 2n
4 + 7n
3 + 5n + 3
Solution.
1. (n
2 + 8)(n + 1)
(n
2 + 8)(n + 1) ≤ C(n
3
)
n
3 + n
2 + 8n + 8 ≤ C(n
3 + n
3 + n
3 + n
3
)
n
3 + n
2 + 8n + 8 ≤ 4(n
3
) C = 4
68 ≤ 108 k > 3
Thus n
3
is O((n
2 + 8)(n + 1)) by taking C = 4 and k > 3 as witnesses.
2. (n log n + 1)2 + (log n + 1)(n
2 + 1)
(n log n + 1)2 + (log n + 1)(n
2 + 1) ≤ C(n
3
)
(n log n + 1)(log n + 1 + n
2 + 1) ≤ C(n
3
)
(n log n)
2 + n log n+n log n + 1 + n
3
log n + n
2 + n log n + 1 ≤ C()
n
3
log n + (n log n)
2 + 5n log n + n
3 + 2n
2 + 2 ≤ C(n
3 + n
3 + n
3 + n
3 + n
3
)
n
3
log n + (n log n)
2 + 5n log n + n
3 + 2n
2 + 2 ≤ 5n
3 C = 5
8.06 ≤ 40 k > 3
Thus (n log n + 1)2 + (log n + 1)(n
2 + 1) is O(n
3
) with C = 5 and k > 3 as witnesses.
3. n
2
n
+ n
n
2
n
2
n
+ n
n
2
≤ C(n
2
n
)
n
2
n
+ n
n
2
≤ 2n
2
n
C = 2
2.33 · 1022 ≤ 4.66 · 1022 k > 5
Thus n
2
n
+ n
n
2
is O(n
2
n
) with C = 2 and k > 5 as witnesses.
4. n
4 + 5 log n
n3 + 1
n
4 + 5 log n
n3 + 1
≤ C(n)
n
4
n3 + 1
+
5 log n
n3 + 1
≤ 2n C = 2
5 ≤ 10 k > 5
Thus n
4 + 5 log n
n3 + 1
is O(x) with C = 2 and k > 5 as witnesses
5
5. 2n
4 + 7n
3 + 5n + 3
2n
4 + 7n
3 + 5n + 3 ≤ 2n
4 + n
4 + n
4 + n
4
2n
4 + 7n
3 + 5n + 3 ≤ 5n
4 C = 5
369 ≤ 405 k > 3
Thus 2n
4 + 7n
3 + 5n + 3 is O(n
4
) with C = 5 and k > 3 as witnesses
6
Problem 5. (20 points)
For each of the following functions, determine whether that function is of the same order as n
2
either by
finding witnesses or showing that sufficient witnesses do not exist:
1. 13n + 12
2. n
2 + 1000n log n
3. 3n
4. 3n
2 + n − 5
5.
n
3 + 2n
2 − n + 3
4n
Solution.
Suppose that there are constants C and k for which n
2 ≤ C(13n + 12) whenever n > k. We can divide both
sides of Cn2 ≤ 13n + 12 by n and simplify to n ≤ 3C for values of n > k. However, no matter what C and
k are, the inequality n ≤ 3C cannot hold for all n with n > k. In particular, once we set a value of k, we
see that when n is larger than the maximum of k and C, it is not true that n ≤ C even though n > k. This
contradiction shows that n
2
is not O(13n + 12). Thus the function 13n + 12 is not as the same order as n
2
.
Suppose that there are particular witnesses C and k for which n
2 + 1000n log n ≤ Cn2
. After dividing both
sides by n the resultant is n + log n
1000 ≤ Cn.
3
n
3n
2 + n − 5
n
3 + 2n
2 − n + 3
4n
7
Aggie Honor Statement: On my honor as an Aggie, I have neither given nor received any unauthorized
aid on any portion of the academic work included in this assignment.
Checklist:
1. Did you abide by the Aggie Honor Code?
2. Did you solve all problems and start a new page for each?
3. Did you submit the PDF to eCampus?
8
Powered by TCPDF (www.tcpdf.org)
