Karaboudjan Shipping Lines Inc. Is a shipping company that owns n .ships and pro
ID: 3636985 • Letter: K
Question
Karaboudjan Shipping Lines Inc. Is a shipping company that owns n .ships and provides service lo n ports over a period of m days. Each of its ships a schedule that says, for each of the in days. which of the ports it is currently visiting, or whether it is out at sea. You can assume that m n. Each ship visits each port for exactly one of the m days. For safety reasons, KSL. Inc. has the following strict requirements: No two ships can lie in the same port on the same day. The company wants to perform maintenance on all the ships this month, via the following scheme. They want to truncate each ship's schedule: for each ship Si, there will lie some day when it arrives In its scheduled port and simply remains there for the rest of the month for maintenance. This means that Si, will not visit the remaining ports on Its schedule that month (if any), but this is okay. So the truncation of Si's schedule will simply consist of its original schedule up to a certain specified day on which it is in a port P. The remainder of the truncated schedule simply has it remain in port P. The company's question to you is the following: given the schedule for each ship, find a truncation of each so that condition f continues to hold: no two ships are ever in the same port on the same day. Show that such a set of truncations can always lie found, and give an algorithm to find them. Example: suppose we have two ships, two ports, a four day schedule, and that the ships have the following schedules: The only way to choose truncations would lie to have the first ship remain in port P2 starting on day 3, and have the second ship remain in port P1 starting on day 2.Explanation / Answer
1. The Stable Matching problem, as discussed in class, assumes that every woman and every man has a fully ordered list of preference. In this and the next problem, we consider the situation where we have n women and n men (as before), but where a woman or man may have ties in her/his ranking. For instance, woman w1 might like man m3 best, followed by m1 and m4 in no particular order (that is, she does not prefer m1 to m4, or m4 to m1), followed by m2. In this case, we will say that w1 is indi?erent between m1 and m4. It is of course possible for a woman or a man to be indi?erent between more than two people. A strong instability in a perfect matching consists of a woman w and a man m such that w and m both prefer each other to their current partner. Does there always exist a perfect matching with no strong instability? Either give an algorithm that ?nds such a matching and prove the correctness of your algorithm, or give an example where every perfect matching has a strong instability. [8] 2. Continuing with the same setup as in the previous question, let us de?ne a weak instability as a woman w with partner m and a man m' with a partner w ' , where either • m prefers w ' to w and w ' either prefers m to m' or is indi?erent between these two choices, or • w ' prefers m to m' and m either prefers w ' to w or is indi?erent between these two choices. Does there always exist a perfect matching with no weak instability? Either give an algorithm that ?nds such a matching and prove the correctness of your algorithm, or give an example where every perfect matching has a weak instability. [8] 3. Karaboudjan Shipping Lines Inc. is a shipping company that owns n ships and provides service to n ports over a period of m days. Each of its ships has a schedule that says, for each of the m days, which of the ports it is currently visiting, or whether it is out at sea. You can assume that m = n. Each ship visits each port for exactly one of the m days. For safety reasons, KSL Inc. has the following strict requirements: † No two ships can be in the same port on the same day. The company wants to perform maintenance on all the ships this month, via the following scheme. They want to truncate each ship’s schedule: for each ship Si , there will be some day when it arrives in its scheduled port and simply remains there for the rest of the month for maintenance. This means that Si will not visit the remaining ports on its schedule that month (if any), but this is okay. So the truncation of Si ’s schedule will simply consist of its original schedule up to a certain speci?ed day on which it is in a port P. The remainder of the truncated schedule simply has it remain in port P. The company’s question to you is the following: given the schedule for each ship, ?nd a truncation of each so that condition † continues to hold: no two ships are ever in the same port on the same day. Show that such a set of truncations can always be found, and give an algorithm to ?nd them. 1Example: suppose we have two ships, two ports, a four day schedule, and that the ships have the following schedules: Ship Day 1 Day 2 Day 3 Day 4 S1 port P1 at sea port P2 at sea S2 at sea port P1 at sea port P2. The only way to choose truncations would be to have the ?rst ship remain in port P2 starting on day 3, and have the second ship remain in port P1 starting on day 2. [8] 4. There is a class of folk songs and holiday songs in which each verse consists of the previous verse, with one extra line added on. “The twelve days of Christmas” has this property; for example, when you get to the ?fth verse, you sing about the ?ve golden rings and then, reprising the lines from the fourth verse, also cover the four calling birds, etc. all the way to the partridge in the pear tree. The Aramaic song “Had gadya” from the Passover Haggadah and the French song “Y’a qu’un cheveu sur la tˆete `a Mathieu” work like this as well, as do many other songs. These songs tend to last a long time, despite having relatively short scripts. In particular, you can convey the words plus instructions for one of these songs by specifying just the new line that is added in each verse, without having to write out all the previous lines each time. So the phrase “?ve golden rings” only has to be written once, even though it will appear in verses ?ve and onward. There is something asymptotic that can be analyzed here. Suppose, for concreteness, that each line has a length that is bounded by a constant number of words c, and suppose that the song, when sung out loud, runs for n words total. Show how to encode such a song using a script that has length in O(f), for a function f(n) that grows as slowly as possible. You should specify what the function f(n) is, and prove that your encoding’s length is in
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.