Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chaptter2section3 [2012/01/23 23:34] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chaptter2section3 [2012/01/23 23:56] (current) – mugabej
@@ Line 61: / Line 61: @@
        * If a man //m// needs to propose to a woman, he will propose to //w// = ManPref[//m//,**Next**[//m//]]
        * Once //m// proposes to //w//, we increment the value of **Next**[//m//] by one, whether or not //w// accepts //m//'s proposal.
+   - __Identifying the man //m'//(if such man exists) //w// is currently engaged to in case //m// proposes to //w//__: To do this:
+       * We can maintain an array **Current** of length //n//
+       * **Current** = //null// if //w// is not currently engaged
+       * Thus **Current** = //null// for all women //w// at the start of the algorithm.
+   - __Deciding which of //m// or //m'// is preferred by //w//__:To achieve constant time for this step:
+       * At the start of the algorithm, we create an //n// X //n// array **Ranking**
+       * **Ranking**[//w//,//m//] contains the rank of man //m// in the sorted order of //w//'s preferences
+       * Creating the array **Ranking** is O(//n//<sup>2</sup>) in time, since it requires us to create such an array for each woman //w//.
+       * To decide which of //m// or //m'// is preferred by //w//, we just compare the values **Ranking**[//w//,//m//] and **Ranking**[//w//,//m'//],effectively doing it in constant time.
+All of the data structures mentioned above help us implement the Gale-Shapley algorithm in O(//n//<sup>2</sup>) time.
+To be honest, I hadn't understood quite well how we can specify the woman //w// a man //m// will propose to, and do it in constant time,before I reread the section and get how we can work it out. The preference lists representation was a little bit trickier because I was thinking of a different way of implementing them, but I'm now convinced the method in the book is really efficient.
+This section was really interesting, it does seem like materials in the book get more and more interesting as we advance through the book.I give this section a 9/10.