Win a copy of Kotlin in Action this week in the Kotlin forum!
  • Post Reply Bookmark Topic Watch Topic
  • New Topic

Gale Shapley sorting algorithm  RSS feed

 
Adebayo Adeoya
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello guys, can someone help me with a solution to this problem:
QST: You may be wondering how having repeated rankings affect the performance of Gale_shapley algorithm. To test this, implement the stable matching with repeating preferences variant of Gale Shapley algorithm, with input give as above. You can use any programming language and any data structures.Then do the test as follows :
(i) First , as a control, let k = n. Generate random inputs for n = 20 to n = 200, in increments of 10; produce random inputs for each n. Now, run your program on each of these test cases and record the number of rounds as well as the overall running time for each.
(ii) To test  what happens when k is a small constant, repeat the experiment with k = 10, for the same range of n and number of samples for each n.
 
Campbell Ritchie
Marshal
Posts: 55717
163
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Welcome to the Ranch

Please show us what you have achieved so far, and please explain what the Gale Shapley algorithm is.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!