Midterm 2015-2018 answers

2) 20 pts Consider the flow network G below with source s and sink t. The edge capacities are the numbers given near each edge. (a) Find a maximum flow in this network using the Ford Fulkerson algorithm. Show all steps of augmentation. Once you have found a maximum flow, draw a copy of the original network G and clearly indicate the flow on each edge of G in your maximum flow. (12 pts) (b) Find a minimum s-t cut in the network, i.e. name the two (nonempty) sets of vertices that define a minimum cut. (8 pts)

d ), and ( b, t ). The capacities of those edges are, respectively, 2 , 3 , 4, and 4, the sum of which is 13 (which it should be according to the Max Flow/Min Cut Theorem). Note, also in this case that the minimum cut isn’t unique. For example, the cut consisting of the two sets {s, a, b, c, d} and {t} also has capacity 13. 3) 20 pts There is a river going from east to west, on the south bank of the river there are a set of cities 1…N as shown in the figure below. On the northern bank there are also N cities. Each city on the south bank has a unique sister city on the north bank of the river. We use X(i) to denote the sister city corresponding to city i. Suppose you are assigned a task to build bridges to connect the southern cities with their sister cities such that as many bridges as possible are built without any bridges crossing each other. Solve this problem using dynamic programming. a) Recurrence formula (7 pts) Solution 1: If we build a bridge between city i and X(i), then for all cities j<i, we try to build as many bridges as possible such that X(j)<X(i) to avoid crossing. Define OPT(i) as the maximum number of bridges built involving southern cities from 1 to i, while guaranteeing that there is a bridge built between city i and X(i). Base case: OPT(1) = 1 Recursive relation (for i>1): OPT(i) = max_ {k: 1<=k<i, X(k)<X(i)} {OPT(k)} +1 Max_bridge_num = max_ {i} {OPT(i)} …………… …….. …………… …….. River 1 2 3 X(3) X(2) X(N-1) X(9) X(1) N N-1

End End Return Bridge_list Method 2: If you keep recording the choice of whether to build a bridge or not, say using a indicator flag(i) = 1 to represent building a bridge for southern bridge i and 0 otherwise, then Bridge_list = []; For j = 1:N If(flag(j)==1) Bridge_list = [j, Bridge_list]; End End Return Bridge_list; 4) 20 pts There are n reservoirs and m cities. Due to the drought you have to bring water from the reservoirs to the cities through a network of pipes. Each city i has a request for Ci gallons of water every day. To make matters worse, engineers have detected a leaking pipe in the water network. If the leaking pipe is used, they will lose L gallons of water per day through that pipe regardless of how much water flows through it (i.e., as long as the pipe is used, it leaks L gallon, we cannot control the leak by trying to push less water through that pipe). The other option is to shut down the leaking pipe at both ends, but that might reduce the capacity of their network. The water network is represented by a graph. Each edge represents the capacity of the pipe in gallons per day. Provide algorithms to determine if it is possible to: a) Meet all demands for water at all cities without using the leaking pipe (7 pts) Assume the original graph is G=(V,E). Build a new graph with a supersource s and a supersink t. Connect the supersource to each reservoir with an edge of infinity capacity. Connect city i to supersink with capacity C_i Remove the edge corresponding to the leaking pipe. Run a max flow from s to t. If the flow over the edge from city i to supersink t equals to C_i for all city i. Then the demand of all city can be met.

max =search(i+1, j) +1 if A[i][j-1] < A[i][j] and search(i, j-1) +1> max max =search(i, j-1) +1 if A[i][j+1] < A[i][j] and search(i, j+1) +1> max max =search(i, j+1) +1 OPT(i,j) = max return OPT(i,j) find_path(i,j): if OPT(i,j) == 0: return [(i,j)] else if OPT(i,j) = OPT(i-1,j) + 1 return [(i,j), find_path(i-1,j)] if OPT(i,j) = OPT(i+1,j) + 1 return [(i,j), find_path(i+1,j)] if OPT(i,j) = OPT(i,j-1) + 1 return [(i,j), find_path(i,j-1)] if OPT(i,j) = OPT(i,j+1) + 1 return [(i,j), find_path(i,j+1)] OPT(i,j) = -1 for all 1<= i , j <=n result = 0 for i = 1 to n for j = 1 to n if search(i,j) > max max = search(i,j) start = (i,j) return find_path(start) ================================================ The time complexity is O(n^2) because we have n^2 subproblems and solve each of them will require O(1) time. ================================================ You can also solve the problem iteratively as follows: update(i,j): max = 0 if A[i-1][j] < A[i][j] and OPT(i-1, j) +1> max

