In the partition problem, we ask whether we can divide a multiset [alternatively lmown as a bag or mset} S into two partitions {S1 and S2] that have equal sums D. r z .f'_r x J..- x E 5. y z 5' Note that it is not required that |Srl = |Sz of S in 5:. Recall also that multiset implies that S {and consequently 51 and S2] can contain duplicates, unlike regular sets. For example, if S = {2,2,1,1D,S,15,4,l] then we can produce S 1 = (5,15) and 52 = [2,2,1,1,1E|,4}, both of which sum to 2D {i.e., the difference between the sums of 51 and S} is El}. ; in the extreme case, there may he one element of S in S; and all other elements This deceptively simple problem is computationally demanding. For a set of cardinality n there are 2'\" possible subsets, giving exponential time complexity o[r] if a brute force approach is used [i_e., trying all possibilities}. It is traditionally framed as an DIP-complete decision problem {i.e., producing a yes or no result, depending upon whether an equal-sum partition is or is not possible]. We can also frame it as an optimization problem that aims to minimize the absolute difference between the two sums. For instance, if S = [16,1110] then the optimal partition is S 1 = [2,15] and S: = {5,lfl], which have sums of 1? and 16 respectively, giving an absolute difference of 1. It is the optimization variant of the partition problem that we shall consider here. First, we will empirically and theoretically compare several simple approaches to see how well they minimize the absolute difference between the partitions they produce over a range of cardinalities of S. Dur multiset S can be implemented as an array in any programming language of your choice [although choose wisely; e_g., CID will unnecessarily complicate matters]. The array should be populated widl randomly generated numbers in the range 1 to the 1D x the current cardinality. We will examine the following cardinalities 32, E4, 123, 2513, 512, and 1D24. Since our objective is to divide S to yield two partitions with equal sum, the ideal sum is equal to the sum of all values in 5 divided by 2. The approaches to be compared are: A. Divide S into two equally sized partinions (S; and S; by splitting the array in the middle. E. Take even elements of S for S1 and odd elements of S for S2. C. Add the first element of S to 51 and the second element to 52. Now iterate through the remaining elements, adding them to whichever partition currently has the smallest sum. This is sometimes called greedy partitioning. D. Divide S array into two sub-arrays comprising values s 5 and values is .S . 'We will again use a greedy approach. First iterate through the array of larger values and allocate each to whichever partition has the smallest current sum. Next iterate through the array of smaller values and allocate those to whichever partition has the smallest current sum. E. Sort S into ascending order and then take even elements for 51 and odd numbered elements for S1. F. First sort 5 into descending order. Add the first element of S to S1 and the second element to 52. Now iterate through the remaining elements, adding them to whichever partition currently has the smallest sum. For each approach A..'E', provide a walkthrough example {similar to those above], state the time complexity in bigLl notation, and provide a line graph with multiset cardinality {array length} on the xaxis and mean absolute partition difference on the y-axis. This can be created by exporting your results from lots of repetitions of your test program to plot in Excel, or using a language that supports graph plotting, like hiA'ILAB or Python. Your graph should also contain error bars around each mean {e.g., 1 standard deviation] to show the dispersion of your samples around that mean. This will also help to confirm that you have a sufficient number of results to make reliable inferences. Next, research, describe, implement, and test one additional approach {but not brute force], (3., that works better than A F, above. Each part {A..F] is worth 5%, and G is worth 15% of your mark