- 797 step-by-step solutions
- Solved by professors & experts
- iOS, Android, & web

- Question : 1E - Decide whether you think the following statement is true or false. If it is true, give a short explanation. If it is false, give a counterexample. True or faLse? In every instance of the Stable Matching Problem, there is a stable matching containing a pair (m, w) such that m is ranked first on the preference list of w and w is ranked first on the preference list of m
- Question : 2E - Decide whether you think the following statement is true or false. If it is true, give a short explanation. If it is false, give a counterexample. True or faLse? Consider an instance of the Stable Matching Problem in which there exists a man m and a woman w such that m is ranked first on the preference list of w and w is ranked first on the preference list of m. Then in every stable matching S for this instance, the pair (m, w) belongs to S.
- Question : 3E - here are many other settings in which we can ask questions related to some type of "stability" principle. Here's one, involving competition between two enterprises. Suppose we have two television networks, whom we'll call A and '.B. There are n prime-time programming slots, and each network has n TV shows. Each network wants to devise a schedule-an assignment of each show to a distinct slot-so as to attract as much market share as possible. Here is the way we determine how well the two networks perform relative to each other, given their schedules. Each show has a fixed rating, which is based on the number of people who watched it last year; we'll assume that no two shows have exactly the same rating. Anetwork wins a given time slot if the show that it schedules for the time slot has a larger rating than the show the other network schedules for that time slot. The goal of each network is to win as many time slots as possible. Suppose in the opening week of the fall season, Network A reveals a scheduleS and Network '.B reveals a schedule T. On the basis of this pair of schedules, each network wins certain time slots, according to the rule above. We'll say that the pair of schedules (S, T) is stable ifneither network can unilaterally change its own schedule and win more time slots. That is, there is no scheduleS' such that Network A wins more slots with the pair (S', T) than it did with the pair (S, T); and symmetrically, there is no schedule T' such that Network '.B wins more slots with the pair (S, T') than it did with the pair (S, T). The analogue of Gale and Shapley's question for this kind of stability is the following: For every set of TV shows and ratings, is there always a stable pair of schedules? Resolve this question by doing one of the following two things: (a) give an algorithm that, for any set of TV shows and associated ratings, produces a stable pair of schedules; or (b) give an example of a set of TV shows and associated ratings for which there is no stable pair of schedules.
- Question : 4E - Gale and Shapley published their paper on the Stable Matching Problem in 1962; but a version of their algorithm had already been in use for ten years by the National Resident Matching Program, for the problem of assigning medical residents to hospitals. Basically, the situation was the following. There were m hospitals, each with a certain number of available positions for hiring residents. There were n medical students graduating in a given year, each interested in joining one of the hospitals. Each hospital had a ranking of the students in order of preference, and each student had a ranking of the hospitals in order of preference. We will assume that there were more students graduating than there were slots available in the m hospitals. The interest, naturally, was in finding a way of assigning each student to at most one hospital, in such a way that all available positions in all hospitals were filled. (Since we are assuming a surplus of students, there would be some students who do not get assigned to any hospital.) We say that an assignment of students to hospitals is stable if neither of the following situations arises.
- Question : 5E - The Stable Matching Problem, as discussed in the text, assumes that all men and women have a fully ordered list of preferences. In this problem we will consider a version of the problemin which men and women can be indifferent between certain options. As before we have a set M of n men and a set W of n women. Assume each man and each woman ranks the members of the opposite gender, but now we allow ties in the ranking. For example (with n = 4), a woman could say that m1 is ranked in first place; second place is a tie between m2 and m3 (she has no preference between them); and m4 is in last place. We will say that w prefers m to m' if m is ranked higher than m' on her preference list (they are not tied). With indifferences in the rankings, there could be two natural notions for stability. And for each, we can ask about the existence of stable matchings, as follows. (a) A strong instability in a perfect matching S consists of a man m and a woman w, such that each of m and w prefers the other to their partner in S. Does there always exist a perfect matching with no strong instability? Either give an example of a set of men and women with preference lists for which every perfect matching has a strong instability; or give an algorithm that is guaranteed to find a perfect matching with no strong instability. (b) A weak instability in a perfect matching s consists of a man m and a woman w, such that their partners in S are w' and m', respectively, and one of the following holds: - m prefers w to w', and w either prefers m to m' or is indifferent between these two choices; or - w prefers m tom', and m either prefers w tow' or is indifferent between these two choices. In other words, the pairing between m and w is either preferred by both, or preferred by one while the other is indifferent. Does there always exist a perfect matching with no weak instability? Either give an example of a set of men and women with preference lists for which every perfect matching has a weak instability; or give an algorithm that is guaranteed to find a perfect matching with no weak instability.
- Question : 6E - Peripatetic Shipping lines, Inc., is a shipping company that owns n ships and provides service to n ports. Each of its ships has a schedule that says, for each day of the month, which of the ports it's currently visiting, or whether it's out at sea. (You can assume the "month" here has m days, for some m > n.) Each ship visits each port for exactly one day during the month. For safety reasons, PSL Inc. has the following strict requirement: (t) 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 (if any) that month, but this is okay. So the truncation of S/s schedule will siJ:nply 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. Now the company's question to you is the following: Given the schedule for each ship, find a truncation of each so that condition (t) 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 find them. Example. Suppose we have two ships and two ports, and the "month" has four days. Suppose the first ship's schedule is port P1; at sea; port P2; at sea and the second ship's schedule is at sea; port P1; at sea; port P2 . Then the (only) way to choose truncations would be 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.
- Question : 7E - Some of your friends are working for CluNet, a builder of large communication networks, and they are looking at algorithms for switching in a particular type of input/output crossbar. Here is the setup. There are n input wires and n output wires, each directed from a source to a terminus. Each input wire meets each output Vlrire in exactly one distinct point, at a special piece of hardware called a junction box. Points on the wire are naturally ordered in the direction from source to terminus; for two distinct points x and y on the same w:ire, we say that x is upstream from y if x is closer to the source than y, and otherwise we say x is downstream from y. The order in which one input wire meets the output '"'riTes is not necessarily the same as the order in which another input 'we meets the output wires. (And similarly for the orders in which output wires meet input wires.) Figure 1.8 gives an example of such a collection of input and output wires. Now, here's the switching component of this situation. Each input wire is carrying a distinct data stream, and this data stream must be switched onto one of the output Vlrires. If the stream of Input i is switched onto Output j, at junction box B, then this stream passes through all junction boxes upstream from B on Input i, then through B, then through all junction boxes downstream from B on Output j. It does not matter which input data stream gets switched onto which output wire, but each input data stream must be switched onto a different output wire. Furthermore-and this is the tricky constraint-no two data streams can pass through the same junction box following the switching operation. Finally, here's the problem. Show that for any specified pattern in which the input wires and output wires meet each other (each pair meeting exactly once), a valid switching of the data streams can always be found-one in which each input data stream is switched onto a different output, and no two of the resulting streams pass through the same junction box. Additionally, give an algorithm to find such a valid switching. ;1f : : : Junction Output 1 l--f'----~.------::;;1------~cmeets Input 2 : before Input 1) Output 2 l---~-7~----~.-------~cmeellimput2 Junction Junction ', before Input 1) . . . . . ' 0 Input 1 Input 2 (meets Output 2 (meets Output 1 before Output 1) before Output 2) Figure 1.8 An example with two input wires and two output wires. mput 1 has its junction with Output 2 upstream from its junction with Output 1; mput 2 has its junction with Output 1 upstream from its junction with Output 2. A valid solution is to switch the data stream of mput 1 onto Output 2, and the data stream of mput 2 onto Output 1. On the other hand, if the stream of mput 1 were switched onto Output 1, and the stream of mput 2 were switched onto Output 2, then both streams would pass through the junction box at the meeting of mput 1 and Output 2-and this is not allowed.
- Question : 8E - For this problem, we will explore the issue of truthfulness in the Stable Matching Problem and specifically in the Gale-Shapley algorithm. The basic question is: Can a man or a woman end up better off by lying about his or her preferences? More concretely, we suppose each participant has a true preference order. Now consider a woman w. Suppose w prefers man m tom', but both m and m' are low on her list of preferences. Can it be the case that by switching the order of m and m' on her list of preferences (i.e., by falsely claiming that she prefers m' to m) and running the algorithm with this false preference list, w will end up with a man m" that she truly prefers to both m and m'? (We can ask the same question for men, but will focus on the case of women for purposes of this question.) Resolve this question by doing one of the following two things: (a) Give a proof that, for any set of preference lists, switching the order of a pair on the list cannot improve a woman's partner in the Gale Shapley algorithm; or (b) Give an example of a set of preference lists for which there is a switch that 'Would improve the partner of a woman who switched preferences.