RCS570 Fall 2017: Analysis of Algorithms Exam II Points Problem 1 20 Problem 2 20 Problem 3 15 Problem 4 15 Problem 5 15 Problem 6 15 Total 100 Instructions: 1. This is a 2-hr exam. Closed book and notes 2. If a description to an algorithm or a proof is required please limit your description or proof to within 150 words, preferably not exceeding the space allotted for that question. 3. No space other than the pages in the exam booklet will be scanned for grading. 4. If you require an additional page for a question, you can use the extra page provided within this booklet. However please indicate clearly that you are continuing the solution on the additional page. 5. Do not detach any sheets from the booklet. Detached sheets will not be scanned. 6. If using a pencil to write the answers, make sure you apply enough pressure so your answers are readable in the scanned copy of your exam. 7. Do not write your answers in cursive scripts.

b) Find the max-flow value and a min-cut. (6 pts) Solution: f = 11, cut: ({S, A, B}, {C, D, T }) Grading Rubics: Max-flow value and min-cut: 6 points in total Max-flow: 2 points. • If you give the wrong value, you lose the 2 points. Min-cut: 4 points • If your solution forms a cut but not a min-cut for the graph, you lose 3 points • If your solution does not even form a cut, you lose all the 4 points c) Prove or disprove that increasing the capacity of an edge that belongs to a min cut will always result in increasing the maximum flow. (4 pts) Solution: increasing (B,D) by one won’t increase the max-flow Grading Rubics: Prove or Disprove: 4 points in total • If you judge it “True”, but give a structural complete “proof”. You get at most 1 point • If you judge it “False”, you get 2 points. • If your counter example is correct, you get the rest 2 points. Popular mistake: a number of students try to disprove it by showing that if the min-cut in the original graph is non-unique, then it is possible to find an edge in one min-cut set, such that increasing the capacity of this does not result in max-flow increase. But they did not do the following thing: The existence of the network with multiple min-cuts needs to be proved, though it seems to be obvious. The most straightforward way to prove the existence is to give an example-network that has multiple min-cuts. Then it turns out to be giving a counter example for the original question statement.

5) 15 pts. You are considering opening a series of electrical vehicle charging stations along Pacific Coast Highway (PCH). There are n possible locations along the highway, and the distance from the start to location k is d k ≥ 0, where k = 1, 2, …, n . You may assume that d i &lt; d k for i &lt; k. There are two important constraints: 1) at each location k you can open only one charging station with the expected profit p k , k = 1, 2, …, n. 2) you must open at least one charging station along the whole highway. 3) any two stations should be at least M miles apart. Give a DP algorithm to find the maximum expected total profit subject to the given constraints. a) Define (in plain English) subproblems to be solved. (3 pts) Let OPT(k) be the maximum expected profit which you can obtain from locations 1, 2, …, k. Rubrics Any other definition is okay as long as it will recursively solve subproblems b) Write the recurrence relation for subproblems. (6 pts) OPT(k) = max{OPT(k − 1), p k + OPT(f(k))} where f(k) finds the largest index j such that d j ≤ d k − M, when such j doesn’t exist, f(k)=0 Base cases: OPT(1) = p 1 OPT(0) = 0 Rubrics: Error in recursion -2pts, if multiple errors, deduction adds up No base cases: -2pts Missing base cases: -1pts Using variables without definition or explanation: -2pts Overloading variables (re-defining n, p, k, or M): -2pts

c) Compute the runtime of the above DP algorithm in terms of n . (3 pts) algorithm solves n subproblems; each subproblem requires finding an index f(k) which can be done in time O(log n) by binary search. Hence, the running time is O(n log n). Rubric: O(n 2 ) is regarded as okay O(d_n n) pseudo-polynomial is also okay if the recursion goes over all d_n values O(n) is also okay O(n 3 ),O(nM), O(kn) : no credit d) How can you optimize the algorithm to have O( n) runtime? (3 pts) Preprocess distances r i = d i – M. Merge d-list with r-list. Rubric Claiming “optimal solution is already found in c” only gets credit when explanation about pre-process is described in either part b or c. Without proper explanation ( e.g . assume we have, or we can do): no credit Keeping an array of max profits: no credit, finding the index that is closest to the installed station with M distance away is the bottleneck, which requires pre- processing.

