编程代考 COMP3121/9101 (Problem Set 5) School of Computer Science and Engineering, U

COMP3121/9101 (Problem Set 5) School of Computer Science and Engineering, UNSW Sydney Solution. From this problem, we can see that dynamic programming has a very important role in the field
of game theory.
Subproblems: Let us consider the subproblem P (i, j): What is opt(i, j), the maximal amount of money we can definitely win if we play on the subsequence between coins at the position i and j. We also add the requirement that such that j − i + 1 is an even number and 1 ≤ i < j ≤ n. Recurrence: Our recurrence is then 􏰇vi +min{opt(i+2,j),opt(i+1,j−1)}, vj +min{opt(i+1,j−1),opt(i,j−2)} opt(i, j) = max The options inside the min functions represent the choice your opponent takes, either to continue taking from the same end as you took or from the opposite end of the sequence. Order of computation: The problems to find opt(i, j) are solved in order of the size of j − i. Final answer: The maximum amount of money we can win is opt(1, n). Time complexity: The total complexity is O(n2) as this is how many pairs of i,j we have and each stage of the recursion has only constant number of steps (4 table lookups and 2 additions plus two min and one max operations). ■ Exercise 1.6. [K] Given a sequence of n positive or negative integers A1,A2,...,An, determine a contiguous subsequence Ai to Aj for which the sum of elements in the subsequence is maximised. Subproblems: For each 1 ≤ i ≤ n, We solve the following subproblem P (i): what is opt(i), the maximum sum of elements ending with integer i? Base case: If there are no elements chosen, the maximum sum of elements is 0; hence, opt(0) = 0. Recurrence: Suppose that we have chosen the sequence of elements that ends in i − 1, this is what we compute when we compute opt(i − 1). Now, if we are forced to choose Ai (since we always end with integer i), either it’ll increase opt(i − 1) or Ai begins a new chain of elements. Thus, we have opt(i)=Ai +max(opt(i−1),0). To determine the contiguous subsequence, we also keep track of the start element; to do so, we solve the following recursive function. That is, for all 1 ≤ i ≤ n, 􏰇start(i − 1) if opt(i − 1) > 0,
start(i) =
i if opt(i−1)≤0.
Order of subproblems: Since each subproblem depends on the previous subproblems, we solve the subprob-
lems in increasing order of i.
Final answer: We can determine the end of the subsequence by solving the initial subproblems and returning
the index i such that max1≤i≤n opt(i). To return the contiguous subsequence, we return [start(i), i]. Time complexity: Each subproblem can be solved in O(1) since we just determine the maximum of opt(i−1)
and 0. There are n subproblems; therefore, the time complexity is O(n). ■

