Chapter 2 1-2 Problems, Introduction to Algorithms, 3rd Edition Thomas H. Cormen

2-1 Insertion sort on small arrays in merge sort 
Although merge sort runs in Θ(nlgn) worst-case time and insertion sort runs in Θ(n2) worst-case time, the constant factors in insertion sort make it faster for small n. Thus, it makes sense to use insertion sort within merge sort when subproblems become sufficiently small. Consider a modification to merge sort in which n/k sublists of length k are sorted using insertion sort and then merged using the standard merging mechanism, where k is a value to be determined.

1. Show that the n/k sublists, each of length k, can be sorted by insertion sort in Θ(nk) worst-case time.
2. Show that the sublists can be merged in Θ(nlg(n/k)) worst-case time.
3. Given that the modified algorithm runs in Θ(nk+nlg(n/k)) worst-case time, what is the largest asymptotic (Θ-notation) value of k as a function of n for which the modified algorithm has the same asymptotic running time as standard merge sort , in terms of Θ-notation?
4. How should k be chosen in practice?

Solution:
1. Sorting Sublists
 For input of size k, insertion sort runs on Θ(k²) worst-case time, i.e. running time of the form (ak²+bk+c). So, worst-case time required to sort n/k sublists, each of length k, with insertion sort:

$$T(k) = \frac n k (ak^2 +bk +c) = ank + bn + \frac {cn} k$$

 Now, k is an integer significantly smaller than n. So, for sufficiently large values of n, we can ignore the last two term of T(k). So, T(k)=Θ(nk).
 2. Merging Sublists
We have n elements divided into n/k sorted sublists each of length k. To merge these n/k sorted sublists to get a single sorted list of length n, we have to take 2 sublists at a time and continue to merge them. This will result in log(n/k) steps. And in every step, we are essentially going to compare n elements. So the whole process will run at Θ(nlg(n/k)).
3. Largest Value of k
 For the modified algorithm to have the same asymptotic running time as standard merge sort, Θ(nk+nlg(n/k))=Θ(nk+nlgn−nlgk) must be same as Θ(nlgn)

