1. (15 points) Stable Matching Running Time. In class, we saw that the Propose-and-reject algo- (a) Construct an instance so that the algorithm requires only O(n) iterations, and prove this fact. (b) Construct an instance so that the algorithm requires S2(n2) iterations (that is, it requires at least rithm terminates in at most n iterations, when there are n students and n colleges. Your construction should be possible for all values of n. cn2 iterations for some constant 0