ALSO PROVIDE A PROOF OF CORRECTNESS AND RUN-TIME ANALYSIS

You've periodically helped the medical consulting firm Doctors Without Weekends on various hospital scheduling issues, and they've just come to you with a new problem. For each of the next n days, the hospital has determined the number of doctors they want on hand; thus, on day i, they have a requirement that exactly p, doctors be present. There are k doctors, and each is asked to provide a list of days on which he or she is willing to work. Thus doctor provides a set Lf of days on which he or she is willing to work. The system produced by the consulting firm should take these lists and try to return to each doctor j a list L'_j with the following properties. (A) L'_j is a subset of L_j so that doctor j only works on days he or she finds acceptable. (B) If we consider the whole set of lists L'_1 .... L'_k, it causes exactly p_i doctors to be present on day i, for i = 1, 2.........n. (a) Describe a polynomial-time algorithm that implements this system. Specifically, give a polynomial-time algorithm that takes the numbers p_1, p_2, ..., p_n, and the lists L_1....L_k, and does one of the following two things. - Return lists L'_, L'_2, ...., L'_k satisfying properties (A) and (B); or - Report (correctly) that there is no set of lists L'_1, L'_2, ...., L'_k that satisfies both properties (A) and (B). (b) The hospital finds that the doctors tend to submit lists that are much too restrictive, and so it often happens that the system reports (correctly, but unfortunately) that no acceptable set of lists L'_1, L'_2.....L'_k exists. Thus the hospital relaxes the requirements as follows. They add a new parameter c > 0, and the system now should try to return to each doctor; a list L'_j with the following properties. (A*) I'_j contains at most c days that do not appear on the list L_f. (B) (Same as before) If we consider the whole set of lists L_j, .... L_k, it causes exactly p, doctors to be present on day i, for i= 1, 2....n. Describe a polynomial-time algorithm that implements this revised system. It should take the numbers p_1, p_2....p_n, the lists L_1...L_k, and the parameter c > 0, and do one of the following two things. - Return lists L'_j, L'_2....., L'_k satisfying properties (A*) and (B); or - Report (correctly) that there is no set of lists L'_1, .... L'_2...., L'_k that satisfies both properties (A*) and (B)