(Number of Stable Matchings) The analysis of the Gale-Shapley algorithm establishes that every instance of the stable matching problem admits at least one stable matching. Here we consider how many such matchings might exist. (a) Give an algorithm that takes an instance of the stable matching problem as input and decides if there is eractly one stable matching for this instance (that is, the algorithm outputs either "unique stable matching", or "more than one stable matching"). Pay close attention to the proof of correctness of your algorithm. (b) Show that the maximum number of possible stable matchings for instances with n men and n women scales super-polynomially in n. In other words, show that it is possible to construct a stable matching problem, in which the number of possible stable matchings is (nc) for any c> 0. (Number of Stable Matchings) The analysis of the Gale-Shapley algorithm establishes that every instance of the stable matching problem admits at least one stable matching. Here we consider how many such matchings might exist. (a) Give an algorithm that takes an instance of the stable matching problem as input and decides if there is eractly one stable matching for this instance (that is, the algorithm outputs either "unique stable matching", or "more than one stable matching"). Pay close attention to the proof of correctness of your algorithm. (b) Show that the maximum number of possible stable matchings for instances with n men and n women scales super-polynomially in n. In other words, show that it is possible to construct a stable matching problem, in which the number of possible stable matchings is (nc) for any c> 0