Homework1_Solutions

pdf

School

University of Texas *

*We aren’t endorsed by this school

Course

360C

Subject

Computer Science

Date

Dec 6, 2023

Type

pdf

Pages

Uploaded by ConstableGiraffeMaster829

ECE360C: Algorithms Homework Assignment #1 University of Texas at Austin Due: September 1, 2023 (11:59pm) Homework Assignment #1 – Solutions Solutions are for individual use only by students registered for ECE 360C in Spring 2023 semester. They should not be otherwise shared or posted. Problem 1: Remember [20 points] Answer the following true/false questions about the Gale-Shapley algorithm. (We are using the version of Gale-Shapley described in class where n positions are offered to n applicants. The positions do the offering, and applicants simply accept the best offer they are made.) True False ⊠ □ Every execution of the Gale-Shapley algorithm results in a stable matching of positions to applicants. □ ⊠ In any execution of the Gale-Shapley algorithm, every applicant will end up with their least favored position. ⊠ □ During the execution of the Gale-Shapley algorithm, once an applicant has been offered a position, they will always have some position. □ ⊠ During the execution of the Gale-Shapley algorithm, once a position has been offered to at least one applicant, the position will always be matched to some applicant. □ ⊠ Depending on the preference lists and the order in which offers are made, it is possible for some position to end up without a matched applicant. ⊠ □ If an applicant and a position rank each other first, they are guaranteed to be matched by Gale-Shapley at the end of the algorithm. □ ⊠ In some cases, even when the inputs to the algorithm are properly formed, the Gale-Shapley algorithm could get into an infinite loop of applicants and positions matching, then breaking the match, then matching again. ⊠ □ The sequence of offers an applicant accepts is always improving (that is, an applicant never has to give up a good position for one the applicant ranks lower). ⊠ □ If a position x makes an offer to applicant b after having made an offer to applicant a earlier in the algorithm, it must be true that x ranks a higher than b . □ ⊠ The number of unfilled positions decreases by one for every iteration of the Gale-Shapley while loop.

Homework Assignment #1: September 1, 2023 (11:59pm) 2 Problem 2: Understand [20 points] In our discussion of the Gale-Shapley algorithm, we used the number of offers as a measure of progress and showed that each iteration of the while loop makes one new offer of a position to an applicant. Since there are n applicants and n positions, and an applicant can never be offered a position more than once, the while loop can be executed at most n 2 times. Consider a simple instance of Gale-Shapley, where n = 3 (there are 3 open positions, A , B , and C and 3 applicants X , Y , and Z ). Provide an example execution of Gale-Shapley that results in the maximum possible number of offers made (i.e., executions of the while loop). You will need to provide the complete preference list of all three positions and all three applicants as well as the order in which positions are offered to applicants. Also state whether your free list is a LIFO queue or a FIFO queue (that is, is a position that becomes open because an applicant took a better offer immediately offered their next favored applicant or do they go to the back of the line?). Finally, summarize at least three generic observations this exercise helps you make about the Gale-Shapley algorithm’s execution. We’ve done the first one for you. Positions’ Preference Lists A: X Y Z (given) B: Y X Z C: X Y Z Applicants’ Preference Lists X: B C A Y: C A B Z: A B C Type of Queue FIFO Initial Queue Order (include A, B, and C) A, B, C How many offers are made, in total? 7 Three Generic Observations (don’t refer to n = 3 or to specific applicants or positions) 1. It is not possible for all n positions to be offered to all n applicants. 2. There will always be at least one applicant who only receives one offer. 3. Regardless of the order in which offers are made, for a given set of preferences lists, the same offers are always made.

