Differences

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

--- courses:cs211:winter2018:journals:devlinn:chapter1 [2018/01/09 16:34] – devlinn
+++ courses:cs211:winter2018:journals:devlinn:chapter1 [2018/01/09 22:13] (current) – devlinn
@@ Line 1: / Line 1: @@
 ====== Chapter 1: Introduction ======
-===== 1.1 A First Problem: Stable Matching =====
+==== 1.1 A First Problem: Stable Matching ====
 The Stable Matching Problem is based on a question posed by David Gale and Lloyd Shapley which involved a self-enforcing admissions or recruiting process. In a more technical sense, this question is phrased as follows:
@@ Line 28: / Line 28: @@
     Return S (set of engaged pairs)
-The runtime of this algorithm is at most O(n2)
+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.