The Array Collection problem accepts a positive integer k and collection of n so

Question

The Array Collection problem accepts a positive integer k and collection of n sorted arrays containing integers between 1 and k. The output of this problem is a subset of the arrays such that every number 1–k appears in exactly one array, or an empty set, if no solution exists. For example, if k = 5 and we are given the arrays [1, 3, 5], [1, 2, 5], [2, 3], and [2, 4], the solution would be {[1, 3, 5], [2, 4]}. Answer questions 1 and 2 below about the Array Collection problem.

1. Give pseudocode for a greedy algorithm for the Array Collection problem. Note that there is more than one reasonable answer to this problem.

2. Prove that your algorithm is not correct. (There is no greedy algorithm that correctly solves this problem.)

Explanation / Answer

1) Pseudocode:

arraylist = [[1, 3, 5], [1, 2, 5], [2, 3], [2, 4]]

iterate through the arraylist

take the 1st element of 1st arraylist, store it in variable (compvalue)

increase the arraylist + 1. so we move to next array in arraylist

compare the variable (compvalue) with elements of the array

if the value is matched

then delete the array in arraylist

else if value is not matched

increase the arraylist by one but array should not cross the lenghth of the arraylist

2) Since in this algorithm we are deleting the array from lit of array based on first element

we may miss the optimal array which can properly sums up the output. As the deleted array could be the

proper array that sums up the Array collection problem. In that way this algorithm may fail.

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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