算法代写 | CS270 Homework #1

这个作业是完成几个算法证明题
CS270 Homework #1

Problem 1. (15 points)
In this problem, we will consider what happens in stable matching when we are guaranteed additional structure on the preferences.
(a) [5 points]. Suppose that among the n ≥ 2 men, there are two men m, m! such that every
woman prefers m to m!
. Prove that for every stable matching, m prefers his assigned partner to
the assigned partner of m!
.
(b) [10 points]. Suppose that all women have the exact same preference ranking.1 Prove that
there is now a unique stable matching, and describe this matching in words.
Hint: There is a simpler algorithm than Gale-Shapley for computing the unique stable matching
in this special case. Thinking about what that algorithm might be should guide you to the proof.
1As a motivation, consider a setting in which each student simply ranks universities by the US News and World
Report ranking.
2
Problem 2. (25 points)
After graduating from USC, you go on to be the CEO of the successful software engineering firm
WorkTogether. Over time, you realize that your employees are most productive when they work in
pairs, and when the teams satisfy a certain “stability” condition. Formally, you have 2n employees
(i.e., an even number), and each employee comes to you with an ordered list of the 2n−1 remaining
employees in decreasing order of preference. You would like to pair up your employees to form a
set M of n disjoint teams, with two employees per team, so that M is stable in the following sense:
for every pair i and j of employees who are not partners in M, it is not the case that both i prefers
j to his/her partner in M and j prefers i to his/her partner in M. This reminds you of the stable
matching problem we described in class, and you wonder whether you can similarly compute a
stable team assignment M.
(a) [5 points]. It turns out that, unlike in the stable marriage problem, a stable team assignment
is not guaranteed to exist. Exhibit an example in which a stable team assignment does not exist.
You will only need n = 2 — i.e., 4 employees. What is the main difference between the stable team
assignment problem and the stable marriage problem which explains this discrepancy?
(b) [10 points]. While a solution may not exist in general for stable team assignment, for certain
more structured instances, one can guarantee the existence. Suppose that for each pair i, j of
employees, there is a number (say, an integer) ai,j that describes how much i and j would like each
other as teammate.2 Importantly, we assume that this feeling is always reciprocated, so ai,j = aj,i
for all pairs i #= j. To avoid unnecessary tie breaking concerns, we also assume that all ai,j are
distinct numbers. Now, each employee i simply orders all other employees j by decreasing ai,j to
obtain his/her ranking.
Prove that in this special case, a stable team assignment always exists. Also prove that it is
unique — i.e., there is exactly one stable team assignment.
[Hint: Your proof of existence may take the form of an algorithm which constructs a stable team
assignment. The runtime of this algorithm is not important, since we are only asking you to prove
existence and uniqueness.]
(c) [10 points]. The problem described in (b) becomes algorithmically easier when the ai,j values
are even more structured. Here is one way to model this. Suppose that each employee i has
one number pi that describes, for instance, how many lines of comments the employee leaves per
line of code. We assume that no two pairs i, j and i
!
, j! are at exactly the same distance, i.e.,
|pi −pj | =# |pi! −pj!| for all {i, j} =# {i
!
, j!
}. Each employee prefers working with more similar others
— formally, each employee i ranks the other employees by decreasing distance from himself/herself.
Show that you can compute the unique stable team assignment in time O(n log n) when the
instance is represented as a set of 2n such points p1,…,p2n ∈ R, one per employee.
[Hint: You will need to sort the points. Moreover, though not absolutely necessary, you might find
it convenient to use a queue and/or heap data structure.]
2For example, these numbers could be derived from similarity along a few important attributes, such as work
style, work hours, number of comments left, and so on.
3
Problem 3. (15 points)
You would like to introduce yourself to all of the CPs in CSCI 270, which requires you to drop
in all of their Zoom office hours. Let’s say that there are n CPs, and for each, you are given one
interval [si, fi] when they hold office hours.3 The real time sink is not so much actually talking to
the CP — we assume that that is instantaneous. The time sink is logging into Zoom with USC’s
two-factor authentication system. As you know, the Internet is quite unreliable, so whenever you
log in, you immediately manage to meet everyone, but are then disconnected. More precisely, if you
decide to log in at 10:00am, you manage to meet all the CPs whose office hours include 10:00am,
but no others (not even someone whose office hours start at 10:01am).
You would like to find a smallest (minimum-cardinality) set of times to log into Zoom such that
those logins together hit every CP’s office hour interval. Give (and of course analyze) an algorithm
that runs in time O(n log n) and finds a smallest set of times to log in and meet all the CPs.
3We disregard the possibility of one person having multiple separate office hour times, like holding office hours
from 10:00-11:00 and then again from 2:00-3:00.