CS570 FALL 2006 FINAL SOLUTIONProblem 1: 1.True 2.True 3.False 4.False 5.True 6.True 7.False 8.Unknown9.Unknown 10.TrueProblem 2:Solution 1): Assume that the weight of material 1, material 2 and material3 carried on the cargo plane are x1,x2and x3respectively. Clearly x1≥ 0, x2≥0, x3≥ 0. Then the total revenue is 1000 ∗x1/2+1200∗ x2/1+ 12000∗ x3/3. As thecargo plane can carry a maximum of 100 tons and a maximum of 60 cubic metersof cargo, we have x1+ x2+ x3≤ 100, x1/2 + x2/1 + x3/3 ≤ 60; As Material 1 hasmaximum available amount 40 cubic meters, we have x1/2 ≤ 40;As Material 2 hasmaximum available amount 30 cubic meters, we have x2/1 ≤ 30; As Material 3 hasmaximum available amount 20 cubic meters, we have x3/3 ≤ 20; Hence the linearprogram which optimize revenue is:max(1000 ∗ x1/2 + 1200 ∗ x2/1 + 12000 ∗ x3/3)subject to:x1≥ 0,x2≥ 0,x3≥ 0,x1+ x2+ x3≤ 100,x1/2 + x2/1 + x3/3 ≤ 60,x1/2 ≤ 40,x2/1 ≤ 30,x3/3 ≤ 20.Solution 2):Assume that the amount of material 1, material 2 and material3 carried on the cargo plane are x1,x2and x3respectively. Clearly x1≥ 0, x2≥0, x3≥ 0. Then the total revenue is 1000 ∗ x1+ 1200 ∗ x2+ 12000 ∗ x3. As thecargo plane can carry a maximum of 100 tons and a maximum of 60 cubic metersof cargo, we have x1+ x2+ x3≤ 60, x1∗ 2 + x2∗ 1 + x3∗ 3 ≤ 100; As Material1 has maximum available amount 40 cubic meters, we have x1≤ 40;As Material 2has maximum available amount 30 cubic meters, we have x2≤ 30; As Material 3has maximum available amount 20 cubic meters, we have x3≤ 20; Hence the linearprogram which optimize revenue is:max(1000 ∗ x1+ 1200 ∗ x2+ 12000 ∗ x3)Date: Dec 8, 2006.12 CS570 FALL 2006 FINAL SOLUTIONsubject to:x1≥ 0,x2≥ 0,x3≥ 0,x1+ x2+ x3≤ 60,x1∗ 2 + x2∗ 1 + x3∗ 3 ≤ 60,x1≤ 40,x2≤ 30,x3≤ 20.Problem 3: The problem is essentially the same as Problem 1 in Chapter 5,which is assigned in HW#5.We denote A[1, n], B[1, n] as the sorted array in increasing order and A[k] asthe k − th element in the array. For brevity of our computation we assume thatn = 2s. First we compare A[n/2] to B[n/2]. Without loss of generality, assumethat A[n/2] < B[n/2], then the elements A[1], ..., A[n/2] are smaller than n ele-ments, that is,A[n/2], ..., A[n] and B[n/2], ..., B[n]. Thus A[1], ..., A[n/2] can’t bethe median of the two databases. Similarly, B[n/2], ..., B[n] can’t be the median ofthe two databases either. Note that m is the median value of A and B if and only ifm is the median of A[n/2], ..., A[n] and B[1], ..., B[n/2](We delete the same numberof numbers that are bigger than m and smaller than m), that is, the n/2 smallestnumber of A[n/2], ..., A[n] and B[1], ..., B[n/2]. Hence the resulting algorithm is:Algorithm 1 Median-value(A[1, n], B[1, n], n)if n = 1 thenreturn min(A[n],B[n]);else if A[n/2] > B[n/2]Median-value(A[1, n/2], B[n/2, n], n/2)else if A[n/2] < B[n/2]Median-value(A[n/2, n], B[1, n/2], n/2)end ifFor running time, assume that the time for the comparison of two numbers isconstant, namely, c, then T (n) = T (n/2) + c and thus T (n) = c log n. Hence ouralgorithm is O(log n).Problem 4: This problem is actually equivalent to solving the Subset Sumproblem: Given n items {1, , n} and each has a given nonnegative weight ai, wewant to maximizePaigiven the condition thatPai= t. If the maximum valuereturned is t, then the output is yes, otherwise false. The recursive relation is:½OP T (i, t) = OP T (i − 1, t), if t < ai;OP T (i, t) = max(OP T (i − 1, t), ai+ OP T (i − 1, t − ai), otherwise;Time complexity: Note the we are building a table of solutions M, and wecompute each of the values M[i, t] in O(1) time using the previous values, thus therunning time is O(nt).Or The Subset-Sum algorithm given in the textbook is O(nt), hence the runningtime of our algorithm is O(nt).Problem 5: This problem can easily be reduced into max flow problem. Wedenote the M faculty as {x1, ..., xM} and N courses as {y1, ..., yN}. The reductionis as follows: add source s, sink t in the graph. For each xi, add edge s → xi. Thecapacity lower bound of these edges is 1 and the capacity upper bound is 2.For eachCS570 FALL 2006 FINAL SOLUTION 3yi, add edge yi→ t. The capacity of each edge is 1. For each faculty xi, if xiprefercourse yi1and yi2, add edges xi→ yi1and xi→ yi2in the graph. The capacityof each edge is 1. To find a feasible allocation, we just need to solve the max flowproblem in the constructed graph to find a max flow with value N.Problem 6:a)To compute the length of the longest path, we just need to find a integer ksuch that D(G, k) = Y es and D(G, k + 1) = No. Hence the algorithm is:k = 0;while D(G, k) = Y esk + +;return k;b)True. The longest path problem is NP-complete. The proof is as follows:Clearly given a path we can easily check if the length is k in polynomial time,hence the problem is NP . To prove that it is NP-complete, we prove that eventhe simplest case of longest path problem is NP-complete. The simplest case inour longest path problem is that the weight of each edge is 1. We use a simplereduction from HAMILTON PATH problem: Given an undirected graph, does ithave a Hamilton path, i.e, a path visiting each vertex exactly once? HAMILTONPATH is NP-complete. Given an instance G0=< V0, E0> for HAMILTON PATH,count the number |V0| of nodes in G0and output the instance G = G0, K = |V0|for LONGEST PATH. Obviously, G0has a simple path of length |V0| if and only ifG0has a Hamilton path. Therefore, if we can solve LONGEST PATH problem, wecan easily solve HAMILTON PATH problem. Hence LONGEST PATH Problem