ECS 122A – Algorithm & Analysis Midterm 2 Solution
Question 2 (5 points each)
1. Divide and conquer 2. Yes
Question 3 (53 Points)
Copyright By PowCoder代写 加微信 powcoder
(a) (1point)10×(5−5)=0 (b) (1point)10×(5−3)=20 (c) (1point)10×(5−1)=40
(10 points) Greedy choice:
Do the assignments in order of decreasing difficult di.
(20 points) Greedy choice property: Answer:
• Outputformat:Let[a1,a2,…,an]bethegivennhomeworkassignmentswithdifficulty[d1,d2,…,dn]. Assume without loss of generality that the assignments are sorted in decreasing difficulty, i.e.,
di ≥di+1(1≤i≤n−1).
• B: Since the input assignments are sorted in decresing difficulty, our greedy solution is B = [1, 2, …, n], i.e., we do homework ai on week i.
• OPT: Let OPT = [o1, …, on] be an optimal solution such that we do homework aoi on week i.
• B′: Suppose ok = 1. i.e., we do assignment a1 on week k in the OPT solution. Then let B′ = [1, o2, o3, …, ok−1, o1, ok+1, on]. (Note: By cut-and-paste method, we replace o1 by 1. But if o1 ̸= 1, we will do homework a1 twice. So we need to replace ok by o1.)
To show B′ is still optimal:
Let p(A) be the points we get when doing the assignments in order specified by A. We have
p(B′)−p(OPT)=(d1×(n−1)+do1 ×(n−k))−(do1 ×(n−1)+d1×(n−k)) = d1 ×(k−1)−do1 ×(k−1)
= (k−1)(d1 −do1) ≥0
So the total points we can get from B′ is greater than or equal to the total points we can get from OPT. OPT is optimal so B′ must also be optimal.
4. (20 points) Suboptimality property: Answer:
Given n assignments [a1, …, an] and an optimal solution OPT = [o1, …, on] to the problem, where ∀1≤i≤n.1≤oi ≤n,weneedtoshowthesolutionB=[o1,…,on−1]isoptimalwhengivenn−1 assignments[a1,…,aon −1,aon +1,an].
Suppose B is not optimal. Then there exists an optimal solution B′ = [b1, …, bn−1]. Let p(A) be the points we get when doing the assignments in order specified by A. We have
p(B′)= ∑ dbi ×(n−1−i) (1) 1≤i≤n−1
p(B)= ∑ doi ×(n−1−i) (2) 1≤i≤n−1
p(B′) > p(B) (3) p(B′ +[on]) = ∑ dbi ×(n−i)+don ×(n−n) = ∑ dbi ×(n−i) (4)
1≤i≤n−1 1≤i≤n−1
p(B+[on]) = p(OPT) = ∑ doi ×(n−i)+don ×(n−n) = ∑ doi ×(n−i) (5)
1≤i≤n−1 1≤i≤n−1 Based on formulas (1), (2) and (3),
∑ dbi ×(n−1−i) > ∑ doi ×(n−1−i) 1≤i≤n−1 1≤i≤n−1
Combining with formulas (4) and (5), p(B′ + [on]) > p(OPT). This is a contradiction.
Conclusion: B is optimal.
(Note: p(B′ + [on]) ̸= p(B′) + doi × (n − n), similar for p(B + [on]).)
Question 4 Dynamic Programming (32 points) Answer:
Take item 4
∑ dbi ×(n−i) > ∑ doi ×(n−i) 1≤i≤n−1 1≤i≤n−1
r[1][1] = r[0][1] = 0
r[2][1] = r[1][1] = 0
r[3][1] = r[2][1] = 0
r[4][1] = max(v4 + r[3][1 − w4], r[3][1]) = max(6 + r[3][0], 0) = max(6, 0) = 6
r[1][2] = r[0][2] = 0
r[2][2] = max(v2 + r[1][2 − w2], r[1][2]) = max(7 + r[1][0], 0) = max(7, 0) r[3][2] = r[2][2] = 7
r[4][2] = max(v4 + r[3][2 − w4], r[3][2]) = max(6 + r[3][1], 7) = max(6, 7) = 7
Take item 2 3.
r[1][3] = max(v1 + r[0][3 − w1], r[0][3]) = max(5 + r[0][0], 0) = max(5, 0) r[2][3] = max(v2 + r[1][3 − w2], r[1][3]) = max(7 + r[1][1], 5) = max(7, 5) = 7 r[3][3] = r[2][3] = 7
r[4][3] = max(v4 + r[3][3 − w4], r[3][3]) = max(6 + r[3][2], 7) = max(13, 7) = 13
Take item 4 and 2 4.
r[1][4] = max(v1 + r[0][4 − w1], r[0][4]) = max(5 + r[0][1], 0) = max(5, 0) = 5 r[2][4] = max(v2 + r[1][4 − w2], r[1][4]) = max(7 + r[1][2], 5) = max(7, 5) = 7 r[3][4] = max(v2 + r[1][4 − w2], r[1][4]) = max(10 + r[2][0], 7) = max(10, 5) = 10 r[4][4] = max(v4 + r[3][4 − w4], r[3][4]) = max(6 + r[3][3], 10) = max(13, 7) = 13
Take item 4 and 2
RUBRICS: For each of the four questions, 1.5 points for each r[i][j] and 2 points for the items being taken.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com