To satisfy this condition, k cannot grow faster than lgn asymptotically (if k grows faster than lgn, because of the nk term, the algorithm will run at worse asymptotic time than Θ(nlgn). But just this argument is not enough as we have to check for k=Θ(lgn), the requirement holds or not.

If we assume, k=Θ(lgn),

Θ(nk+nlg(n/k))=Θ(nk+nlgn−nlgk)

=Θ(nlgn+nlgn−nlg(lgn))

=Θ(2nlgn−nlg(lgn))

=Θ(nlgn) 

4. Practical Value of k

In practice, k should be the largest list length on which insertion sort is faster than merge sort.

2-2 Correctness of bubble-sort

Bubble-sort is a popular, but inefficient, sorting algorithm. It works by repeatedly swapping adjacent elements that are out of order. 

BUBBLESORT(A)
  for i to A.length - 1
      for j = A.length downto i + 1
          if A[j] < A[j - 1]
              exchange A[j] with A[j - 1]

1. Let A′ denote the output of BUBBLESORT(A). To prove that BUBBLESORT is correct, we need to prove that it terminates and that  A′[1]≤A′[2]≤⋯≤A′[n](2.3) where n=length[A]. What else must be proved to show that BUBBLESORT actually sorts? 
2. State precisely a loop invariant for the for loop in lines 2–4, and prove that this loop invariant holds. Your proof should use the structure of the loop invariant proof presented in this chapter.
3. Using the termination condition of the loop invariant proved in part (2), state a loop invariant for the for loop in lines 1–4 that will allow you to prove inequality (2.3). Your proof should use the structure of the loop invariant proof presented in this chapter. 
4. What is the worst-case running time of bubblesort? How does it compare to the running time of insertion sort?

Solution:
1. Required Proof of Correctnesses
We also need to prove that A′ consists of the elements originally in A but in sorted order.
2. Loop Invariant for Inner Loop
The loop invariant for the for loop in lines 2–4 can be stated as follows:
At the start of each iteration of the for loop, the subarray A[j..n] consists of the elements originally in A[j..n] before entering the loop but possibly in a different order and the first element is the smallest among them.
And here is how the three necessary properties hold for the loop invariant:

Initialization: Initially the subarray contains only the last element A[n] and this is the smallest element of the subarray.

Maintenance: In every step we compare A[j] with A[j−1] and make A[j−1] the smallest among them. So, after the iteration, , the length of the subarray increases by one and the first element is the smallest of the subarray. 

Termination: The loop terminates when j=i+1. At that point also the length of the subarray increases by one and the first element is the smallest of the subarray as we swap A[i+1] with A[i].

3. Loop Invariant for the Outer Loop

The loop invariant for the for loop in lines 1–4 can be stated as follows:

At the start of each iteration of the for loop, the subarray A[1..i−1] consists of the elements that are smaller than the elements in the subarray A[i..n] in sorted order.

And here is how the three necessary properties hold for the loop invariant:

Initialization: Initially the subarray A[1..i−1] is empty and trivially this is the smallest element of the subarray.

Maintenance: From part (2), after the execution of the inner loop, A[i] will be the smallest element of the subarray A[i..n]. And in the beginning of the outer loop, A[1..i−1] consists of elements that are smaller than the elements of A[i..n], in sorted order. So, after the execution of the outer loop, subarray A[1..i] will consists of elements that are smaller than the elements of A[i+1..n] , in sorted order.

Termination: The loop terminates when i=A.length. At that point the array A[1..n] will consists of all elements in sorted order.

4. Running Time of Bubblesort

• At worst-case, bubblesort will iterate over the whole array for each element, i.e. for each element bubble sort will perform n comparisons and swaps. Therefore, worst-case running time of bubblesort is Θ(n²).
• Although insertion also runs at Θ(n²) worst-case time, the number of assignments (swaps) performed in bubblesort is way more than that of insertion sort. So, the constant factors in the running time will be much larger for bubblesort compared to that of insertion sort. This means, for the same input size, insertion sort will run faster than bubblesort.

Chapter 2 Exercise 2.3, Introduction to Algorithms, 3rd Edition Thomas H. Cormen

2.3-1 Using Figure 2.4 as a model, illustrate the operation of merge sort on the array A=<3,41,52,26,38,57,9,49>

Solution:

2.3-2 Rewrite the MERGE procedure so that it does not use sentinels, instead stopping once either array L or R has had all its elements copied back to A and then copying the remainder of the other array back into A.

Solution:

MERGE(A, p, q, r)
 n1 = q - p + 1
 n2 = r - q
 create arrays L[1..n1] and R[1..n2]
 for i = 1 to n1
   L[i] = A[p + i - 1]
 for j = 1 to n2
   R[j] = A[q + j]
 i = 1
 j = 1
 for k = p to r
   if i > n1
    A[k] = R[j]
    j = j + 1
   else if j > n2
    A[k] = L[i]
    i = i + 1
   else if L[i] ≤ R[j]
    A[k] = L[i]
    i = i + 1
   else
    A[k] = R[j]
    j = j + 1

2.3-3 Use mathematical induction to show that when n is an exact power of 2, the solution of the recurrence

$$T(n) = \begin{cases} 2 & \text{if } n = 2, \\ 2T(n/2) + n & \text{if } n = 2^k, \text{for } k > 1. \end{cases}$$

is $$T(n) = n\lg{n}$$

Solution:

First, let's establish a function on which we're going to perform induction:

$$F(k) = T(2^k)$$

We want to prove that:

$$F(k) = 2^k \lg{2^k}$$

Base. It is simple enough:

$$F(1) = T(2) = 2 = 2\lg2 = 2^1\lg{2^1}$$

Step. We assume that:

$$F(k) = 2^k \lg{2^k}$$

We prove it for k+1:

$$\begin{align} F(k + 1) & = T(2^{k+1})= 2T(\frac{2^{k+1}}{2}) + 2^{k+1} = \\ & = 2T(2^k) + 2^{k+1} = 2 \cdot 2^k \lg{2^k} + 2^{k+1} = \\ & = 2^{k+1}(\lg{2^k} + 1) = 2^{k+1}(\lg{2^k} + \lg2) = \\ & = 2^{k+1}\lg{2^{k+1}} \end{align}$$

2.3-4 We can express insertion sort as a recursive procedure as follows. In order to sort. In order to sort A[1..n], we recursively sort A[1..n−1] and then insert A[n] into the sorted array A[1..n−1]. Write a recurrence for the running time of this recursive version of insertion sort.

Solution:

There are two steps in this recursive sorting algorithm:

1.  Sort the sub-array A[1..n−1]
2. Insert A[n] into the sorted sub-array from step 1 in proper position

For n=1, step 1 doesn’t take any time as the sub-array is an empty array and step 2 takes constant time, i.e. the algorithm runs in Θ(1) time.
For n>1, step 1 again calls for the recursion for n−1 and step 2 runs in Θ(n) time.

So, we can write the recurrence as:

$$% <![CDATA[ T(n) = \begin {cases} \Theta(1) & \text { if } n = 1, \\ T(n - 1) + \Theta(n) & \text { if } n > 1 \end {cases} %]]>$$

Solution to the Recurrence: Let us assume that for n=1, T(n)=c₁, where c₁ is some constant. 

And on average for n>1, inserting an element in its proper position in a sorted array requires shifting half of the elements, i.e. c₂n/2+c₃ time (c₂n/2 for shifting the elements and c₃

for inserting the element).

So, we can rewrite the recurrence as:
$$% <![CDATA[ T(n) = \begin {cases} c_1 & \text { if } n = 1, \\ T(n - 1) + c_2(n - 1)/2 + c_3 & \text { if } n > 1 \end {cases} %]]>$$
So for any general n>1,

$$% <![CDATA[ \begin {align} T(n) & = T(n - 1) + c_2(n - 1)/2 + c_3 \\ & = T(n - 2) + c_2(n - 2)/2 + c_3 + \{c_2(n - 1)/2 + c_3\} \\ & = T(1) + \cdot \cdot \cdot + \{c_2(n - 2)/2 + c_3\} + \{c_2(n - 1)/2 + c_3\} \\ & = c_1 + \frac {c_2} 2 \{1 + 2 + \cdot \cdot \cdot + (n - 1)\} + c_3(n - 1) \\ & = c_1 + \frac {c_2} 2 \cdot \frac {n(n - 1)} 2 + c_3(n - 1) \\ & = \Theta(n^2) \end {align} %]]>$$

2.3-5 Referring back to the searching problem (see Exercise 2.1-3), observe that if the sequence A is sorted, we can check the midpoint of the sequence against and eliminate half of the sequence from further consideration. The binary search algorithm repeats this procedure, halving the size of the remaining portion of the sequence each time. Write pseudocode, either iterative or recursive, for binary search. Argue that the worst-case running time of binary search is Θ(lgn).

Solution:

Pseudo-code:

ITERATIVE-BINARY_SEARCH(A, v)
 low = A[1]
 high = A[A.length]
 while low ≤ high
  mid = (low + high) / 2
  if v == A[mid]
   return mid
  elseif v > A[mid]
   low = mid + 1
  else
   high = mid - 1
 return NIL

RECURSIVE-BINARY-SEARCH(A, v, low, high)
 if low > high
    return NIL
 mid = (low + high) / 2
 if v == A[mid]
  return mid
 elseif v > A[mid]
  RECURSIVE-BINARY-SEARCH(A, v, mid + 1, high)
 else
  RECURSIVE-BINARY-SEARCH(A, v, low, mid - 1)

Intuitively, in worst case, i.e. when v is not at all present in A, we need to binary search over the whole array to return NIL. So in worst-case, we need to repeatedly divide the array by 2. So the running time is nothing but how many times the input size can be divided by 2, i.e. lgn.

And using recurrence formula, we can say running time T(n)=T((n−1)/2)+Θ(1)=Θ(lgn).

2.3-6 Observe that 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]. Can we use a binary search (see Exercise 2.3-5) instead to improve the overall worst-case running time of insertion sort to Θ(nlgn)?

