$1.$ Describe a $\backslash$Theta $($n log n$)$ time algorithm that, given a set S of n integers and another integer x$,$

determines whether or not there exist two elements in S whose difference is exactly x$.$

$2.$ Suppose that in the MergeSort algorithm the input sequence split into k subsequences $($k $>2,$

but fixed$).$ Determine the running time of such algorithm. Does it have any advantages

comparing to the standard MergeSort? $($You may wish to look into Chapter $4$ of CLR$.)$

$3.$ We explore the issue of truthfulness in the Stable Matching problem and specifically in the

Gale$-$Shapley algorithm. The basic question is: Can a man or a woman end up better off

lying about his or her preferences? More concretely, we suppose each participant has a true

preference order. Consider a woman w$.$ Suppose w prefers man m to m$,$ but both m and m$$

are low on her list of preferences. Can it be the case that by switching the order of m and m$$

on her list of preferences $($i$.$e$.$ by falsely claiming that she prefers m$$ to m$)$ and running the

algorithm with this false preference list, w will end up with a man m$$ that she truly prefers

to both m and m$,$ but would not end up with using the true list of preferences?

Resolve this question by doing one of the following two things:

$($a$)$ Give a proof that, for any set of preference lists, switching the order of a pair on the list

cannot improve a woman$$s partner in the Gale$-$Shapley algorithm; or

$($b$)$ Give an example of a set of preference lists for which there is a switch that would improve

the partner of a woman who switched preferences.

$4.$ An m $\backslash$times n Young tableau is an m $\backslash$times n matrix such that the entries of each row are in sorted order from left to right and the entries of each column are in sorted order from top to bottom.

Some of the entries of a Young tableau may be $\backslash$infty $,$ which we treat as nonexistent element.

Thus a Young tableau can be used to hold r $<=$ mn finite numbers.

$($a$)$ Show how to insert a new element into a non$-$full m$\backslash$times n Young tableau in O$($m$+$n$)$ time.

$($b$)$ Give a O$($m$+$n$)$ time algorithm to determine whether a given number is stored in a given

O$($m $+$ n$)$ Young tableau.

$5.$ Show that the worst$-$case running time of Heapify$-$Up on a heap of size n is $\backslash$Omega $($log n$).$

$6.($a$)$ What is the running time of Quicksort whe all elements of array A have the same value?

$($b$)$ Show that the running time of Quicksort is $\backslash$Theta $($n$2)$ when the array A contains distinct

elements and is ordered in decreasing order.

$7.$ The Quicksort algorithm contains two recursive calls to itself. After the call to Partition,

the left subarray is recursively sorted and then the right subarray is recursively sorted. The

second recursive call in Quicksort is not really necessary; it can be avoided by using an

iterative control structure. This technique, called tail recursion, is provided automatically by

good compilers. Consider the following version of Quicksort, which simulates tail recursion.

Quicksort$($A$,$p$,$r$)$

while p