Lab 12 Gale-Shapley and Irving Algorithms

Galey-Shapley and Irving Algorithms (Groups of up to 3 students)

1. Find the best and worst cases for the Gale-Shapley and Irving ( An Efficient Algorithm for the “Stable Roommates” Problem) Algorithms and run in Colab these algorithms for those cases for n=4 and 40.
   • Gale–Shapley algorithm simply explained – towardsdatascience
   • Stable Marriage Problem – geeksforgeeks
   • Stable matching, as a game – towardsdatascience.com
2. Run the Gale-Shapley Algorithm 100 times using random permutations as preference lists for n=4 and 40. Find the minimum, maximum and average number of iterations and plot the distribution of the number of iterations.
3. (Extra credit) Simulate the the Gale-Shapley and Irving algorithms using random preference lists , for n=4 and 40 and generate a gift animation fo the type show in "Illustrating the Deferred Acceptance Algorithm with R – Code https://www.r-bloggers.com/illustrating-the-deferred-acceptance-algorithm-with-r/
   • https://gist.github.com/dsparks/3892404
   • https://gist.github.com/1628636
   • https://www.pythoninformer.com/python-libraries/pillow/creating-animated-gif/
   • https://www.quora.com/How-do-I-plot-a-grayscale-image-with-a-2D-array-of-random-numbers-in-Python

Upload the links to the Colab Notebook in UN Moodle (do not include emails because it sends annoying email updates)