Homework Assignment #1: September 1, 2023 (11:59pm) 3 Problem 3: Apply [20 points] Read about this real world application of a Gale-Shapley-like algorithm: https://nyti.ms/3EevfRv Identify three similarities and three differences between the classic Gale-Shapley algorithm and the version described in the article. Two Similarities 1. The goal is the same – match two types of parties with the other based on preferences. 2. Both parties rank the other, and each individual has the option to rank based on their own preferences. Two Differences 1. There aren’t necessarily the same number of students and slots available. At least it doesn’t appear to be explicitly the case. 2. The applicants (and positions) don’t have to rank all of the other party Based on your knowledge of Gale-Shapley and your reading of this article, do you have any concerns or questions about how the matching algorithm works in this context? If so, write them here. If not, write “No concerns or questions.” (Finish this part of the question before moving on. It will be more interesting for you and for us.) My Questions and Concerns Lots of things are fine here. Now read these two additional articles about the process (note the dates on all three articles): https://nyti.ms/3KTO14w https://bit.ly/NYCPart3 If you have any trouble accessing these articles, please let us know ASAP.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Homework Assignment #1: September 1, 2023 (11:59pm) 4 In your own words, write a paragraph explaining the pitfalls of relying on the match algorithm to determine high school admissions in New York City. You might consider the following questions (but you can come up with your own instead if you prefer): what makes the algorithm equitable or inequitable? How have “tweaks” to the classic Gale-Shapley algorithm influenced the outcome of the algorithm? What aspects of public schooling are “hidden” by the algorithm? Pitfalls There are a variety of things here that are “correct”. Some examples: students don’t have to rank all schools and vice versa. There might not be the same number of spaces and schools. As a result of these, some of the students remain unmatched (and positions remain unfilled). For things that are hidden: it’s not clear how specialized schools are handled (if a program is an arts magnet, how are auditions handled?). It can be a hardship for all students to get to schools across the city, from a transportation perspective. Etc. Finally, suggest at least one concrete change that you would want to investigate making to the New York City admissions process. You cannot entirely throw out the matching algorithm, so the change has to be made in the context of continuing with something Gale-Shapley-like. In developing your idea (which doesn’t have to be formally written or evaluated), find at least one additional resource (e.g., what have other school districts done, how is this working in NYC (the NYC department of education’s website has some informative videos), etc.) and include that resource in your response. An Idea to Try Again, there are a lot of possibilities for a “correct” response here. This is just one exam- ple. Each high school could have a restriction that only a particular fraction of their stu- dents can come from the same middle school. It would take some time and care to make this work within the algorithm in terms of how to implement it to ensure that the algorithm is still deterministic and halts. As far as a reference goes, this was inspired by information on the NYC DEO webpage (https://www.schools.nyc.gov/enrollment/enroll-grade-by-grade/how- students-get-offers-to-doe-public-schools) – in the current system, seats are reserved for students with disabilities, so possibly this could be implemented similarly.

Homework Assignment #1: September 1, 2023 (11:59pm) 5 Problem 4: Analyze [20 points] In order to execute an implementation of the Gale-Shapley algorithm, one must provide it inputs. State, completely, what input is required for Gale-Shapley to execute. Then write an expression using n (the number of open positions and available applicants) and s (the size in bits of an integer in a machine representation) to capture the size (in bits) of the input provided to the algorithm to run. (Hint: you can assume, for simplicity, that each applicant and each position can be represented by a single integer.) The input to Gale-Shapley (GS) consists of n preference lists from applicants and n preference list from positions. Each preference list ranks all n of the opposite group, and each member of each group is represented by a single integer. So the bits required for one preference list is ns . Since there are n applicant preference list, the total size for these is n 2 s . The same is true for the positions’ preference lists, giving a total of 2 n 2 s . Examine the pseudocode for the Gale-Shapley algorithm provided in the textbook or in lecture. Describe a set of data structures you would use to fully implement the algorithm. Again using n and s , write an expression for the size of the representation required to run the algorithm. • We keep a queue of open positions. For simplicity, we can implement our queue as an array of integers indicating the “name” of the open positions. The size of this queue is then ns . • We have to maintain the preference lists given as input, so that’s 2 n 2 s . [note: it’s ok not to explicitly include this since it was included above.] • We also need to keep the to arrays of matches, each of which is n long, each entry holding an integer, so this is 2 ns in total. • In total, these data structures require 2 n 2 s + 3 ns bits.