Solution:

Insertion sort has a loop like this

while i > 0 and A[i] > key
    A[i + 1] = A[i]
    i = i - 1

This loop serves two purposes:

1. A linear search to scan (backward) through the sorted sub-array to find the proper position for key.
2. Shift the elements greater than key towards the end to insert key in the proper position.

Although we can reduce the number of comparisons by using binary search to accomplish purpose 1, we still need to shift all the elements greater than key towards the end of the array to insert key. And this shifting of elements runs at Θ(n) time, even in average case (as we need to shift half of the elements). So, the overall worst-case running time of insertion sort will still be Θ(n²).

2.3-7 Describe a Θ(nlgn)-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 sum is exactly x.

Solution:

First we sort S. Afterwards, we iterate it and for each element i we perform a binary search to see if there is an element equal to x−i. If one is found, the algorithm returns true. Otherwise, it returns false.

We iterate n elements and perform binary search for each on in an n-sized array, which leads to Θ(nlgn)-time. If we sort first (with merge sort) it will introduce another Θ(nlgn) time, that would change the constant in the final algorithm, but not the asymptotic time.

PAIR-EXISTS(S, x):
  A = MERGE-SORT(S)

  for i = 1 to S.length
      if BINARY-SEARCH(A, x - S[i]) != NIL
          return true

  return false

