CLRS Chapter 2 Exercises

Exercises.md

Exercise 2.1-2

At the start of the for loop, sum contains the sum of values in the subarray A[1:i-1].

Initialization: i=1, and sum is 0, so it contains the sum of the empty array A[1:0].

Maintenance: sum increases by A[i]. So If it held A[1:i-1], then it now holds the sum of all values in the subarray A[1:i]. Incrementing i for the next iteration of the for loop then preserves the invariant.

Termination: The loop exits when i is equal to n+1. Substituting this for i in the loop in variant, we get that sum holds the sum of the values in the subarray A[1:n+1-1] = A[1:n].

Exercise 2.1-3

Descending sort is here. The comparison operator is just changed to <=.

Exercise 2.1-4

Find(A, x)
  index = nil
  for i = 1 to A.length
    if A[i] == x
      index = i
      break
  return index

Loop Invariant: At the start of the for loop, A[1:i-1] does not contain the value x.

Initialization: At the start of the for loop, A[1:0] is empty, so it does not contain x.

Maintenance: Suppose i = 3 in an array A of size 5. Suppose A[1:i-1] = A[1:2] does not contain x. The loop executes, and it does not exit early on the break statement. So A[3] did not equal x. Now, i is 4, prior to the start of the next iteration of the for loop. So A[1:4-1], or A[1:3], the combination of A[1:2] and A[3], does not contain x. Incrementing i for the next iteration of the for loop preserves the loop invariant.

Termination: Suppose the for loop exited because A[i] was equal to x. Then we will capture i in index, and return it, such that A[index] is equal to x. Suppose the loop terminated because i was equal to A.length + 1. Using the loop invariant, we have A[1:A.length+1-1] does not contain the value x, or A[1:A.length] does not contain the value x. index will hold the value nil, and we'll return it.

Exercise 2.1-5

Here is the code for adding two n-bit binary integers.

Exercise 2.2-1

$θ(n^3)$

Exercise 2.2-2

SelectionSort(A, n)
  for i = 1 to n-1
    min = nil
    minJ = nil
    for j = i to n
      if min == nil || A[j] < min
        min = A[j]
        minJ = j
    
    temp = A[i]
    A[i] = min
    A[minJ] = temp

Loop invariant: At the start of the outer loop, A[1:i-1] contains the i-1 smallest values of A, and they are sorted.

Initialization: A[1:-1] is the empty array, so it holds the smallest 0 values of A, and it is sorted.

Maintenance: Suppose n=5, and i=3. At the start of the outer loop, A[1:2] contains the 2 smallest values of A, and it is sorted.

The inner loop will loop over A[3:n] and find the smallest value in it. This value is greater than or equal to all of the values in A[1:2], by virtue of our assumption. The algorithm will then swap the value it found with A[3]. Then the loop will be ready for its next iteration. At this point, i=4, and A[1:3] holds the 3 smallest values of A, and they are sorted. So incrementing i for the next iteration of the outer loop preserves the loop invariant.

Termination: When i=n, the outer loop terminates. The loop invariant gives us thatA[1:i-1]=A[1:n-1] contains the smallest n-1 elements of the array, and they are sorted. A[n] is greater than or equal to these elements. So A is sorted.

Suppose A is sorted in descending order, so that the if statement body inside the inner for loop executes all the time. This is the worst case. The if statement will execute:

$$ \sum_{1}^{n-1}t_i-1 $$

times, where $t_i$ is the number of times the inner for loop executes for the $i^{th}$ iteration of the outer loop. $t_i$ can be found to equal $n-i+1$ after some inspection. We solve for this:

$$ \begin{align} \sum_{1}^{n-1}t_i-1 &= \sum_{1}^{n-1}n-i+1-1 \\ \sum_{1}^{n-1}n + \sum_{1}^{n-1}i \\ &= n(n-1) - n(n-1)/2 \\ &= n^2-n-(n^2-n/2) \\ &= n^2-n-(n^2/2-n/2) \\ &= n^2/2-n/2 \\ \end{align} $$

This if statement's cost dominates the running time of the algorithm. Thus the worst-case running time of SelectionSort is $θ(n^2)$.

The best case is no better, because the inner for loop executes a very similar number of times to the if statement. So the best-case running time is also $θ(n^2)$.

Exercise 2.2-3

The worst case running time of the linear search is θ(n), as the cost of the for loop body is $n$, having to traverse over the entire array, A.

To think about the average case, let us consider searching an array A of size $n=5$. If the element we're searching for is equally likely to be any element, then the probability of A[1] being the element is 1/5. So is the probability of A[2] being the element. So on, up to A[5]. Suppose we run the search 10 times. A[1] will be the element we're searching for 2/10 times. So too, for A[2]. If A[1] was the element we sought, the for loop body will have executed 1 time. If A[2], 2 times. We can look at the for loop body executions for when A[i] is the element we sought, for $i=1,2,...,5$.

