Chapter 2.1

1E

2E

3E

Pseudocode for Linear Search

The pseudocode for linear search, it scans the sequence for v using a loop invariant:

Input: A sequence of n numbers and a value v.

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

Linear Search (A, v)

1 for i =1 to n

2 {

3 if A[i] = v

4 return i

5 }

6 return NIL

Three properties hold for linear search:

• Initialization: It will start by presenting the loop invariant holds before the first loop iteration, when i = 1, the sub array A [1…n]. Therefore, consists of just the single element A [1], which is in fact original element in A [1]. Moreover, this sub array is searched, which shows that the loop invariant holds prior to the first iteration of the loop.

• Maintenance: Each iteration maintains the loop invariant. Informally the body of the outer for loop works by moving A [1], A [2], .and soon by one position to the right until the proper element found for v in if loop. The second property satisfies.

• Termination: Finally, for linear search, the outer for loop ends, when i exceed n+1. Substituting n+1 for i in the wording of loop invariant, Hence, the searched element found, which means that the algorithm is correct.

4E

Suppose andare 2 integer arrays to store binary equivalent of two decimal numbers. Each of these arrays can store n bits.

Suppose is another array to store the binary addition of A and B array. The length of this array is 1 more than A and B array because it may possible the addition can give one more value in the array.

Logic:

• Start fetching the elements of both A and B array from last index to 0^th index.

• Add i^th bits (that is i^th element) of both A and B array. When i^th bit of both array are 1 then place 0 at the i+1^th position in C array and put 1 in the carry forward.

• When i^th bits of both A and B array are added then it is also necessary to check whether there is any carry to i^t^h bit from i + 1 bit.

Pseudo code:

BINARY-ADDITION