• :00Days
• :00Hours
• :00Mins
• 00Seconds
A new era for learning is coming soon Suggested languages for you:

Europe

Answers without the blur. Sign up and see all textbooks for free! Q61E

Expert-verified Found in: Page 204 ### Discrete Mathematics and its Applications

Book edition 7th
Author(s) Kenneth H. Rosen
Pages 808 pages
ISBN 9780073383095 # Write the deferred acceptance algorithm in pseudocode.

$\left({P}_{a},{w}_{a}\right)$ is pair of women and their accepted proposals.

And return is $\left({P}_{a},{w}_{a}\right)$ for all $a\in \left\{1,2,...,n\right\}$

See the step by step solution

## Step 1:

We will use ‘match’ algorithm.

Procedure match

$\left({m}_{1},{m}_{2},\dots ,{m}_{n},{w}_{1},{w}_{2},\dots .,{w}_{n}\text{with preference lists}{\mathrm{M}}_{1},{M}_{2},\dots {M}_{n},{W}_{1},{W}_{2},\dots {W}_{n},\text{respectively)}$

Here ${p}_{i}$ is the proposal list of women ${w}_{i}$ .

Every man proposes to their preferred women and the women reject the proposal of all the men that are not their preferred man from the entire proposal. When the men will propose to the first women in their remaining preference list and the women will reject all the proposals of their no preferred men.

This will repeat until all women have exactly one remaining proposal.

## Step 2:

For i : = 1 to n ,

${P}_{i:=}\varphi$

While there exists a ${P}_{i}$ with $i\in \left\{1,2,...,n\right\}$ such that${P}_{i:=}\varphi$

For j : = 1 to n

${P}_{{M}_{i}\left(1\right)}:={P}_{{M}_{i}\left(1\right)}\cup \left\{{M}_{j}\right\}$

For k : = 1 to n

best = ${p}_{k}\left(1\right)$

## Step 3

For all $p\in {P}_{k}$ do if p is preferred over best in ${W}_{k}$ then,

${M}_{best}:={M}_{best}-{w}_{k}$

Else

${M}_{p}:={M}_{p}-\left\{{w}_{k}\right\}$

Hence, $\left({P}_{a},{w}_{a}\right)$ is pair of women and their accepted proposals.

And return is $\left({P}_{a},{w}_{a}\right)$ for all $a\in \left\{1,2,...,n\right\}$ ### Want to see more solutions like these? 