$i$	How often A[i] is the element we sought	Number of for loop body executions
1	2/10	1
2	2/10	2
3	2/10	3
4	2/10	4
5	2/10	5

The weighted average of the number of times the for loop ran is:

$$ \sum_{i=1}^{5}\frac{2i}{10} = \frac{2}{10}\sum_{i=1}^{5}i=\frac{2}{10}\frac{5(5+1)}{2}=\frac{2}{10}(15)=3 $$

So the body of the for loop on average executed 3 times. The body of the for loop runs a number of times equal to a fraction of the maximum possible, $n=5$. This ratio came out to be 3/5. That's about half of 5. Generalizing this ratio for any value of n, we can express the average-case running time as $T(n)=n/2=θ(n)$.

We conclude that the running time of the average-case and worst-case running time of linear search are the same.

Exercise 2.2-4

Since sorting algorithms don't run in linear time except in the best case, you can add a linear-time check at the start of any sorting algorithm to see if the input A is already sorted. This will cost θ(n), and thus not disrupt the algorithm's original running time.

returnEarly = true
for i = 2 to n
  returnEarly = returnEarly && A[i-1] <= A[i]
if returnEarly
  return

Exercise 2.3-2

I think what the problem is asking is what if we test for p == r on line 1, instead of p >= r. I think it is written incorrectly to say we're going to test for p != r. That would return immediately even when there is legitimate sorting to be done.

So, suppose MergeSort(A,p,r) is called initially with MergeSort(A,1,n), $n \ge 1$. We want to show that MergeSort(A,p,r) will never be called recursively with $p \gt r$, as long as we have a test of p == r on line 1 of MergeSort, to return early.

Consider a call of MergeSort(A, k, k). This will return immediately.

Consider a call of MergeSort(A, k, k+1). This results in the following calculation of $q$:

$$ \begin{align} q &= \lfloor (k + k + 1)/2 \rfloor \\ &= \lfloor \frac{2k}{2} + \frac{1}{2} \rfloor \\ &= \lfloor k + \frac{1}{2} \rfloor \\ &= k \\ \end{align} $$

Which will result in calls to MergeSort(A,k,k) and MergeSort(A,k+1,k+1), both of which will return immediately since p == r for these.

Finally, consider the final possibilility of MergeSort(A,k,k+j), $j \gt 1$ (so $j \ge 2$). We have the following calculation of $q$.

$$ \begin{align} q &= \lfloor (k + k + j) / 2 \rfloor \\ &= \lfloor \frac{2k}{2} + \frac{j}{2} \rfloor \\ &\ge k + 1 \end{align} $$

So this results in calls to MergeSort(A,k,k+1) and MergeSort(A,k+2,k+j) where $j \ge 2$. We already know that the first of these is safe. As for the second, if j == 2, it will return immediately. If j > 2, let l = k + 2. Let m = j - 2. Since j > 2, m >= 1. The second call is rewritten as MergeSort(A,l,l+m). It is MergeSort(l,l+1) if m == 1. We've covered this case. That just leaves MergeSort(A,l,l+m) with m > 1. Thus,

MergeSort(A,k,k+j) with j > 1 $\implies$ MergeSort(A,l,l+m) with m > 1 (unless one of our earlier cases was triggered).

All of this is to say that MergeSort(A,k,k+j) with j >= 0 ensures no call to MergeSort(A,p,r) will ever be made with p < r. MergeSort(A,1,n) with n >= 1 is well-examined by the above cases.

This solution needs to consider situations of $q \gt k + 1$.

Exercise 2.3-3

Loop Invariant: At the start of the while loop, A[p:k-1] is a sorted subarray, containing the sorted elements from subarrays L[0:i-1] and R[0:j-1].

Initialization: i=0 and j=0, k=p. So the empty subarray A[p:p-1] contains the sorted elements from the (also) empty arrays L[0:-1] and R[0:-1].

Maintenance: Suppose p=5, k = 8, i=1, and j=2, n_L=4, and n_R=4. This means A[p:k-1]=A[5:7] contains the sorted elements from L[0:0] and R[0:1].

Suppose L[1] < R[3]. Then A[8] will be assigned L[1], and i and k will be incremented to 2 and 9, respectively. Then A[5:8] will contain A[5:7] combined with A[8]=L[1], and it is sorted. It contains all elements from L[0:1] and R[0:1]. So incrementing k for the next iteration of the for loop preserves the invariant, in this case.