Chapter 2 Exercise 2.2, Introduction to Algorithms, 3rd Edition Thomas H. Cormen

2.2-1 Express the function $$n^3/1000-100n^2-100n+\mathrm{3\; in\; terms\; of}$$
$$\theta -notatio\mathrm{n.}$$

$$\mathrm{Solution:}$$
The leading term of the function ignoring the constant coefficient is $$n^3$$ . So, the function in $$\theta -notation$$will be $$\theta (n^3).$$

$$2.2-2\; Consider\; sorting\; n\; numbers\; stored\; in\; array\; A\; by\; first\; finding\; the\; smallest\; element\; of\; A\; and\; exchanging\; it\; with\; the\; element\; in\; A[1].\; Then\; find\; the\; second\; smallest\; element\; of\; A,\; and\; exchange\; it\; with\; A[2].\; Continue\; in\; this\; manner\; for\; the\; first\; n\; 1elements\; of\; A.\; Write\; pseudocode\; for\; this\; algorithm,\; which\; is\; known\; as\; selection\; sort.\; What\; loop\; invariant\; does\; this\; algorithm\; maintain?\; Why\; does\; it\; need\; to\; run\; for\; only\; the\; first\; n\; 1\; elements,\; rather\; than\; for\; all\; n\; elements?\; Give\; the\; best-case\; and\; worst-case\; running\; times\; of\; selection\; sort\; in$$$$\theta -notation?\; Justify\; your\; answers.$$

$$Solution:$$

$$Pseudocode$$

SELECTION-SORT(A):
  for i = 1 to A.length - 1
      min = i
      for j = i + 1 to A.length
          if A[j] < A[min]
              min = j
      temp = A[i]
      A[i] = A[min]
      A[min] = temp

Loop invariants

At the start of each iteration of the inner for loop, A[min] is the smallest number in the subarray A[i..j−1].

Why n−1 elements?
In the final step, the algorithm will be left with two elements to compare. It will store the smaller one in A[n−1] and leave the larger in A[n]. The final one will be the largest element of the array, since all the previous iteration would have sorted all but the last two elements (the outer loop invariant). If we do it n times, we will end up with a redundant step that sorts a single-element subarray.