6) 15 pts. A group of traders are leaving Switzerland, and need to convert their Francs into various international currencies. There are n traders t 1 ,t 2 ,…,t n and m currencies c 1 ,c 2 ,…,c m . Trader t k has F k Francs to convert. For each currency c j , the bank can convert at most B j Franks to c j . Trader t k is willing to trade as much as S kj of his Francs for currency c j .(For example, a trader with 1000 Francs might be willing to convert up to 200 of his Francs for USD, up to 500 of his Francs for Japanese’s Yen, and up to 200 of his Francs for Euros). Assuming that all traders give their requests to the bank at the same time, describe an algorithm that the bank can use to satisfy the requests (if it can). a) Describe how to construct a flow network to solve this problem, including the description of nodes, edges, edge directions and their capacities. (8 pts) Bipartite graph: one partition traders t 1 ,t 2 ,…,t n . Other, available currency, c 1 ,c 2 ,…,c m . Connect t k to c j with the capacity S kj Connect source to traders with the capacity F k . Connect available currency c j to the sink with the capacity B j . Rubrics: - Didn’t include supersource (-1 point) - Didn’t include traders nodes (-1 point) - Didn’t include currencies nodes (-1 point) - Didn’t include supersink (-1 point) - Didn’t include edge direction (-1 point) - Assigned no/wrong capacity on edges between source & traders (-1 point) - Assigned no/wrong capacity on edges between traders & currencies (-1 point) - Assigned no/wrong capacity on edges between currencies & sink (-1 point) b) Describe on what condition the bank can satisfy all requests. (4 pts) If there is a flow f in the network with |f| = F 1 +…+ F n . then all traders are able to convert their currencies. Rubrics: - Wrong condition (-4 points): Unless you explicitly included |f| = F 1 +…+ F n , no partial points were given for this subproblem. - In addition to correct answer, added additional condition which is wrong (-2 points) - No partial points were given for conditions that satisfy only some of the requests, not all requests. - Note that Σ S kj and Σ B j can be larger than Σ F k in some cases where bank satisfy all requests. - Note that Σ S kj can be larger than Σ B j in some cases where bank satisfy all requests. - It is possible that Σ S kj or Σ B j is smaller than Σ F k . In these cases, bank can never satisfy all requests because max flow will be smaller than Σ F k .

c) Assume that you execute the Ford-Fulkerson algorithm on the flow network graph in part a), what would be the runtime of your algorithm? (3 pts) O(n m |f| ) Rubrics: - Flow( |f| ) was not included (-1 point) - Wrong description (-1 point) - Computation is incorrect (-1 point) - Notation error (-1 point) - Missing big O notation (-1 point) - Used big Theta notation instead of big O notation (-1 point) - Wrong runtime complexity (-3 points) - No runtime complexity is given (-3 points)

CS570 Spring 2018: Analysis of Algorithms Exam II Points Problem 1 20 Problem 2 20 Problem 3 20 Problem 4 20 Problem 5 20 Total 100 Instructions: 1. This is a 2-hr exam. Closed book and notes 2. If a description to an algorithm or a proof is required please limit your description or proof to within 150 words, preferably not exceeding the space allotted for that question. 3. No space other than the pages in the exam booklet will be scanned for grading. 4. If you require an additional page for a question, you can use the extra page provided within this booklet. However please indicate clearly that you are continuing the solution on the additional page. 5. Do not detach any sheets from the booklet. Detached sheets will not be scanned.

6. If using a pencil to write the answers, make sure you apply enough pressure so your answers are readable in the scanned copy of your exam. 7. Do not write your answers in cursive scripts. 1) 20 pts Mark the following statements as TRUE or FALSE . No need to provide any justification. [ TRUE/ FALSE ] The residual graph of a maximum flow f can be strongly connected. Note: A directed graph is strongly connected if there is a path from every node to every other node in the graph. [ TRUE /FALSE ] The Ford-Fulkerson algorithm can be used to efficiently compute a maximum matching of a given bipartite graph. [ TRUE/ FALSE ] In successive iterations of the Ford-Fulkerson algorithm, the total flow passing through a vertex in the graph never decreases. [ TRUE/ FALSE ] In a dynamic programming solution, the space requirement is always at least as big as the number of unique sub problems. [ TRUE /FALSE ] Any problem that can be solved with a greedy algorithm can also be solved with dynamic programming. [ TRUE /FALSE ] In a flow network G, if we increase the capacity of one edge by a positive amount x and we observe that the value of max flow also increases by x , then that edge must belong to every min-cut in G. [ TRUE/ FALSE ] If we have a dynamic programming algorithm with n 2 subproblems, it is possible that the running time could be asymptotically strictly greater than Θ (n 2 ). [ TRUE /FALSE ] If we modify the Ford-Fulkerson algorithm by the following heuristic, then the time complexity of the resulting algorithm will be strongly polynomial: At each step, choose the augmenting path with fewest edges. [ TRUE/ FALSE ] The dynamic programming solution (presented in class) to the 0/1 knapsack problem has a polynomial run time.

