Solutions to Cormen Chapter 2. Without further ado let’s get to business.

2.1.1 Using figure 2.4 as a model, illustrate the operations ofInsertion-Sorton the array A = [31, 41, 59, 26, 41, 58]

Well you can do it by yourself.

2.1.2 Rewrite theInsertion-Sortprocedure to sort into nonincreasing instead of nondecreasing order.

This is straightforward. All needed to be done is to reverse the condition at the starting of the while loop.

for j = 2 to A.length key = A[j] i = j - 1 while i > 0 and A[i] < key //note here we replaced A[i] > key with 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 ofnnumbersA = [aand a value_{1}, a_{2}, a_{3}……a_{n}]v.

Output: And indexisuch thatv = A[i]or a special valueNILifvis not found inA.

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

Its a simple linear search the pseudocode is simple too:

SEARCH(A, v): for i = 1 to A.length if A[i] == v return i return NIL

Now comes the part of defining the loop invariant. This I defined to be like “**At the start of each iteration of the for loop, the subarray A[1…..i-1] consists of elements that are different than v**“.

Now comes the part where we verify the correctness with 3 conditions.

**Initialization:** At the beginning, i.e. before the firs iteration the subarray is simply empty, this becomes the trivial.

**Maintenance:** For every step we check *A[i]* against *v*. We have already assumed that *A[1…..i-1]* does not contain *v*. So if we find *v* at *A[i]* we return it and the loops terminates with the procedure itself.

**Termination:** Loop terminates if* i > A.lenghth* which signifies the checking of the complete array. In this case we simple return* NIL*. The other condition in which loop ends is by the ending of the procedure itself when it returns the value of i in case we get *A[i] = v*.

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+1) bit element array C. State the problem formally and write pseudocode for adding the two integers.

I am not going to state the problem formally as we already understand it properly. Here is the psuedocode:

AddNbitArrays(A, B) C = newArray integer(A.length) carry = 0 for i = 1 to A.length C[i] = (A[i] + B[i] + carry) % 2 carry = (A[i] + B[i] + carry) / 2 C[i] = carry return C