• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Gale Shapley sorting algorithm

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Marshal
Posts: 79180
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
What is that? Is that a mongol hoarde? Can we fend them off with this tiny ad?
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic