Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chaptter2section3 [2012/01/23 23:49] – [Implementation of the algorithm] mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chaptter2section3 [2012/01/23 23:56] (current) – mugabej
@@ Line 69: / Line 69: @@
        * **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
+       * 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.
-**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.