Suppose you and your friend Alanis live together with n - 2 other people at a...

 

Transcribed Image Text:

Suppose you and your friend Alanis live together with n - 2 other people at a popular "cooperative" apartment. Over the next n nights, each of you is supposed to cook dinner for the co-op exactly once, so some one cooks on each of the nights. To make things interesting, everyone has scheduling conflicts with some of the nights (e.g., exams, deadlines at work, basketball games, etc.), so deciding who should cook on which night becomes a tricky task. For concreteness, let's label the people {p1,... Pn} and the nights {d₁,..., dn}. Then for person pi, associate a set of nights S; C {d₁,..., dn} when there are not available to cook. A feasible dinner schedule is defined to be an assignment of each person in the co-op to a different night such that each person cooks on exactly one night, there is there is someone to cook on each night, and if p, cooks on night dj, then d; & S₁. (a) [10 points] Describe a bipartite graph G such that G has a perfect matching if and only if there is a feasible dinner schedule for the co-op. (b) [10 points] Your friend Alanis takes on the task of trying to construct a feasible dinner schedule. After great effort, she constructs what she claims is a feasible schedule and then heads off to work for the day. Unfortunately, when you look at the schedule she created, you notice a big problem-n-2 of the people at the co-op are assigned to different nights on which they are available (no problem there), but for the other two people p, and p,, and the other two days d and di, you discover she has accidentally assigned both p; and p; to cook on night d and no one to cook on night d. You want to fix this schedule but without having to recompute everything from scratch. Show that it is possible, using her "almost correct" schedule, to decide in only O(n²) time whether there exists a feasible dinner schedule for the co-op. If one exists, your algorithm should also provide that schedule. Prove the correctness of your solution. Suppose you and your friend Alanis live together with n - 2 other people at a popular "cooperative" apartment. Over the next n nights, each of you is supposed to cook dinner for the co-op exactly once, so some one cooks on each of the nights. To make things interesting, everyone has scheduling conflicts with some of the nights (e.g., exams, deadlines at work, basketball games, etc.), so deciding who should cook on which night becomes a tricky task. For concreteness, let's label the people {p1,... Pn} and the nights {d₁,..., dn}. Then for person pi, associate a set of nights S; C {d₁,..., dn} when there are not available to cook. A feasible dinner schedule is defined to be an assignment of each person in the co-op to a different night such that each person cooks on exactly one night, there is there is someone to cook on each night, and if p, cooks on night dj, then d; & S₁. (a) [10 points] Describe a bipartite graph G such that G has a perfect matching if and only if there is a feasible dinner schedule for the co-op. (b) [10 points] Your friend Alanis takes on the task of trying to construct a feasible dinner schedule. After great effort, she constructs what she claims is a feasible schedule and then heads off to work for the day. Unfortunately, when you look at the schedule she created, you notice a big problem-n-2 of the people at the co-op are assigned to different nights on which they are available (no problem there), but for the other two people p, and p,, and the other two days d and di, you discover she has accidentally assigned both p; and p; to cook on night d and no one to cook on night d. You want to fix this schedule but without having to recompute everything from scratch. Show that it is possible, using her "almost correct" schedule, to decide in only O(n²) time whether there exists a feasible dinner schedule for the co-op. If one exists, your algorithm should also provide that schedule. Prove the correctness of your solution.