Homework 5
Due date: 2/10/2021 right before class
Problem 1
Consider a blob of text in need of formatting. Suppose our text consists of a sequence of words, W = w1, w2, …, wn, where wi consists of ci characters. We have a maximum line length of L . A formatting of W consists of a partition of the words in W into lines. In the words assigned to a single line, there should be a space after each word except the last; and so if wj,wj+1,…,wk are assigned to one line, then we should have
Pk 1 +ck L. j
Give an e cient algorithm to find a partition of a set of words W into valid lines, so that the sum of the squares of the slacks of all lines (including the last line) is minimized. (Chapter 6 question 6 in our book).
0.1 Solution 1
Define the cost of including a line containing words i through j in the sum: lc[i,j] = ⇢ 1 P if words i,…,j don’t fit
(M j + i jk=i lk)3 otherwise
We want to minimize the sum of lc over all lines of the paragraph. Let
OP T [j] denote the cost of an optimal arrangement of words i, . . . , j. OPT[j]=⇢ min1ij{OPT[i 1]+lc[i,j]} ifj>0
0 if j = 0
This allows us to have a dynamic programming algorithm. The algorithm tries to compute the elements of a one-dimensional array OPT[0…n], where OPT[0] = 0, and for i from 1 to n the algorithm computes OPT[i] using the above recursive formula. The final output of the algorithm is OP T [n]. The time complexity is O(n2).
Problem 2
Given a rod of length n inches and an array of prices that contains prices of all pieces of size smaller than n. Determine the maximum value obtainable by
1
sawing up the rod and selling the pieces. For example, if length of the rod is 8 and the values of di↵erent pieces are given as following, then the maximum obtainable value is 22 (by cutting in two pieces of lengths 2 and 6)
length 1 2 3 4 5 6 7 8 price 1 5 8 9 10 17 17 20
Analyze both time and space complexity of your algorithm.
0.2 Solution 2
1 2 3 4 5 6 7 8 9
10
def cutRod(price, n):
if(n <= 0): return 0
max_val = -infinity
# Recursively cut the rod in different pieces # and compare different configurations
for i in range(0, n):
max_val = max(max_val, price[i] + cutRod(price, n - i - 1))
return max_val
Listing 1: algo
Time complexity involves calling cutRod on n 1, n 2, ....1 chunks, and this happens n times. Overall this is an O(n2) algorithm. We are keeping the max val plus a recursive call tree of n elements at each point in time, making the space complexity O(n)
The algorithm involves recursive calls that span all options of cutting the rod into pieces. At each recursion we keep the maximum value of cutting the rod into one of the possible configurations, eventually finding the best one.
Problem 3
We are given a string of letters x1, x2, ..., xn from the English alphabet. For each xj we would like to find the longest proper prefix of x1,x2...xj such that it is also a su x of it, i.e., find a number P(j) < j such that x1,x2...xP(j) = xj P (j)+1, xj P (j)+2...xj and P (j) is the largest one with this property. For example, the longest proper prefix of ababa that is also a su x is aba. Give an algorithm to calculate the array P whose j’th entry is P(j), and analyze its complexity.
For example, given the input ababaca, P = [0, 0, 1, 2, 3, 0, 1].
2
(a) Design a “brute force” algorithm and argue it’s time complexity.
Solution:
The brute force algorithm is check every possible value of P(i) for each x1x2...xi. The algorithm runs in O(n2) time.
(b) Design an O(n) algorithm using dynamic programming. You need to write the recursion first. Solution:
The problem is called to calculating “the failure function” of a pattern string, which is a part of the KMP string matching algorithm. The idea of the recursion is, to calculate P[i], we try to extend the longest previous valid prefix x1..xp[i 1], if it fail, we try to extend the longest proper suffix of x1.. xp[i 1], which is x1.. xp[p[i 1]]. If it fails again, we repeat the process until
no previous prefix can be extend and so, it returns 0. Define Pc[i] inductively: P0[i] = i, c
BRUTEFORCE(x1, x2, . . . , xn) for i 1 to n
P[i] 0
for j 1 to i 1
ifx1x2...xj =xi j+1xi j+2...xi P[i] max(P[i], j)
z }| {
c c 1
and P [i] = P[P [i]] =P[P[..[P[ i]]..]]. The recursion of the problem is
8>0 ><
8
>