COMP3121/9101 (Problem Set 5) School of Computer Science and Engineering, UNSW Sydney
Exercise 1.7. [H] Skiers go fastest with skis whose length is close to their height. Consider n skiers with heights h1,h2,…,hn, gets a delivery of m ≥ n pairs of skis, with lengths l1,l2,…,lm. Design an algorithm to assign to each skier one pair of skis to minimise the sum of the absolute differences between the height hi of the skier and the length of the corresponding ski they got, i.e., to minimise
S = 􏰈 􏰀􏰀 h i − l s ( i ) 􏰀􏰀
where s(i) is the index of the skies assigned to the skier of height hi.
Solution. To start, we observe that
Proof. We produce a similar argument to Tutorial 3 question 4.6. As the |·| is the distance between 2 points on a number line, we can consider all possible orientation of hi,hj and ls(i),ls(j) and consider the sum of distance between them. After considering all orientations, we will see that swapping the assignment will always produce a lower or equal sum of difference. (try it yourself!!) ■
This implies that we may initially sort the skiers by height, sort the skis by length, and find some sort of pairing such that there are no crossovers. We now relabel the sorted height and skis as h1, h2, . . . , hn and l1,l2,…,lm.
Subproblems: Consider the following subproblem P (i, j): What is opt(i, j), the minimum cost of matching the first i skiers with the first j skies such that each of the first i skiers gets a ski?
Base case: Our base case is then for all i = j,
opt(i,i)=􏰈|hk −lk|
Claim — For any 2 skiers i and j with hi < hj, then our preferred assignment will have ls(i) < ls(j) (we call this the case of crossover). If this were not the case, we could swap the skis assigned to i and j, which would lower the sum of differences. as this this the case of i skiers are “forced” to pick i skis. Recurrence: Our recurrence for j > i is then
opt(i, j) = min {opt(i, j − 1), opt(i − 1, j − 1) + |hi − lj |} as we consider assigning the skier i with lj and picking the more optimal option.
Order of computation: Note that for this recurrence we need to again be careful of the order of computation for our subproblems. For the discrete grid domain of opt(·), for each (i, j), we require (i, j−1) and (i−1, j−1). Therefore, one such valid order is to compute the subproblems in increasing order of j then increasing order of i.
Final answer: We can now use this value to compute our assignment, by starting at (i, j) = (n, m), we start at (i, j) where i = n and j = m. If opt(i − 1, j − 1) + |hi − lj | < opt(i, j − 1) then s(i) = j and we try again at (i − 1, j − 1). Otherwise, we try again at (i, j − 1). If at any point we reach i = j (our base case), we simply assign s(k) = k for all 1 ≤ k ≤ i. Time complexity: The complexity of our recurrence is then O(nm) for all i, j until opt(n, m). The complexity of retrieval is O(m), as each step of our retrieval, j decreases by exactly 1. The total complexity of our algorithm is then O(mn). COMP3121/9101 (Problem Set 5) School of Computer Science and Engineering, UNSW Sydney Exercise 1.8. [H] You have been handed responsibility for a business in Texas for the next n days. Initially, you have K illegal workers. At the beginning of each day, you may hire an illegal worker, keep the number of illegal workers the same or fire an illegal worker. At the end of each day, there will be an inspection. The inspector on the ith day will check that you have between li and ri illegal workers (inclusive). If you do not, you will fail the inspection. Design an algorithm that determines the fewest number of inspections you will fail if you hire and fire illegal employees optimally. Solution. We start by noticing that: Subproblems: we can consider the subproblem P (i, j): What is opt(i, j), the minimum number of inspections I have failed on day i assuming that on that day I have j many illegal workers? Base case: Our base case is opt(0,K) = 0, since we start with 0 failed inspections before the first day begins. Recurrence: Our recurrence for 1 ≤ i ≤ n and all j such that max(0, K − i) ≤ j ≤ K + i, opt(i−1,j−1) ifj−1≥max(0,K−(i−1))), opt(i, j) = failed(i, j) + min opt(i − 1, j), opt(i−1,j+1) ifj+1≤K+i−1. Here, failed(i,j) returns 1 if the j falls out of the range of [li,ri], and returns 0 otherwise. Note that the first option in the cases corresponds to hiring an illegal worker on the morning of day i, providing that the number of workers the second corresponds to keeping the same number of illegal workers as on the previous day and the third option corresponds to firing a worker from the previous day. Order of computation: we can compute the subproblems in increasing order of j then i. Final answer: The final answer is then min{opt(n,j):max(K−n,0) ≤ j ≤ K+n}. Time complexity: The total complexity is O(n2), as there are n days, and at most 2n + 1 possible values of illegal worker each day. ■ Exercise 1.9. [H] A company is organising a party for its employees. The organisers of the party want it to be a fun party, and so have assigned a fun rating to every employee. The employees are organised into a strict hierarchy, i.e. a tree rooted at the president. There is one restriction, though, on the guest list to the party: an employee and their immediate supervisor (parent in the tree) cannot both attend the party (because that would be no fun at all). Give an algorithm that makes a guest list for the party that maximises the sum of the fun ratings of the guests. Solution. Suppose that T(i) defines the subtree of the tree T of all employees that is rooted by employee i. Then, for each subtree, we will look at the maximum sum of the fun ratings in two ways: one which includes employee i and one that does not include employee i. For each subtree, we define the following quantities: • I(i) is the maximal sum of fun factors fun(i) that satisfies all of the constraints but includes root i, Note — Minimum and maximum illegal workers you could possible have on the evening of day i are max(K −i,0) and K +i. COMP3121/9101 (Problem Set 5) School of Computer Science and Engineering, UNSW Sydney • E(i) is the maximal sum of fun factors fun(i) that satisfies all of the constraints but excludes root i. With these quantities defined, we now perform the dynamic programming approach. Subproblems: We solve the following subproblem P(i): What is opt(i), the maximum sum of the fun ratings of T(i)? Base case: For each i that is a leaf node, opt(i) = fun(i). Recursion: For the recursion, we need to compute two quantities, I(i) and E(i). For each non-leaf node, we need to consider excluding the subordinates (because i is the immediate supervisor of these workers) if we choose to include employee i, or if we exclude i, then we can either choose to exclude the children or include the children of i, whichever value is greater. Thus, we compute I(i) by I(i) = fun(i) + 􏰈 E(jk), 1≤k≤m where j1, . . . , jm are the subordinates of i. We compute E(i) by E(i) = 􏰈 max (I(jk), E(jk)) , 1≤k≤m where j1, . . . , jm are defined as above. In this way, for each child of i, we can either include them or exclude them. Then solving P(i) is simply a matter of max(I(i),E(i)). Order of subproblems and Final answer: We solve the subproblems from the leaves of the tree to the root of the leaves, where the final solution is simply opt(n) = max(I(n), E(n)) where n is the root of the tree. Time complexity: The time complexity is linear in the number of employees because we only need to scan through each of the employees once. Each employee only has one parent. In the worst case, we need to ask every employee exactly once. ■ Exercise 1.10. [H] You have to cut a wood stick into several pieces. The most affordable company, Analog Cutting Machinery (ACM), charges money according to the length of the stick being cut. Their cutting saw allows them to make only one cut at a time. It is easy to see that different cutting orders can lead to different prices. For example, consider a stick of length 10 m that has to be cut at 2, 4, and 7 m from one end. There are several choices. One can cut first at 2, then at 4, then at 7. This leads to a price of 10 + 8 + 6 = 24 because the first stick was of 10 m, the resulting stick of 8 m, and the last one of 6 m. Anotherchoicecouldcutat4,thenat2,thenat7. Thiswouldleadto 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com