Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Analysis of Algorithms
Homework 5
1. (a) Consider the following chain of six matrices: A1, A2, A3, A4, A5, and A6, where A1 is 5 × 10, A2 is
10× 3, A3 is 3× 12, A4 is 12× 5, A5 is 5× 50, and A6 is 50× 6. Find an optimal parenthesization of this
matrix-chain. Show both the table containing the optimal number of scalar operations for all slices and the
choice table.
(b) Prove using the strong form of induction that for any n ∈ N, if n ≥ 1 then a full parenthesization of an
n-element expression has n− 1 pairs of parentheses.
2. (a) CLRS 15.3-1
(b) Draw the recursion tree for the merge-sort algorithm on an input sequence of length 16. Explain why
memoization fails to speed up a good divide-and-conquer algorithm like merge-sort.
(c) Consider a variant of the matrix-chain multiplication problem in which the goal is to parenthesize the
sequence of matrices so as to maximize the number of scalar multiplications. Does this problem exhibit
optimal substructure?
3. (project) Recall Fn the recurrence that defines the Fibonacci numbers. Write a function fibDyn that computes
Fibonacci numbers which implements the naive recurrence via dynamic programming.
4. Consider the 0-1 knapsack problem in CLRS chapter 16.
(a) Write functional pseudo-code for a recursive solution to the variation on the 0-1 knapsack problem that
computes the maximum value that can be placed in the knapsack. The first parameter is a sequence of items
(i.e., value-weight pairs), and the second parameter is the knapsack weight capacity. Note that weights are
natural numbers.
(b) (project) Give a dynamic programming solution to the 0-1 knapsack problem that is based on the previous
problem; this algorithm should take and return the same values as the functional pseudo-code above.
Implement this algorithm and call it knapsack.
(c) (project) Implement a function called knapsackContents that takes the same values but returns a
sequence of items that maximize the knapsack’s value.
5. Consider the problem of neatly printing a paragraph on the screen (or on a printer). For the project portion,
put all functions in the file printPar. The input text is a sequence S of n words (represented as strings) of
lengths `1, . . . , `n (measured in characters). The input bound M is the maximum number of characters a line
can hold. The key to neatly printing a paragraph is to identify in the text sequence the lines of the paragraph so
that new-lines can be placed at the end of each line. We can formalize the notion of the “badness” of a line as
the number of extra space characters at the end of the line or∞ if the bound M is exceeded. We can formalize
the notion of the “badness” of a paragraph as the badness of the worst (i.e., maximum) line of the paragraph not
1
including the last line. Thus to identify the lines for a neat paragraph, we seek to minimize the badness of the
paragraph.
(a) If a given line contains words i through j, and we leave exactly one space between words, the number of
extra space characters at the end of the line is M − j+ i−∑jk=i `k. Write functional pseudo-code for the
function e(S,M, i, j) that computes the number of extra space characters at the end of a line.
(b) (project) Write a procedure extraSpace that implements e.
(c) Use the function e to write functional pseudo-code for the function bl(S,M, i, j) that computes line bad-
ness.
(d) (project) Write a procedure badnessLine that implements bl.
(e) Write functional pseudo-code for the recursive function mb(S,M) that computes the minimum paragraph
badness (using slicing). The base case must be that the sequence S is the last line (and not that S is empty).
(f) Write functional pseudo-code for the recursive function mb′(S,M, i) where mb′(S,M, i) = mb(S[i :],
M). The base case must be that the sequence characterized by S and i is the last line (and not that S is
empty).
(g) (project) Write a recursive procedure minBad that implements the function mb′. It should take three
parameters: S, M , and i a slicing index.
(h) (project) Write a procedure minBadDynamic that implements the functionmb′ using dynamic program-
ming. It should take only two parameters: S, and M .
(i) (project) Write a procedure minBadDynamicChoice that implements the function mb′ using dynamic
programming. In addition to returning mb(S,M), it should also return the choices made. Then write a
procedure printParagraph which takes two parameters: S and M that displays the words in S on
the screen using the choices of minBadDynamicChoice. What is the asymptotic running time of your
algorithm?