ECS 122A – Algorithm & Analysis Homework 05 Solution
• Identify the corresponding pages for each question according to the outline on Gradescope. • If you handwrite your solutions, make sure they are clear and readable.
Question 1: Suboptimality Property for LCS (20 points)
Prove the suboptimality property for LCS’s dynamic programming algorithm we defined in class. (Hint: Prove the different cases individually.)
Copyright By PowCoder代写 加微信 powcoder
LetXm =⟨x1,x2,…,xm⟩andYn =⟨y1,y2,…,ym⟩bethetwoinputsequences,andOPT=⟨o1,o2,…,ok⟩be
a LCS of Xm and Yn.
The proof has three cases depending on xm, yn, and ok.
• Case 1: To prove that if xm = yn, then B = ⟨o1,o2,…,ok−1⟩ is a LCS of Xm−1 and Yn−1. Proof by contradiction:
Assume that B is not a LCS of Xm−1 and Yn−1.
Then there exists a sequence B′ which is a common sequence of Xm−1 and Yn−1.
B′ + ⟨ok⟩ is a LCS of Xm and Yn and |B′ + ⟨ok⟩| = |B′| + 1 > |B| + 1 = |OPT|.
This is a contradiction because no common sequence of Xm and Yn can be longer than OPT.
• Case2:Toprovethatifxm ̸=yn andok ̸=xm,thenOPTisaLCSofXm−1 andYn. Proof by contradiction:
Assume that OPT is not a LCS of Xm−1 and Yn.
Then there exists a sequence B which is a common sequence of Xm−1 and Yn.
B is a common sequence of Xm and Yn and |B| > |OPT|.
This is a contradiction because no common sequence of Xm and Yn can be longer than OPT.
• Case3:Toprovethatifxm ̸=yn andok ̸=yn,thenOPTisaLCSofXm andYn−1. Proof by contradiction:
Assume that OPT is not a LCS of Xm and Yn−1.
Then there exists a sequence B which is a common sequence of Xm and Yn−1.
B is a common sequence of Xm and Yn and |B| > |OPT|.
This is a contradiction because no common sequence of Xm and Yn can be longer than OPT.
Note: You could say Case 3 is the same as Case 2 without loss of generality.
Question 2: 0-1 Knapsack (40 points total)
0-1 Knapsack is a classical problem that can be solved using dynamic programming. There is a thief with a knapsack that can carry at most weight of C. The thief is stealing jewelry from a store. Each item has a weight and a value. The goal is to maximize the total value but the total weight has to be less than or equal to C. And the items cannot be cut into pieces. The problem is which items the thief should carry.
• an array v[1..n] for the value of each of the n items
• an array w[1..n] for the weight of each of the n items
• a number C for the maximum capacity of the knapsack
• r: the maximum total value the thief can carry
• s: thesetofitemswecarrytogetr
1. (15 points) Define the recursive formula for the problem
Answer: Let r[i][j] denote the max total value we can carry using only items 1 to i given a knapsack
of capacity j.
2. (20 points) Write the pseudo-code for a dynamic-programming algorithm based on your recursive
1 2 3 4 5 6 7 8 9
3. (5 points) Analyze the time complexity of your dynamic-programming algorithm Answer: Θ(nC) for the nested for loop
r[n][C] = max(vn + r[n − 1][C − wn], r[n − 1][C])
knapsack(v, w, C): n = v.size()
r = (n+1) * (C+1) array
for i = for
j = 0 to C:
if i == 0 or j == 0:
r[i][j] = 0 else if w[i] > j:
r[i][j] = r[i-1][j] else:
r[i][j] = max(v[i] + r[i-1][j-w[i]], r[i-1][j]) return r[n][C]
Question 3: Print Neatly (40 points)
Consider the problem of neatly printing a paragraph with a monospaced font (all characters having the same width) on a printer. The input text is a sequence of n words of lengths l1, l2, …, ln, measured in characters. We want to print this paragraph neatly on a number of lines that hold a maximum of M characters each.
Our criterion of “neatness” is as follows. If a given line contains words i through j, where i ≤ 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 − ∑j lk, which must be nonnegative so that the words fit on the line. We wish to minimize k=i
the sum, over all lines except the last, of the cubes of the numbers of extra space characters at the ends of lines. We call the sum the cost of printing neatly.
• an array l = [l1, l2, …, ln] such that li is the number of characters in the ith word
• a non-negative integer M for the maximum number of characters can be fit in each line Output:
• an integer C for the minimum cost of printing the words neatly
• an array P = [p1, p2, …, ] where pj is the index of the last word printed on line j
1. (15 points) Define the recursive formula for the problem Answer:
Let s[i, j] be the number of spaces at the end of a line when the line contains words i + 1, i + 2, …, j.
j s[i,j]=M−j+i+1− ∑ lk
But not all of these words can be put on the same line. We define the cost of printing a line with
words i + 1, …, j as
s[i, j]3
The recursive formula for printing words 1, .., j is
∞ c[i, j] = 0
if s[i, j] < 0
if j = n and s[i, j] ≥ 0 otherwise
0 if j = 0 C[j] = min0≤i
if j == n: c=0
if m > C[i] + c: m = C[i] + c word_idx = i
last_word[j] = word_idx word_idx
W = traceback(last_word) return (C[n], W)
traceback(last_word[0..n]): W = [n]
while i > 0:
W.prepend(last_word[i])
i = last_word[i] return W
// the last word printed on previous line is
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com