Homework Assignment #1: September 1, 2023 (11:59pm) 6 Problem 5: Evaluate [20 points] Consider a variation of the Stable Matching problem where we have a set P of n positions and a set A of n applicants being considered for the positions. In this case, each position and each applicant are not required to give each of their possible matches a distinct ranking, i.e., their preference lists may include ties. When we have ties like this, we say that p strictly prefers a ′ to a to mean that a ′ is ranked strictly higher than a , (in other words a ′ is not ranked lower than or tied with a ). In this problem, an instability in a matching S occurs if: There are two pairs ( p, a ) and ( p ′ , a ′ ) in S such that p strictly prefers a ′ to a , and a ′ strictly prefers p to p ′ . Prove that a stable matching always exists for any set of preference lists (even with possible ties). (Hint: first come up with a way to run Gale-Shapley on these preference lists with ties, then prove that the resulting matching is stable.) We can break the ties in any fashion (so just arbitrarily). Then we run the regular Gale- Shapley algorithm on the resulting preference lists. The result has no instability for applicants and positions based on strict preferences. This follows directly from the proof of Gale-Shapley correctness – any stability of the form described above whould also be an instability in “ordi- nary” Gale-Shapley, which has been proven (in class) to not have any instabilities. Now consider another different definition of instability, still in the case where there can be ties in the preference list. An instability in a matching S occurs if: There are two pairs ( p, a ) and ( p ′ , a ′ ) in S such that p prefers a ′ at least as much as a , and a ′ prefers p at least as much as p ′ . Give a counterexample to show a stable matching does not always exist. Let n = 2 and p 1 , p 2 be the two positions, a 1 , a 2 be the two applicants. Let p 1 be indifferent between a 1 and a 2 and let both applicants prefer p 1 to p 2 . The choices of p 2 are insignificant. There is no matching without this type of stability in this case, since, regardless of who was mached with p 1 , the other applicant together with p 1 would form an instability.

Your preview ends here

Eager to read complete document? Join bartleby learn and gain access to the full version

Access to all documents
Unlimited textbook solutions
24/7 expert homework help

Homework Assignment #1: September 1, 2023 (11:59pm) 7 Problem 6: Create [20 points] Consider a shipping company that owns n ships and provides services to n ports. Each of its ships has a schedule that says, on each day of the month, which of the ports it is currently visiting, or whether it is out to 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, the company has the following strict requirement: ( † ) 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 S i , there will be some day when it arrives in its scheduled port and simply remains there for the rest of the month. This means that S i will not visit the remaining ports on its schedule (if any) that month. The truncation of S i ’s schedule will consist of its original schedule up to a certain specified date on which it is in a port P ; the remainder of the truncated schedule simply has it remain in port P . Now the challenge: given the schedule for each ship, find 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 truncation 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 that the first ship’s schedule is: port P 1 ; at sea; port P 2 ; at sea and the second ship’s schedule is: at sea; port P 1 ; at sea; port P 2 Then the (only) way to choose truncations would be to have the first ship remain in port P 2 starting on day 3 and have the second ship remain in port P 1 , starting on day 2. For each schedule, we have to choose a stopping port : the port in which the ship will spend the rest of the month. Implicitly, these stopping ports will define truncations of the schedules. We will say that an assignment of ships to stopping ports is acceptable if the resulting trunca- tions satisfy the conditions of the problem—specifically, condition ( † ). (Note that because of condition ( † ), each ship must have a distinct stopping port in any acceptable assignment. We set up a stable matching problem involving ships and ports. Each ship ranks each port in chronological order of its visits to them. Each port ranks each ship in reverse chronological order of their visits to it. Now we simply have to show: A stable matching between ships and ports defines an acceptable assignment of stop- ping ports. Proof. If the assignment is not acceptable, then it violates condition ( † ). That is, some ship S i passes through port P k after ship S j has already stopped there. But in this case, under our preference relation above, ship S i “prefers” P k to its actual stopping port, and port P k “prefers” ship S i to ship S j . This contradicts the assumption that we chose a stable matching between ships and ports.

Homework1_Solutions

Related Documents