• ¿Documento equivocado? Cámbialo gratis
  • Escrito por estudiantes que aprobaron
  • Inmediatamente disponible después del pago
  • Leer en línea o como PDF
Vender
¿Dónde estudias?
Tu idioma
Document preview thumbnail
Vista previa 4 fuera de 356 páginas
Examen

Algorithm Design (Kleinberg & Tardos) Complete Solutions Manual PDF | Algorithm Design 2005 | All Chapters Solutions Guide

Document preview thumbnail
Vista previa 4 fuera de 356 páginas

Master algorithm analysis and problem-solving techniques with this comprehensive Algorithm Design Solutions Manual for the renowned textbook by Jon Kleinberg and Éva Tardos (2005). This study resource is designed to help computer science students strengthen their understanding of algorithmic design, computational problem solving, complexity analysis, and advanced programming concepts. Ideal for undergraduate and graduate students studying computer science, software engineering, data structures, algorithms, and technical interview preparation. This resource provides extensive support for coursework, homework practice, examinations, assignments, and academic review.

Vista previa del contenido

, Algorithm Design Solutions Manual By Jon Kleinberg Eva Tardo
1 Stable Matching
Note: Exercises denoted with an asteris∗ k ( ) tend to be more difficult, or to rely on some of the more advanced material.

1. Gale and Shapley published their paper on the stable marriage 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.

• First type of instability: There are students s anr d s , and a hospital h, so that

– s is assigned to h, and
– sr is assigned to no hospital, and
– h prefers sr to s.
r r
• Second type of instability: There are students s and s , and hospitals h and h ,
so that

– s is assigned to h, and
– sr is assigned to hr, and
– h prefers sr to s, and
– sr prefers h to hr.

So we basically have the stable marriage problem from class, except that (i) hospitals generally want more than one
resident, and (ii) there is a surplus of medical students.

Show that there is always a stable assignment of students to hospitals, and give an efficient algorithm to find one. The
input size is Θ(mn); ideally, you would like to find an algorithm with this running time.

2

, Solution. The algorithm is very similar to the one from class. At any point in time, a student is either
“committed” to a hospital or “free.” A hospital either has available positions, or it is “full.” The algorithm is the
following:
While some hospital hi has available positions hi offers a position to the next student sj on its
preference list if sj is free then sj accepts the offer else (sj is already committed to a hospital hk) if
sj prefers hk to hi then sj remains committed to hk else sj becomes committed to hi the number of
available positions at hk increases by one. the number of available positions at hi decreases by one.

The algorithm terminates in O(mn) steps because each hospital offers a positions to a student at most once, and
in each iteration, some hospital offers a position to some student.
Suppose there are pi > 0 positions available at hospital hi. The algorithm terminates with an assignment in which
all available positions are filled, because any hospital that did not fill all its positions must have offered one to every
student; but then, all these students would be committed to some hospital, wΣh i c h contradicts our assumption that
i= pi < n.
m
1

Finally, we want to argue that the assignment is stable. For the first kind of instability, suppose there are students
s and sr, and a hospital h as above. If h prefers sr to s, then h would have offered a position to sr before it offered
one to s; from then on, sr would have a position at some hospital, and hence would not be free at the end — a
contradiction.

For the second kind of instability, suppose that (hi, sj) is a pair that causes instability. Then hi must have offered a
position to sj, for otherwise it has pi residents all of whom it prefers to sj. Moreover, sj must have rejected hi in
favor of some hk which he/she preferred; and sj must therefore be committed to some hl (possibly different from hk)
which he/she also prefers to hi.

2. We can think about a different generalization of the stable matching problem, in which certain man-woman pairs are
explicitly forbidden. In the case of employers and ap- plicants, picture that certain applicants simply lack the necessary
qualifications or degree; and so they cannot be employed at certain companies, however desirable they may seem.
Concretely, we have a set M of n men, a set W of n women, and a set F ⊆ M × W of pairs who are simply
not allowed to get married. Each man m ranks all the women w for which (m, w) /∈ F , and each woman wr ranks
all the men mr for which (mr, wr) /∈ F .

In this more general setting, we say that a matching S is stable if it does not exhibit any of the following types of
instability.

(i) There are two pairs (m, w) and (mr, wr) in S with the property that m prefers wr
to w, and wr prefers m to mr. (The usual kind of instability.)

(ii) There is a pair (m, w∈) S, and a man mr, so that mr is not part of any pair in the
matching,/∈(mr, w) F , and w prefers mr to m. (A single man is

, 3

Información del documento

Subido en
28 de octubre de 2026
Número de páginas
356
Escrito en
2026/2027
Tipo
Examen
Contiene
Preguntas y respuestas
$19.99

¿Documento equivocado? Cámbialo gratis Dentro de los 14 días posteriores a la compra y antes de descargarlo, puedes elegir otro documento. Puedes gastar el importe de nuevo.
Escrito por estudiantes que aprobaron
Inmediatamente disponible después del pago
Leer en línea o como PDF

Seller avatar
Los indicadores de reputación están sujetos a la cantidad de artículos vendidos por una tarifa y las reseñas que ha recibido por esos documentos. Hay tres niveles: Bronce, Plata y Oro. Cuanto mayor reputación, más podrás confiar en la calidad del trabajo del vendedor.
DocuPrep
4.3
(3)
Vendido
29
Seguidores
0
Artículos
1499
Última venta
5 días hace



Por qué los estudiantes eligen Stuvia

Creado por compañeros estudiantes, verificado por reseñas

Calidad en la que puedes confiar: escrito por estudiantes que aprobaron y evaluado por otros que han usado estos resúmenes.

¿No estás satisfecho? Elige otro documento

¡No te preocupes! Puedes elegir directamente otro documento que se ajuste mejor a lo que buscas.

Paga como quieras, empieza a estudiar al instante

Sin suscripción, sin compromisos. Paga como estés acostumbrado con tarjeta de crédito y descarga tu documento PDF inmediatamente.

Student with book image

“Comprado, descargado y aprobado. Así de fácil puede ser.”

Alisha Student

Preguntas frecuentes