Differences

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

--- courses:cs211:winter2018:journals:patelk:chapter1 [2018/01/10 03:29] – patelk
+++ courses:cs211:winter2018:journals:patelk:chapter1 [2018/01/11 00:45] (current) – [1.1 A First Problem: Stable Matching] patelk
@@ Line 1: / Line 1: @@
 ====== 1.1 A First Problem: Stable Matching ======
+**Problem Explanation**
 The Stable Matching Problem originated from two mathematical economists, David Gale and Lloyd Shapley, who wanted to understand if it was possible to design a job recruiting process that was //self-enforcing//?
@@ Line 29: / Line 31: @@
 ----
+**Runtime**
+Worst-case runtime is n² interations, as there are at most n² possible pairs of men and women.
+----
+**Other**
+The G-S algorithm creates an interesting problem, in which the set that proposes the matching will always end up with the best possible stable matching, while the set that is on the other side will end up with the worst problem stable matching.
+----
+**Personal Thoughts**
+This chapter section was clear and concise in describing the Stable Matching Problem. It was well-explained and provided an interesting insight into one of the more basic algorithm problems. It is very easy to see where more complexity can be added into this problem, and serves as motivation for why this problem is explored first. It will be interesting to see cases where this problem is morphed (i.e- the example of the two sets of men and women not being completely separate).
+Readability: 9
+Interesting: 9