StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q61E

Expert-verifiedFound in: Page 204

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\}$

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},\right.\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.

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)$

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\}$

94% of StudySmarter users get better grades.

Sign up for free