# 算法代写 | 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.