$($a$)$ In the notes, we show that the stable matching algorithm terminates in at most $n^2$ days. Prove the following stronger result: the stable matching algorithm will always terminate in at most $(n-1{)}^2+1=n^2-2n+2$ days.

$($b$)$ Provide a set of preference lists for $4$ jobs and $4$ candidates that will result in the upper bound from part $($a$)$ when running the Propose$-$and$-$Reject algorithm. Verify this by running the Propose$-$and$-$Reject algorithm on your preference lists.