[[courses:cs211:winter2018:journals:devlinn:chapter1]]
Trace:
Show page
Recent ChangesSitemap

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
courses:cs211:winter2018:journals:devlinn:chapter1 [2018/01/09 22:02] – devlinncourses:cs211:winter2018:journals:devlinn:chapter1 [2018/01/09 22:13] (current) – devlinn
Line 30: Line 30:
 The runtime of this algorithm is at most n<sup>2</sup> iterations. Another interesting fact of the Gale-Shapley algorithm is that all executions return the same matching, one in which each m ∈ M is paired with its ideal w (provided no overlapping preferences). However, for all w ∈ W, their pairings are the worst possible m. The runtime of this algorithm is at most n<sup>2</sup> iterations. Another interesting fact of the Gale-Shapley algorithm is that all executions return the same matching, one in which each m ∈ M is paired with its ideal w (provided no overlapping preferences). However, for all w ∈ W, their pairings are the worst possible m.
                  
-  +I am interested by the claims being proved in this section; I do not always see the relevance in their arguments. I would assume the purpose is to illustrate the trends and facts of this algorithm. I found this section to provide a strong introduction to algorithms in a simple manner using an understandable example.
courses/cs211/winter2018/journals/devlinn/chapter1.1515535359.txt.gz · Last modified: by devlinn
Show pageOld revisions
Media ManagerBack to top
CC Attribution-Noncommercial-Share Alike 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0