The Titanic is sinking! As a brave captain, you want to split your passengers in half to fit on the two lifeboats on board. For maximum safety, you will want to balance the two boats' carrying weights. To simplify this problem, you assume that the passengers have (positive) integer weights. The question then becomes: assume that there are n people on board, where person i has weight wi E N. Given the non-sorted list (wi,. .. , wn), pick out the people (should be a subset of (1.. -. ,n)) who go on the first lifeboat. The rest will automatically go to the other lifeboat. Your goal is to minimize |(weight in boat 1) - (weight in boat 2)| (a) The nave algorithm is given by: "exhaust all possible combinations of passengers that go to boat 1; in each combination, find the absolute value of boat-passenger-weight dif ference. Return the combination with the smallest absolute value." Find the complexity of the nave algorithm in big-O notation (b) Let C -wi be the total weight of passengers to be allocated. Write another al- gorithm, using DP, that trades off space for time. Your algorithm should run in time O (n C) Hint: This problem is similar to the 1-0 knapsack problem (c) In what case do you expect the nave algorithm to run faster than the DP algorithm you devised? List at least 1 case in which this could happen, assuming that you run both Hint: Just looking at the big-O notation is not enough! We want to know the actual (d) Does the algorithm you found in part (b) run in polynomial time with respect to the algorithms on the same machine. run-time, taking into consideration the constants and lower-order terms if applicable. size of the input? Give a brief (one or two sentence) explanation