2.11 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.12
Rewrite the INSERTION SORT procedure to sort into nonincreasing
instead of nondecreasing order.
Solution:
InsertionSort(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.13
Consider
the searching problem:
Input: A sequence
of n numbers A=<a_{1},a_{2},...,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:
LinearSearch(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 ith
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
ith iteration, the subarray
A[1..i]
will not contain v before the
next iteration (unless ith
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
2.14
Consider the problem of adding two nbit binary integers, stored in
two nelement
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:
A=<a_{1},a_{2},...,a_{n}> and
B=<b_{1},b_{2},...,b_{n}>.
Output: A (n+1)bit
binary integer stored in (n+1)element
array of binary digits (either 0 or 1) C=⟨c_{1},c_{2},...,c_{n}+1⟩
such that C=A+B.
BinaryAdd(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
No comments :
Post a Comment