Creative problem, not based on any material discussed in class: Let P be a list

Question

Creative problem, not based on any material discussed in class: Let P be a list of k distinct integers in arbitrary order, and let Q be a list of the same integers, also in arbitrary order (unrelated to the order in P). A merging of P and Q is a combined list of 2k integers so that the numbers in P appear in their same relative order, and so that the numbers in Q also appear in their same relative order. For example if P = 5,3,4,2,1 and Q = 3,5,2,4,1, then 5,3,3,4,5,2,4,2,1,1 is a merging of P and Q (the numbers from Q are written with primes to distinguish them from the numbers in P). If you consider the numbers in P and Q to be written on a stack of cards, then a merging can be achieved by shuffling the two stacks together once, and visa verse. In certain applications we want to find a merging which places every number from P before its corresponding number in Q. That is, the first number from P must come before the first number of Q, and the second number from P must come before the second number from Q, etc. We call such an merging a “proper merging”. Among all the possible proper mergings, want one that maximizes the number of times two equal numbers are adjacent. For example, the merging 5, 3, 3, 5, 4, 2, 2, 4, 1, 1 is a proper merging and places three equal numbers together in the merged list. I don’t claim that this merging maximizes the number of equal adjacent numbers. Give an efficient algorithm to take in two lists P and Q of k integers each, and output a proper merging that maximizes the number of equal adjacent numbers. The efficiency of the method should be measured by the number of operations (comparisons) it does. Hint: A method using O(n^2) operations is possible. Creative problem, not based on any material discussed in class: Let P be a list of k distinct integers in arbitrary order, and let Q be a list of the same integers, also in arbitrary order (unrelated to the order in P). A merging of P and Q is a combined list of 2k integers so that the numbers in P appear in their same relative order, and so that the numbers in Q also appear in their same relative order. For example if P = 5,3,4,2,1 and Q = 3,5,2,4,1, then 5,3,3,4,5,2,4,2,1,1 is a merging of P and Q (the numbers from Q are written with primes to distinguish them from the numbers in P). If you consider the numbers in P and Q to be written on a stack of cards, then a merging can be achieved by shuffling the two stacks together once, and visa verse. In certain applications we want to find a merging which places every number from P before its corresponding number in Q. That is, the first number from P must come before the first number of Q, and the second number from P must come before the second number from Q, etc. We call such an merging a “proper merging”. Among all the possible proper mergings, want one that maximizes the number of times two equal numbers are adjacent. For example, the merging 5, 3, 3, 5, 4, 2, 2, 4, 1, 1 is a proper merging and places three equal numbers together in the merged list. I don’t claim that this merging maximizes the number of equal adjacent numbers. Give an efficient algorithm to take in two lists P and Q of k integers each, and output a proper merging that maximizes the number of equal adjacent numbers. The efficiency of the method should be measured by the number of operations (comparisons) it does. Hint: A method using O(n^2) operations is possible. Creative problem, not based on any material discussed in class: Let P be a list of k distinct integers in arbitrary order, and let Q be a list of the same integers, also in arbitrary order (unrelated to the order in P). A merging of P and Q is a combined list of 2k integers so that the numbers in P appear in their same relative order, and so that the numbers in Q also appear in their same relative order. For example if P = 5,3,4,2,1 and Q = 3,5,2,4,1, then 5,3,3,4,5,2,4,2,1,1 is a merging of P and Q (the numbers from Q are written with primes to distinguish them from the numbers in P). If you consider the numbers in P and Q to be written on a stack of cards, then a merging can be achieved by shuffling the two stacks together once, and visa verse. In certain applications we want to find a merging which places every number from P before its corresponding number in Q. That is, the first number from P must come before the first number of Q, and the second number from P must come before the second number from Q, etc. We call such an merging a “proper merging”. Among all the possible proper mergings, want one that maximizes the number of times two equal numbers are adjacent. For example, the merging 5, 3, 3, 5, 4, 2, 2, 4, 1, 1 is a proper merging and places three equal numbers together in the merged list. I don’t claim that this merging maximizes the number of equal adjacent numbers. Give an efficient algorithm to take in two lists P and Q of k integers each, and output a proper merging that maximizes the number of equal adjacent numbers. The efficiency of the method should be measured by the number of operations (comparisons) it does. Hint: A method using O(n^2) operations is possible.

Explanation / Answer

This is a dynamic programming question:

Let dp(i,j,P) be the maximum number of equal adjacent numbers in the list ending with the ith element of P , which contains i numbers from P and j numbers from Q, and j <= i.

Let dp(i,j,Q) be the maximum number of equal adjacent numbers in the list ending with the ith element of Q , which contains i numbers from P and j numbers from Q, and j <= i.

so our result would be dp(n,n,Q)

Now,
dp(i,j,P) can be split into suboptimal solutions and the max of them can be taken:

dp(i-1,j,Q) : if we place ith element of P in front of jth element of Q, add 1 if both are equal

dp(i-1,j,P) : if we place ith element of P in front of i-1th element of P, add 1 if both are equal

Take max of them.

dp(i,j,Q) can be split into suboptimal solutions and the max of them can be taken:

dp(i,j-1,P) : if we place jth element of Q in front of ith element of P, add 1 if both are equal

dp(i,j-1,Q) : if we place jth element of Q in front of j-1th element of Q, add 1 if both are equal

Take max of both of them

since we are calulating a 2*n*n array with O(1) operations.

Complexity == n^2

take max of them

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.