Skip to content

2.3 Designing algorithms

2.3-1

Using Figure 2.4 as a model, illustrate the operation of merge sort on an array initially containing the sequence $\langle 3, 41, 52, 26, 38, 57, 9, 49 \rangle$.

$$ [3|41|52|26|38|57|9|49]$$

$$\downarrow$$

$$[3|41|52|26] \quad [38|57|9|49]$$

$$\downarrow$$

$$[3|41] \quad [52|26] \quad [38|57] \quad [9|49]$$

$$\downarrow$$

$$[3] \quad [41] \quad [52] \quad [26] \quad [38] \quad [57] \quad [9] \quad [49]$$

$$\downarrow$$

$$[3|41] \quad [26|52] \quad [38|57] \quad [9|49]$$

$$\downarrow$$

$$[3|26|41|52] \quad [9|38|49|57]$$

$$\downarrow$$

$$[3|9|26|38|41|49|52|57]$$

2.3-2

The test in line 1 of the MERGE-SORT procedure reads "if $p \geq r$" rather than "if $p \neq r$." If MERGE-SORT is called with $p > r$, then the subarray $A[p:r]$ is empty. Argue that as long as the initial call of MERGE-SORT(A, 1, n) has $n \geq 1$, the test "if $p \neq r$" suffices to ensure that no recursive call has $p > r$.

  • inductive case:

$$ \begin{aligned} if \quad p \leq r\cr if \quad p < r\cr q = \lfloor (p+r)/2 \rfloor\cr q \geq p\cr q+1 \leq r\cr MERGE-SORT(A,p,q)\cr MERGE-SORT(A,q+1,r)\cr \text{else return}\cr \text{no recursive call has p>r}\cr p \leq r \text{ holds in new recursive call}\cr \end{aligned} $$

  • base case:

$$ \begin{aligned} MERGE-SORT(A,1,n)\cr n \geq 1\cr p \leq r holds\cr \end{aligned} $$

"if $p \neq r$" suffices to ensure that no recursive call has $p > r$.

2.3-3

State a loop invariant for the while loop of lines 12–18 of the MERGE procedure. Show how to use it, along with the while loops of lines 20–23 and 24–27, to prove that the MERGE procedure is correct.

  • loop invariant: at the start of each iteration, $A[p:k-1]$ consist of the smallest elements of union of $L$ and $R$ at sort order.

  • when the while loop of lines 12-18 finish $A[p:k-1]$ consist of the smallest elements of union of $L$ and $R$ at sort order, either while loop of lines 20–23 or 24–27 will be run, $L$ or $R$ has the biggest rest elements in sort order.when the second while loop finish, they are added to the end of A, and A consist of all elements at sort order.

2.3-4

Use mathematical induction to show that when $n \geq 2$ is an exact power of 2, the solution of the recurrence

$$ \begin{aligned} T(n) = \begin{cases} 2 & \text{if } n = 2, \cr 2T(n/2) + n & \text{if } n > 2 \end{cases} \end{aligned} $$ is $T(n) = n \lg n$.

$$ \begin{aligned} T(n) & = T(2^t)\cr & = 2T(2^{t-1}) + 2^t\cr & = 4T(2^{t-2}) + 2\cdot{2^t}\cr & = 2^{t-1}T(2) + 2^t\cdot{\lg 2^t }\cr & = n\lg n \end{aligned} $$

2.3-5

You can also think of insertion sort as a recursive algorithm. In order to sort $A[1:n]$, recursively sort the subarray $A[1:n-1]$ and then insert $A[n]$ into the sorted subarray $A[1:n-1]$. Write pseudocode for this recursive version of insertion sort. Give a recurrence for its worst-case running time.

INSERTIONSORT_RECURXIVE(A,n)
    if n = 1
        return
    INSERTIONSORT_RECURXIVE(A,n-1)
    i = n-1
    key = A[n]
    while A[i]>key and i>=1
        A[i+1]=A[i]
        i--
    A[i+1]=key

2.3-6

Referring back to the searching problem (see Exercise 2.1-4), observe that if the subarray being searched is already sorted, the searching algorithm can check the midpoint of the subarray against v and eliminate half of the subarray from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the subarray each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is $\Theta (\lg n)$. iterative:

BINARY_SEARCH_ITERATIVE(A,l,r,x)
    while r>=l 
        mid = (l+r)/2
        if A[mid] == x
            return mid
        else if A[mid] > x
            r = mid -1
        else
            l = mid +1
    return NIL

recursive:

BINARY_SEARCH_RECURVISE(A,l,r,x)
    if(l>r)
        return NIL
    mid= (l+r)/2
    if A[mid] == x
        return x
    if A[mid] < x
        return A[A,mid+1,r,x]
    if A[mid] > x
        return A[A,l,mid-1,x]

the worst-case is no x in $A$, BINARY SEARCH will end al condition l>r which occurs when A[l:r] is empty. since BINARY SEARCH halving the size of A[l:r] each time, it cost $\Theta (\lg n)$ to make A[l:r] empty

2.3-7

The while loop of lines 5-7 of the INSERTION-SORT procedure in Section 2.1 uses a linear search to scan (backward) through the sorted subarray $A[1:j-1]$. What if insertion sort used a binary search (see Exercise 2.3-6) instead of a linear search? Would that improve the overall worst-case running time of insertion sort to $\Theta(n \lg n)$

It can save search time, but can not save movement time. At worst -case, it cost $j-1 = \Theta(j)$ time to move elements bigger than $A[j]$ in $A[1:j-1]$.The same as the original INSERTION-SORT
Therefore, that improve the overall worst-case running time of insertion sort to $\Theta(n\lg n)$

2.3-8

Dscribe Describe an algorithm that, given a set $S$ of $n$ integers and another integer $x$, determines whether $S$ contains two elements that sum to exactly $x$. Your algorithm should take $\Theta (n \lg n)$ time in the worst case.

FUCTION(S,x)
    n=S.lenfth()
    MERGE_SORT(S,1,n) //cost $\Theta n \lgn$
    i=1
    j=n
    sum=A[i]+A[j]
    while sum !=x and j>i //cost \Theta n
        if sum > x 
            j--
        else i++ 
    if sum == x
        return i j
    else
        return NIL

The time complexity of the algorithm is $\Theta (n \lg n)+\Theta (n)$