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?
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?
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.
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
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