[ TRUE /FALSE ] Bellman-Ford algorithm runs in strongly polynomial time. 2) 20 pts. Given a list of n integers v 1 , …., v n the “product-sum” of the list is the largest sum that can be formed by multiplying adjacent elements in the list, with the limitation that each element can only be multiplied with at most one of its neighbors. For example, given the list 1,2,3,1 the product sum is 8 = 1 + (2 × 3) + 1, and given the list 2,2,1,3,2,1,2,2,1,2 the product sum is . a) Verify that the product-sum of 1, 4, 3, 2, 3, 4, 2 is 29. (2pts) 29 = 1 + (4 × 3) + 2 + (3 × 4) + 2. Give a dynamic programming algorithm for computing the value of the product-sum of a list of integers. b) Define (in plain English) subproblems to be solved. (5 pts) Let OPT[j] be the product-sum for elements 1..j in the list. Rubric: 1. Mention OPT[j] is the product-sum: 3pts 2. The range should be “from v 1 to v j ”: 2pts Note: Some students incorrectly define the sub-problem as “OPT[i, j] is product- sum of v i to v j ”: 2pts deducted c) Write the recurrence relation for subproblems. (7 pts) Rubric: 1. Give a correct form of the recurrence, say, “OPT[j] = max (…, …)”. In the max function there are two entries, “OPT[j-1] + v j ” and “OPT[j-2] + v j *v j-1 ”: each for 3pts 2. Boundary case arranged correct as “OPT[0] = 0, OPT[1] = v 1 or OPT[1] = v 1 , OPT[2] = max(v 1 + v 2 , v 1 * v 2 )”: 1pt

d) Write pseudo-code to compute the value of the product-sum (You do not need to determine which pairs are multiplied together – we just need the value of the optimal solution.) (4 pts) Prod-Sum(int[ ]v, n) if (n == 0) return 0; int [ ] OPT = new int [n + 1]; OPT[0] = 0; OPT[1] = v[1]; for int j = 2 to n OPT[j] = max(OPT[j − 1] + v[j], OPT[j − 2] + v[j] ∗ v[j − 1]); endfor return OPT[n]; Rubric: 1. If your recurrence in Part(b) is incorrect and the pseudo-code is formed on top of that: 2pts 2. If your Part(b) is correct but the pseudo-code is wrong, e.g., additional for- loop: 3pt 3. Boundary case is correct: 1pt Compute the runtime of the algorithm in terms of n . (2 pts) O(n) Rubric: 1. If you leave Part(c) blank and simply write an answer here: no point 2. If your Part(c) is incorrect and you derive the complexity based on that: 1pt 3. If your Part(c) is correct but the complexity is wrong: 1pt

3) 20 pts A dating website has used complicated algorithms to determine the compatibility between the profiles of men and women on their website. The following graph shows the set of compatible pairs. The website is trying to setup meetings between the men and the women. The i th man has indicated a preference of meeting exactly m i women, while the j th woman prefers to meet at most w j men. All meetings must be between compatible pairs. How would you use network flow to set up the meetings? a) Construct a network flow solution, i.e. draw the network with which you can solve this problem, and explain your construction. (10 pts) Solution: We design a flow network, shown above, such that each unit of flow indicates a meeting between a man and a women. Observe that: • Edges (S, Mi) have capacity mi , enabling man i to be matched with up to mi women.

• Since each man-woman pair should only be matched at most once, edges (Mi , Wj ) have unit capacity. • Edges (Wj , T) have capacity wj , preventing woman j from being matched with more than wj men. Rubrics: Add source and sink linking to all men and all women: 2pt Edge capacity (S,Mi) should have m_i capacity 2 pts Edge (Mi, Wj) should have unit capacity, directed from Mi to Wj: 4 pts Edge (Wj,T) should have w_j capacity 2 pts Or as with the lower bounds: Add source and sink linking to all men and all women: 2pt Edge capacity (S,Mi) should be m_i with m_i lower bound: 2pts Edge capacity (Mi, Wj) should be 1 with 0 lowerbound:4 pts Edge capacity (Wj,T) should be w_j with 0 lowerbound:2 pts Small mistakes -1pt (can add up)

