to q in da( I 0); otherwise, p is single in da( I 0). Hints:( 1) Use the confluence property of the deferred acceptance algorithm;( 2) Observe that once execution of the deferred acceptance algorithm reaches a state where there is exactly one single man who has not proposed to all of his acceptable women, the rest of the execution is deterministic. Definition: For any SMI instance I and any woman q in I, we define the unique element x identified in Problem 1 as threshold( I, q). Problem 2. Let I be an SMI instance, let q be a woman in I, let p be a man who is not in I, and let I 0 be an SMI instance in add( I, p, q). Prove that no woman q 0 in I prefers threshold( I, q 0) to threshold( I 0, q 0). Hints:( 1) Use proof by contradiction, i. e., assume that there is a woman q 0 who prefers threshold( I, q 0) to threshold( I 0, q 0), and derive a contradiction;( 2) Use the confluence property of the deferred acceptance algorithm. Problem 3. Let I be an SMI instance, let q be a woman in I, let p be a man who is not in I, and let I 0 be an SMI instance in add( I, p, q). Prove that if p is single in 2 University of Texas at Austin Department of Computer Science Algorithms and Complexity CS 331, Spring 2017 da( I 0), then threshold( I 0, q 0) = threshold( I, q 0) for every woman q 0 in I. Hints:( 1) Use proof by contradiction, i. e., assume p is single in da( I 0) and there is a woman q 0 such that threshold( I 0, q 0) 6 = threshold( I, q 0), and derive a contradiction;( 2) Use the result of Problem 2;