Shutter Talk's office space has a shared kitchen facility. Unfortunately, it's early days, and there is...

 

Transcribed Image Text:

Shutter Talk's office space has a shared kitchen facility. Unfortunately, it's early days, and there is not yet sufficient funding to hire staff responsible for keeping the kitchen cleaned up. Therefore, the first task for the newbie (that's you!) is to design an algorithm to assign each of the n members of Shutter Talk's technical staff into a kitchen patrol rotation. Specifically, your job is to create an n day rotation for the days {d, d2,..., dn} in which each staff member is responsible for kitchen patrol exactly once. There's a wrinkle, of course; a given staff member is not available every day, either because of vacation or because of important technical deadlines. That is, for each member of the staff, {81, 82,...,sn}, there is a subset of the days when the staff member is not available for kitchen patrol. You have these "vacation" days accessible to you before starting your algorithm. A feasible schedule is an assignment of each member of the staff to perform kitchen patrol on one of the n days such that the staff member is available on the scheduled day. (a) [15 points] Describe a polynomial time algorithm that determines whether such a feasible schedule is possible and, if it is, outputs the schedule. (b) [5 points] Give an asymptotically tight upper bound on the runtime of your algorithm. Briefly explain. Shutter Talk's office space has a shared kitchen facility. Unfortunately, it's early days, and there is not yet sufficient funding to hire staff responsible for keeping the kitchen cleaned up. Therefore, the first task for the newbie (that's you!) is to design an algorithm to assign each of the n members of Shutter Talk's technical staff into a kitchen patrol rotation. Specifically, your job is to create an n day rotation for the days {d, d2,..., dn} in which each staff member is responsible for kitchen patrol exactly once. There's a wrinkle, of course; a given staff member is not available every day, either because of vacation or because of important technical deadlines. That is, for each member of the staff, {81, 82,...,sn}, there is a subset of the days when the staff member is not available for kitchen patrol. You have these "vacation" days accessible to you before starting your algorithm. A feasible schedule is an assignment of each member of the staff to perform kitchen patrol on one of the n days such that the staff member is available on the scheduled day. (a) [15 points] Describe a polynomial time algorithm that determines whether such a feasible schedule is possible and, if it is, outputs the schedule. (b) [5 points] Give an asymptotically tight upper bound on the runtime of your algorithm. Briefly explain.