University of Waterloo CS 341 Midterm Exam Fall 2014

University of
Waterloo
CS 341 —
Algorithms
Fall 2014
Solutions to
Midterm Examination
1. [25 marks] True-false: 5 marks each.
No justification necessary. Just write “T” or “F”
and write clearly. If we can’t tell
them apart, no credit.
(a) OurO(n2logn) algorithm for solving the “colinear
points in the plane” problem
used the “reduce to known problem”
paradigm.

(b)
Jarvis’ march and Graham’s scan for the convex hull problem are examples of the
divide-and-conquer strategy.

(c)
Givennpoints in the plane, we can find the
two closest inO(nlogn) time.

(d)
The coin-changing problem (make change using the smallest number of coins) is
an example where the greedy algorithm
sometimes works and sometimes fails,
depending on the system of
denominations used.

(e)
Iff, gare functions with logf=O(logg) thenf=O(g).

Multiple-choice question. No
justification necessary. Choose the single best answer.
2. [10 marks] Professor I. M. Smart
discovered a way to multiply ap×qmatrix by aq×r
matrix using only (pqr)3/4scalar multiplications.
Now he wants to solve the optimal
matrix multiplication order (OMMO) problem
taking into account his new method.
Recall that in OMMO we are givennmatrices
M1,M2, . . . ,Mnof differing sizes and we want to find
the optimal cost for computing the
productM1M2···Mnover all possible parenthesizations of
this expression. In class we
discussed a dynamic programming
algorithm called MATRIX-MULT-ORDER (given
below) to solve the problem.
Can we still use the ideas in
MATRIX-MULT-ORDER to compute the optimal cost,
if the matrices are to be multiplied
using Smart’s new method?
Choose the best answer from
(a) Exactly the same algorithm can be
used.

(b) We only have to change the line
q := m[i,k] + m[k+1,j] +
p[i-1]*p[k]*p[j]
in the pseudocode below. Nothing else
significant needs to be changed.

(c) This algorithm cannot be used.

3. [20 marks] Recall that Karatasuba’s
algorithm is a divide-and-conquer algorithm for
multiplying twon-bit integersXandY. It runs inf(n) time, where we
expect that
you remember whatf(n) is.
Suppose we modify it by — instead of
splitting each number into two pieces, each
of sizen/2 — splitting each number intofourpieces,
each of sizen/4. Furthermore,
suppose we have a clever way to obtain
the productXYrecursively using exactlyk
multiplications of thesen/4-bit numbers, and also some constant number of
additions
and subtractions on them. Letg(n) be the running time of this new
algorithm.

(a) [5 marks] Write down a recurrence
relation forg(n) in terms ofkandn.

(b)
[10 marks] What is the largest integer thatkcould be and still improve the
asymptotic bound in Karatsuba, that is,
so thatg=o(f)? Show your work.

(c)
[5 marks] What would the running timeg(n) be for thekyou found in part (b)?
State your answer in the simplest
possible form.

4. [20 marks] Consider the dynamic
programming solution of the LLCS (length of longest
common subsequence) problem, as
described in class, on the two inputs below.
x= “pine-knot ire”
y= “pin-basket skittishness”
Note the presence of a single blank
symbol and a single hyphen in each string. Blanks
and hyphens are treated like every
other symbol.
(a) [10 marks] In the table below, the
entry in rowiand columnjis the length of the
longest common subsequence ofx[1..i] andy[1..j]. Fill in the 16 missing entries in the
array below, following the dynamic
programming algorithm.

(b)
[5 marks] What is the length of the longest common subsequence ofxandy?

(c)
[5 marks] What is a longest common subsequence ofxandy?

5.The barn repair problem.[20 marks]
A barn hasNstalls of equal width laid out in a line, but only
some of them are
occupied by horses. The horses occupy
the stalls in the listL,which may not be in
sorted order.
You want to arrangekboards on top of the stalls so thateach occupied stall is
covered, andas few unoccupied stalls as possible are covered. You get to
choose the length of each board.
For example, consider the followingN= 17 stalls, with 5 horses indicated by the letter
H. HereL={2,16,5,9,11}.
If you have onlyk= 3 boards, then the following arrangement covers
all the occupied
stalls, but also covers 3 unoccupied
stalls (numbers 3, 4, and 10).
For this configuration, with 3 boards,
you can’t do better than covering 3 unoccupied
stalls.
(a) [5 marks] In the diagram above, how
many unoccupied stalls are covered in the
optimal solution fork= 1,2,3,4,5 boards? Fill
in the table below:
knumber of
unoccupied
stalls covered
1 10
2 6
3 3
4 1
5 0
You got 1 free mark here, and 1 mark
for every correct answer.

(b) [15 marks] Develop agreedyalgorithm to compute the optimal board arrange-
ment for any input. An arrangement is
defined to be, for each board, the stall
number where it begins, and the board
length. The input isN, the number of
stalls; a listLof the occupied stalls, in arbitrary order; andk, the number of
boards.
(i) [10 marks] After any needed
preprocessing (be sure to mention what!), your
algorithm should start by covering all
the occupied stalls from the first to the last
with one board. Explain what you need
to do to greedily go from an optimal so-
lution forjboards to an optimal solution forj+1 boards. An English description
is enough, although you can provide
pseudocode, too, if you like. Try to be as
efficient as possible.
Justify correctness briefly.

(ii)
[5 marks] What is the running time of your method in the unit cost model?
You can express it using any of the
parametersN,k, and|L|(the length ofL).

6. [5 marks] This is the hardest
problem, so save it for last.
Recall that lg_(n) is defined to
be the number of times you need to apply log2over and
over tonto obtain a number?1. That is,
lg_(n) =
(
0,ifn?1;
lg_(lgn) + 1,ifn >1.
By analogy we can also define ln_(n) which is
exactly the same, except that we apply
the natural logarithm lnninstead:
ln_(n) =
(
0,ifn?1;
ln_(lnn) + 1,ifn >1.
Prove or disprove: lg_(n) = ln_(n) +O(1).