b) Explain how the solution to the network flow problem you constructed in part a will correspond to the solution to our dating problem, and prove the correctness of your solution. (10 pts) We find max flow f. If the value of max flow v(f) equals Σ i mi then we have a feasible solution. Unit flow on edge (Mi , Wj ) indicates that meeting between Mi and Wj takes place in the schedule. Proof of solution: Prove that G has a max flow of Σ i mi iff there is a feasible schedule of meetings for all men and women. A – If we have a max flow of Σ i mi in the network we will have a schedule of meetings between men and women that meets all constraints: - Man i is scheduled to meet with exactly mi women since all edges out of S must be saturated, so there is a flow of exactly mi going into the node corresponding to man i and therefore there are mi edges carrying unit flows from i to mi women, i.e. mi meetings scheduled - Woman j is scheduled to meet with at most wi men since flow over edge connecting woman j to sink t has a capacity of wj, so there cannot be more than wj unit flows coming into j, i.e. j can have up to wj meetings scheduled. B - If we have a schedule of meetings between men and women that meets all constraints, we will have a max flow of Σ i mi in the network: - Send a flow of exactly mi from S to man i - Send a unit flow from man i to woman j if there is a meeting scheduled between them - Send a flow equal to the number of meetings scheduled for woman j, from j to T This will be a max flow since all edges out of S are saturated, and it will be a valid flow since conservation of slow is satisfied at all nodes.

Solution 2: Circulation Build a network similar to that in solution 1, but instead place a demand value of Σ i mi at T and - Σ i mi at S Proof will follow the same argument as in solution 1 Solution 3: Circulation with lower bounds Build a network similar to that in solution 2, but also add lower bounds of mi to those edges between S and man i. These lower bounds are basically redundant in this particular problem and the solution works with or without them. Proof will follow the same argument as in solution 1 Rubric: Mention the matching is possible when we have a max flow 3 pts (Will not be credited if graph in part a is not correct) The value of max flow should be explicitly written as exactly F = sigma m_i to satisfy the condition: 3pts (The value of max flow can be omitted only when the graph was constructed with lower bounds, and claimed a solution with valid flow/circulation) Saying max flow F = sigma m_i = sigma w_j -2pts Correct proof of correctness: 4pts (In order to prove the correspondence, if and only if condition between max-flow ↔ dating solution should be proved. This was handled in the lecture.) Case of weak proof: -2pts for one direction(e.g. stating only “if” statement) proof Not enough explanation about proof: -2pts (e.g. writing statement only)

4) 20 pts. Consider the following flow graph G, with an assigned flow f. The pair x/y indicates that the edge is carrying a flow x and has capacity y. a) Draw the residual Graph for the flow . (10 pts) Solution: We apply the standard construction for the residual graph. If there is a flow of f and capacity c on the edge (u, v), we create an edge of capacity c − f from u to v, and an edge of capacity f from v to u. As shown in the graph below. 6/9 6/9 8/15 7/14 6/9 2/9 4/8 9/12 5/10 2/4 2/10

Rubric: Wrong directions of the edges (-2 ~ -4) Only draw one direction of the connected edges (-4 ~ -5) Miscalculated the value of edges (-1 ~ -5, depends on how many mistakes)

b) Perform one additional step of the Ford-Fulkerson algorithm by choosing an augmenting path with the maximum bottleneck value. Show the residual graph at the end of this step of augmentation. (10 pts) Solution: Choose path S → c → e → b → d → t with bottleneck value of 4. Any other augmenting path cannot reach this value. As shown in the graph below. Rubric: Correct residual graph, but doesn't tell us which is the path (-0.5 ~ -1) Miscalculate the value of edges or the directions (-1 ~ -3, depends on how many mistakes. Notice the direction of the edge between b and e ) Wrote a wrong augmentation path (value is not 4), and drew the residual graph (-5 ~ -6) Only drew the wrong residual graph (-6 ~ -8)

