Differences

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

--- courses:cs211:winter2018:journals:devlinn:chapter1 [2018/01/09 21:27] – devlinn
+++ courses:cs211:winter2018:journals:devlinn:chapter1 [2018/01/09 22:13] (current) – devlinn
@@ Line 28: / Line 28: @@
     Return S (set of engaged pairs)
-The runtime of this algorithm is at most O(n<sup>2</sup>).
+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.