4out of 5Eduard InzhirovAlgorithm Design Algorithm Design Solutions Manual is an interesting book. My concepts were clear after reading this book. All fundamentals are deeply explained with examples. I highly recommend this book to all students for step by step textbook solutions.

4out of 5GowthamI am a student at Harvard University and I read Algorithm Design Algorithm Design Solutions Manual and attempted crazy for study textbook solutions manuals which helped me a lot. Thanks a lot.

4out of 5IrisI am a student of college. My experience of textbook solutions with them was superb. They have a collection of almost all the necessary books and the Algorithm Design Algorithm Design Solutions Manual helped me a lot.

4out of 5Amanda LiangExcellent service when it comes to textbook solutions. The Algorithm Design Algorithm Design Solutions Manual. which I was looking for so long finally landed me here. My experience with crazy for the study was pretty good.

4out of 5Dewi Syaroh AlamI read Algorithm Design 1st Edition Solutions Manual and it helped me in solving all my questions which were not possible from somewhere else. I searched a lot and finally got this textbook solutions. I would prefer all to take help from this book.

5out of 5Doaa Abdo HassanAlgorithm Design 1st Edition Solutions Manual is an interesting book. My concepts were clear after reading this book. All fundamentals are deeply explained with examples. I highly recommend this book to all students for step by step textbook solutions.

5out of 5Janet SmithAlgorithm Design, 1st Edition - Text Book Solutions, with the ISBN No. of 9780321295354, is one of the best services I have achieved. If I had gone to some other service, I would have had to get the whole manual for a lot of money and then look for the solution. However, at CFS, I can simply get separate textbook solutions and pay exactly for what I want.