CSCI 3110 Midterm 1 11.10.2019
Topics: Asymptotic notation, recurrence relations, divide-and-conquer,
greedy algorithms, dynamic programming
1. (2 marks) Which are true statements?
(a) 4n − 2n = o(3n)
(b) ((n mod 2) + 2)n = O(3n)
(c)
(
n
n−1
)
= Θ(n)
(d) n2 = Ω(n log n)
(e) 2log5 n = ω(
√
n)
Solution: b, c and d
2. (2 marks) There’s an asymptotically faster (but more complicated) ver-
sion of Karatsuba’s algorithm, called Toom-Cook-3, that divides each
number into three parts instead of two. This algorithm multiplies two n-
digit numbers using 5 multiplications of n/3-digit numbers and 20 or 30
additions and subtractions of n/3-digit numbers, with the exact number
of additions and subtractions depending on the implementation. Write
the recurrence for this algorithm, assuming that those additions and
subtractions take a total of 15n time units, and use the Master Theorem
(on the reverse of this sheet) to give its complexity in Theta-notation
(so with formulas in exponents rather than rounded numbers).
Solution: T (n) = 5T (n/3) + 15n so T (n) = Θ(nlog3 5)
3. (2 marks) There’s a fast and simple greedy algorithm for making change
using the fewest coins possible with Canadian coinage: 1-cent, 5-cent,
10-cent, 25-cent, 1-dollar and 2-dollar coins (for simplicity, let’s pretend
1-cent coins still exist). For example, if we want to give $3.87 change,
then we can do so with eight coins — two 1-cent coins, one 10-cent coin,
three 25-cent coins, one 1-dollar coin and one 2-dollar coin — but we
cannot with only seven coins. What is this algorithm? You need not
give a proof of correctness.
Solution: To make change for x cents,
while (x > 0)
let c be the largest coin-value at most x
give (x div c) coins of value c
x = x mod c
end while
4. (2 marks) Give an example of another possible coinage system — i.e.,
a set S of positive integer values in cents, including 1 — and a positive
integer x such that with S, the algorithm you just described uses more
coins than necessary to give x cents change.
Solution: Let S = {1, 3, 4} and x = 6. The algorithm above makes
change with three coins — one 4-cent coin and two 1-cent coins — but
it can be done with two 3-cent coins. Who would ever use such a system?
With the old pounds-shillings-pence system∗, the algorithm would make
48 pence change with a half-crown, a shilling and six-pence whereas it’s
possible to do it with two florins.
∗https://en.wikipedia.org/wiki/%C2%A3sd
5. (2 marks) Suppose you are given two strings S[1..m] and T [1..n] and
asked to find the length of their longest common subsequence (i.e., the
longest string that is a subsequence of both). For example, if S =
HALIFAX and T = HELSINKI then the longest common subsequence
is
S[1]S[3]S[4] = T [1]T [2]T [5] = HLI
of length 3. Give an O(mn)-time algorithm for this problem. You need
not give a proof of correctness.
(Hint: think about the red-and-grey-bridges formulation of Edit Dis-
tance but now with grey bridges being free and red bridges paying you
$1 to cross; watch out for the base cases!)
Solution: Let M [1..m][1..n] be a matrix with M [i][0] = M [0][j] = 0 for
1 ≤ i ≤ m and 1 ≤ j ≤ n. We fill in the matrix with the recurrence
M [i][j] = max(M [i− 1][j],M [i][j − 1],M [i− 1][j − 1] + Xi,j)
where Xi,j is an indicator variable with Xi,j = 1 if S[i] = T [j] and
Xi,j = 0 otherwise. We report M [m][n].