3. The Trader Whole's grocery store is open every day until 9p.m at which point there are n customers waiting in line to check out and no new customer can join the waiting line. Currently, Trader Whole's has two registers with separate lines, and a greeter directs customers to either line. To avoid confusion at closing time, once a customer has joined a line, he should not be redirected to the other one. You can assume that each customer will take time ti 0 at the register and that ti can be estimated accurately by looking at the contents of his shopping cart The store manager would like to close the store as soon as possible, and he can only close the store once both registers are done. She has hired Dr. Dina P. Rogram to organize the checkout procesS a. (40 points) Dr. Rogram has created an algorithm that, given the ti's, assign the customers to one of the two checkout lines so that the registers close as soon as possible. The algorithm takes O(nT) time, where T is defined as T-?, t. Describe the algorithm. b. (EECS 454 only) The manager complains that Dr Rogram's algorithm is slow, but Dr. Rogram shows her that the checkout problem is NP-complete with a reduction from PARTITION. Substantiate Dr. Rogram's claim. (PARTITION: given a finite set of positive integers, is there a subset whose sum is exactly equal to one-half of the total.) c. (10 points) The store manager is still unhappy and demands that Dr. Rogram provide a faster algorithm. Help Dr. Rogram by describing a 2-approximation algorithm that takes O(n) time. d. (Extra Credit) The store manager is even more unhappy with Dr. Rogram solution and demands a 3/2 approximation algorithm that takes O(n) time. Help Dr Rogram by describing the approximation algorithm