University of Waterloo CS 341 Midterm Exam Fall

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

Our website has a team of professional writers who can help you write any of your homework. They will write your papers from scratch. We also have a team of editors just to make sure all papers are of HIGH QUALITY & PLAGIARISM FREE. To make an Order you only need to click Ask A Question and we will direct you to our Order Page at WriteDemy. Then fill Our Order Form with all your assignment instructions. Select your deadline and pay for your paper. You will get it few hours before your set deadline.