CLRS Chapter 2 Solutions

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 of Insertion-Sort on the array A = [31, 41, 59, 26, 41, 58]

Well you can do it by yourself.

2.1.2 Rewrite the Insertion-Sort procedure 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 of n numbers A = [a1, a2, a3……an] and a value v .

Output: And index i such that v = A[i] or a special value NIL if v is not found in A.

Write the 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.

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
Advertisements