Suppose L[1] >= R[2]. Then A[8] will be assigned R[2], and j and k will be incremented to 3 and 9, respectively. Then A[5:8] will contain A[5:7] combined with A[8]=R[2], and it will be sorted. It contains all elements from L[0:0] and R[0:2]. So incrementing k for the next iteration of the for loop preserves the loop invariant in this case.

So regardless of whether L[1] < R[3] or not, incrementing k for the next iteration of the for loop preserves the loop invariant.

Termination: Either i = n_L or j = n_R. If the former, the loop invariant gives us that A[p:k-1] contained the sorted elements of L[0:n_L-1] and R[0:j-1]. Lines 20 to 23 will not execute, but 24-27 will. These will append (n_R-j) elements to A[p:k-1] (for p=5 and k=11, A[5:10]), and then (for n_R-j=4-2=2) k will equal 13, and A[p:k-1]=A[5:13-1]=A[5:12] will contain the sorted elements from L and R. Suppose the latter, the loop invariant gives us that A[p:k-1] contained the sorted elements of L[0:i-1] and R[0:n_R-1]. Lines 24-27 will not execute, but 20-23 will. These will append (n_L-i) elements to A[p:k-1] (for p=5, k=10, A[5:9]), and then (for n_L-i=4-1=3) k will equal 13, and A[5:k-1]=A[5:12] will contain the sorted elements from L and R. So regardless of which of the two conditions caused the while loop of lines 12-18 to exit, A[5:12] will contain the sorted elements of L and R.

Exercise 2.3-4

We see what the base case of T(2) is equal to:

$$ \begin{align} T(2)&=2\\ &=\lg 4\\ &=\lg 2^2 \\ &= 2 \lg 2 \\ &= n \lg n \end{align} $$

Now we assume $T(n) = n \lg n$ where $n=2^i$ and see what $T(m)$ is, where $m=2^{i+1}$:

$$ \begin{align} T(m)&=2T(m/2)+m \\ &=2 T(2^i) + m \\ &= 2(n \lg n) + m \\ &= n \lg n^2 + m \\ &= 2^i \lg 2^{2i} + m \\ &= 2^i 2i + m \\ &= i2^{i+1} + m \\ &= i2^{i+1} + 2^{i+1} \\ &= 2^{i+1}(i+1) \\ &= m(i+1) \\ &= m \lg 2^{i+1} \\ &= m \lg m \end{align} $$

$\implies T(n) = n \lg n$, when $n=2^i$ for some $i \in Z^{*}$.

Exercise 2.3-5

Here is the code for the recursive InsertionSort.

Its worst-case running time is $T(n) = T(n-1) + n$.

Exercise 2.3-6

The binary search code is here.

The size of the input to find on any given call to it is $r-p$. On every call to find, we take the average of p and r (and name it q), and in the worst case call find again with either (p,q-1) or (q+1, r).

In the first case, the next size of the input will be (we drop respect for the floor and minus 1):

$$ \begin{align} q-1-p &= \lfloor (p+r)/2 \rfloor - 1 - p \\ &= \frac{p}{2} + \frac{r}{2} - 1 - p \\ &= -\frac{p}{2} + \frac{r}{2} \\ &= (r-p)/2 \end{align} $$

So the size of the input has been cut in half. If we choose (q+1, r), we get:

$$ \begin{align} r-(q+1) &= r - (\lfloor (p + r)/2 \rfloor + 1) \\ &= r - \frac{p}{2} - \frac{r}{2} - 1 \\ &= \frac{r}{2} - \frac{p}{2} \\ &= (r-p)/2 \end{align} $$

So the input size is cut in half no matter which of the two possible routes the code takes. You can draw a recursion tree, which will have $\lg n + 2$ nodes at most. Each node has an edge going to exactly one other node, the one it calls. The addition of 2 is for when $r-p$ is 1 and 0. The cost of traversing the entire tree, in the worst case, and finding (or not finding) x is thus $θ(\lg n)$.

Exercise 2.3-7

No, the binary search would not improve things. Even though it could find where the key needs to be inserted in $\lg n$ time, space has to be made for the key. At the $i^{th}$ iteration of the outer loop, in the worst case, there are $i-1$ elements that need to be moved one place to the right. This takes linear time, and it's the inner loop. So the worst case running time is still $θ(n^2)$.

Exercise 2.3-8

The code for finding the two elements that sum to x is here.

It uses MergeSort at the outset, costing $n \lg n$. It then brings two indices i and j together until they cross, in a while loop. This is linear time, so the cost of FindSum is $θ(n \lg n + n) = θ(n \lg n)$. This holds for the worst-case, as the most expensive part of this algorithm is the call to MergeSort.