Running times
In the best-case time (the array is sorted), the body of the if is never invoked. The number of operations (counting the comparison as one operation) is:

$$ (n - 1)(\frac{n + 2}{2} + 4) $$

In the worst-case time (the array is reversed), the body of the if is invoked on every occasion, which doubles the number of steps in the inner loop, that is:

 (n-1)(n+6)

Both are clearly Θ(n2).

2.2-3 Consider linear search again (see Exercise 2.1-3). How many elements of the input sequence need to be checked on the average, assuming that the element being searched for is equally likely to be any element in the array? How about in the worst case? What are the average-case and worst-case running times of linear search in ‚Θ-notation? Justify your answers.

Solution:

If the element is present in the sequence, half of the elements are likely to be checked before it is found in the average case. In the worst case, all of them will be checked. That is, n/2 checks for the average case and n for the worst case. Both of them are Θ(n).

2.2-4 How can we modify almost any algorithm to have a good best-case running time?

Solution:

We can modify it to handle the best-case efficiently. For example, if we modify merge-sort to check if the array is sorted and just return it, the best-case running time will be Θ(n).

Chapter 2 Exercise 2.1, Introduction to Algorithms, 3rd Edition Thomas H. Cormen

2.1-1 Using Figure 2.2 as a model, illustrate the operation of INSERTION -SORT on the array A=⟨31,41,59,26,41,58⟩.

Solution:

2.1-2 Rewrite the INSERTION -SORT procedure to sort into nonincreasing instead of non-decreasing order.

Solution:

Insertion-Sort(A)

for j = 2 to A.length
    key = A[j]
    // Insert A[j] into the sorted sequence A[1..j − 1]
    i = j − 1
    while i > 0 and A[i] < key
        A[i + 1] = A[i]
        i = i − 1
    A[i + 1] = key

2.1-3 Consider the searching problem:

Input: A sequence of n numbers A=<a₁,a₂,...,a_n> and a value v.

Output: An index i such that v=A[i] or the special value NIL if v does not appear in A.

Write pseudocode for linear search, which scans through the sequence, looking for v. Using a loop invariant, prove that your algorithm is correct. Make sure that your loop invariant fulfills the three necessary properties.

Solution:

Linear-Search(A,v): 
for i = 1 to A.length
    if A[i] == v
        return i

return NIL

Initialization: Initially the subarray is empty. So, none of its’ elements are equal to v.

Maintenance: In i-th iteration, we check whether A[i] is equal to v or not. If yes, we terminate the loop or we continue the iteration. So, if the subarray A[1..i−1] did not contain v before the i-th iteration, the subarray A[1..i] will not contain v before the next iteration (unless i-th iteration terminates the loop).

Termination: The loop terminates in either of the following cases,

• We have found index i such that v = A_i
  
• We reached the end of the array, i.e. we did not find v in the array A. So, we return NIL
  

In either case, our algorithm does exactly what was required, which means the algorithm is correct.

2.1-4 Consider the problem of adding two n-bit binary integers, stored in two n-element arrays A and B. The sum of the two integers should be stored in binary form in an .n C 1/-element array C . State the problem formally and write pseudocode for adding the two integers.

Solution:

Input: Two n-bit binary integers stored in two n-element array of binary digits (either 0 or 1)

A=<a₁,a₂,...,a_n> and B=<b₁,b₂,...,b_n>.

Output: A (n+1)-bit binary integer stored in (n+1)-element array of binary digits (either 0 or 1) C=⟨c₁,c₂,...,c_n+1⟩ such that C=A+B.

Binary-Add(A,B): 
n = A.length
for i = 1 to (n + 1)
    C[i] = 0

carry = 0
for i = n to 1
    C[i] = (A[i] + B[i] + carry) % 2
    carry = (A[i] + B[i] + carry) / 2
C[i] = carry

return C