5) 20 pts We want to solve the problem of determining the set of states with the smallest total population that can provide the votes to win the election (electoral college). Formally, the problem can be described as: Let p i be the population of state i, and v i the number of electoral votes for state i. If a candidate wins state i, he/she receives v i electoral votes, and the winning candidate is the one who receives at least V electoral votes, where . Our goal is to find a set of states S that minimizes the value of subject to the constraint that . Give a dynamic programming algorithm for finding the set S. Hint: One way to solve this problem is to turn it into a 0/1 knapsack problem. If you choose this route, you still need to fill out all sections a through e as they relate to solving this particular problem. In other words, you still need to define subproblems, your recurrence formula, etc. in the context of this problem. a) Define (in plain English) subproblems to be solved. (4 pts) Missing some information (-1 pt, each) Solution 1: use 0/1 knapsack to solve the problem OPT(i,w) = max population of states 1..i such that their total vi does not exceed w. We are basically trying to find those states with the highest total population whose total vi does not exceed W = Σ v i – V. This set is the complement of the set that the problem statement is asking for. b) Write the recurrence relation for subproblems. (7 pts) If one part of the recurrence is wrong (-2 pt, each) We accept answer if only mention Max( OPT(i-1,w-vi) + pi, OPT(i-1,w)). Same as in knapsack: OPT(i,w) = OPT(i-1, w) if w < vi , Otherwise Max( OPT(i-1,w-vi) + pi, OPT(i-1,w)) c) Write pseudo-code to compute the optimal value of all unique subproblems. (4 pts) If the base cases / initialization are wrong (-2 pt) If you do not consider the case if W < vi (-2 pt) If one part of the pseudo-code is wrong (-2 pt, each) W = Σ v i – V Initialize OPT(0,w) = 0 for w=0 to W

For i=1 to n For w=0 to W If W< vi OPT(i,w) = OPT(i-1, w) Otherwise OPT(i,w) = Max( OPT(i-1,w-vi) + pi, OPT(i-1,w)) Endfor Endfor Return OPT(n,W) d) Write pseudo-code to find the set of states S. (3 pts) If one part of the pseudo-code is wrong (-2 pt, each) First find those states with the highest total population whose total vi does not exceed Initialize set S to NULL W = Σ v i – V For i=n to 1 by -1 If ( OPT(i-1,W-vi) + pi > OPT(i-1,W) ) then //or If ( OPT(i-1,W-vi) + pi = OPT(i,W) ) then Add i to the set of states S W = W-vi Endif Endfor Our Solution S’ = complement of the set S e) Is the solution you have provided an efficient solution? Give a brief explanation. (2 pt) The answer is correct (1 pt). The explanation is correct (1 pt) No the solution runs in O(nW) which is pseudo-polynomial with respect to the input size, since W represents the numerical value of the input and not the size of the input.

Solution 2: Solve directly a) Define (in plain English) subproblems to be solved. (4 pts) Missing some information (-1 pt, each) OP T[i, v] = minimum populations of a set of states from 1, 2, . . . , i such that their votes sum to exactly v electoral votes. b) Write the recurrence relation for subproblems. (7 pts) If one part of the recurrence is wrong (-2 pt, each) We accept answer if only mention min{OP T[i − 1, v], OP T[i − 1, v − vi ] + pi} OP T[i, v] = OP T[i − 1, v] if v < vi , Otherwise min{OP T[i − 1, v], OP T[i − 1, v − vi ] + pi} c) Write pseudo-code to compute the optimal value of all unique subproblems. (4 pts) If the base cases / initialization are wrong (-2 pt) If you do not consider the case if v < vi (-2 pt) If one part of the pseudo-code is wrong (-2 pt, each) W = Σ v i The important thing here is the initialization: OP T[0, 0] = 0 OP T[0, v] = ∞ for v ≥ 1 For i=1 to n For v=0 to W If v< vi OPT[i, v] = OPT[i − 1, v] Otherwise OPT[i, v] = min{OPT[i − 1, v], OP T[i − 1, v − vi ] + pi} Endfor Endfor Return smallest OPT[i, v] where v >=V and i=n. d) Write pseudo-code to find the set of states S. (3 pts) If one part of the pseudo-code is wrong (-2 pt, each) Initialize set S to NULL Let W = v, where OPT[n, v] was the optimal value of the solution found in part c For i=n to 1 by -1

If ( OPT(i-1,W-vi) + pi < OPT(i-1,W) ) then //or If ( OPT(i-1, W-vi) + pi = OPT(i,W) ) then Add i to the set of states S W = W-vi Endif Endfor Our solution is the set S e) Is the solution you have provided an efficient solution? Give a brief explanation. (2 pt) The answer is correct (1 pt). The explanation is correct (1 pt) No, similar to solution 1. No the solution runs in O(nW) which is pseudo-polynomial with respect to the input size, since W represents the numerical value of the input and not the size of the input.