4 Public Libraries in Saskatchewan The Small Town Public Libraries Association of Saskatchewan (STPLAS for short) has public libraries in n small towns in Saskatchewan. Patrons can request books from any one of these n libraries, to be delivered to the library closest to them. In order to provide this service, STPLAS has n drivers who move around the n towns to bring the books that have been requested. In the back of each library, there is a room with a bed that the driver can use to rest (possibly overnight if he/she arrives late and needs to sleep before continuing his/her travel). Over the course of two days (either Monday and Tuesday, or Thursday and Friday), each driver visits each of the n towns exactly once. To avoid problems, the schedule is designed so at most one driver is in any given town at any time. On Wednesday evening, the CBC announces a major snow storm that will sweep through the province on Friday. The STPLAS' managers then decides to truncate each driver's schedule: each of them will stop in one of the towns and stay in the bed in the back of its public library until the snow storm is over and the roads have been cleared. This means the driver will not visit the remaining towns on his/her schedule this time around, but that's better than that driver ending up in the ditch in the middle of nowhere (of which there is a lot in Saskatchewan). So the truncated schedule of the driver's schedule will simply consist of its original schedule up to a certain specified time on which it is in a town T. The remainder of the truncated schedule simply has the driver remain in town T. Example: suppose we have two drivers, two towns, and that the drivers have the following schedules: Driver Time 1 Time 2 Time 3 Time 4 D1 Town Ti on the road Town T2 on the road D2 on the road Town Ti on the road Town T2. The only way to choose truncated schedules would be to have the first driver remain in town T2 starting at time 3, and have the second driver remain in town Ti starting at time 2. The STPLAS' manager question to you is the following: given the schedule for each driver, find a truncated schedule where no two drivers are ever in the same town at the same time. 1. [4 marks] Show how to reduce each instance I of this problem problem into an instance I' of the stable matching problem, in order to find a set of truncated schedules. 2. (8 marks] Prove the correctness of your algorithm, by showing that the schedule obtained from your reduction does not result in two drivers being in the same town at the same time. Hint: use a proof by contradiction. 4 Public Libraries in Saskatchewan The Small Town Public Libraries Association of Saskatchewan (STPLAS for short) has public libraries in n small towns in Saskatchewan. Patrons can request books from any one of these n libraries, to be delivered to the library closest to them. In order to provide this service, STPLAS has n drivers who move around the n towns to bring the books that have been requested. In the back of each library, there is a room with a bed that the driver can use to rest (possibly overnight if he/she arrives late and needs to sleep before continuing his/her travel). Over the course of two days (either Monday and Tuesday, or Thursday and Friday), each driver visits each of the n towns exactly once. To avoid problems, the schedule is designed so at most one driver is in any given town at any time. On Wednesday evening, the CBC announces a major snow storm that will sweep through the province on Friday. The STPLAS' managers then decides to truncate each driver's schedule: each of them will stop in one of the towns and stay in the bed in the back of its public library until the snow storm is over and the roads have been cleared. This means the driver will not visit the remaining towns on his/her schedule this time around, but that's better than that driver ending up in the ditch in the middle of nowhere (of which there is a lot in Saskatchewan). So the truncated schedule of the driver's schedule will simply consist of its original schedule up to a certain specified time on which it is in a town T. The remainder of the truncated schedule simply has the driver remain in town T. Example: suppose we have two drivers, two towns, and that the drivers have the following schedules: Driver Time 1 Time 2 Time 3 Time 4 D1 Town Ti on the road Town T2 on the road D2 on the road Town Ti on the road Town T2. The only way to choose truncated schedules would be to have the first driver remain in town T2 starting at time 3, and have the second driver remain in town Ti starting at time 2. The STPLAS' manager question to you is the following: given the schedule for each driver, find a truncated schedule where no two drivers are ever in the same town at the same time. 1. [4 marks] Show how to reduce each instance I of this problem problem into an instance I' of the stable matching problem, in order to find a set of truncated schedules. 2. (8 marks] Prove the correctness of your algorithm, by showing that the schedule obtained from your reduction does not result in two drivers being in the same town at the same time. Hint: use a proof by contradiction