Differences

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

--- courses:cs211:winter2012:journals:jeanpaul:chaptter2section3 [2012/01/23 22:47] – mugabej
+++ courses:cs211:winter2012:journals:jeanpaul:chaptter2section3 [2012/01/23 23:56] (current) – mugabej
@@ Line 32: / Line 32: @@
       * //deletion//: To delete //e//: Have the //e//.Prev and //e//.next point directly to each other
       * //insertion//: To insert //e// between //d// and //f//: update d.next and f.Prev to point to //e//, //e//.Prev point to //d// and //e//.next point to //f//.
+Disadvantage of //linked lists//: To find the i<sup>th</sup> element we have to follow the "next" pointers starting from "First" until we get the element, which takes O(i), whereas it takes us O(1) time with arrays.
+Using arrays and linked lists, it takes us O(n) to convert back and forth.
+===== Implementation of the algorithm =====
+The algorithm takes O(n<sup>2</sup>) to terminate, so we need to implement each iteration in O(1) time.
+  * Let's assume the set of men and women are both {1,...,n)
+  * To do this, we can order the men and women, and associate number i with the i<sup>th</sup> man m<sub>i</sub> or i<sup>th</sup> women in the same order.
+  * In this way, we have an indexed array of all men or all women
+  * We need preference lists for each man and each woman:
+      * We use 2 arrays: one for women's preference lists and another for men's preference lists
+      *  ManPref[//m//,i] represents the i<sup>th</sup> woman on man //m//'s preference list
+      * Similarly, WomanPref[//w//,i] represents the i<sup>th</sup> man on woman //w//'s preference lis
+  * The space needed to give preference to all 2//n// persons is O(n<sup>2</sup>) since each person has a list of length //n//.
+To implement our algorithm in constant time, we need to implement each of the following in constant time:
+  * We need to be able to identify a free man
+  * For a man,//m//, we need to identify the highest ranked woman to whom he has not yet proposed
+  * For a woman,//w//, we need to know if she is currently engaged,and if she is, identify the current partner
+  * For a woman,//w//, and two men,//m// and //m'//, we need to decide which of //m// or //m'// is preferred by //w//, all in constant time.
+  - __Selecting a free man__: We need to maintain a list of free men as a linked list. To select a man, we take the first man //m//  on the list. If //m// becomes engaged, we delete //m// from the list. If some other man //m'// becomes free, he's inserted at the front of the list. All of these operations are thus done in constant time using a linked list
+  - __Identifying the highest-ranked woman to whom a man //m// has not yet proposed__: To achieve this:
+       *  We maintain an extra array,call it **Next** that indicates for each man //m//the position of the next woman he will propose to on his list.
+       * We initialize **Next** = 1 for all men //m//.
+       * 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.