Question

1) Use insertion sort to sort: 25, 17, 31, 13, 2. Show your work step-by-step.

2) Use Euclidean algorithm to find gcd(248, 198)

3) (ABCDEF)₁₆ to binary, octal and decimal

Answer 1

1) Use insertion sort to sort: 25, 17, 31, 13, 2. Show your work step-by-step.

Ans.

1. The first step involves the comparison of the element in question with its adjacent element.
2. And if at every comparison reveals that the element in question can be inserted at a particular position, then space is created for it by shifting the other elements one position to the right and inserting the element at the suitable position.
3. The above procedure is repeated until all the element in the array is at their apt position.

Let us now understand working with the following example:

Consider the following array: 25, 17, 31, 13, 2

First Iteration: Compare 25 with 17. The comparison shows 17< 25. Hence swap 17 and 25.

The array now looks like:

17, 25, 31, 13, 2

Second Iteration: Begin with the second element (25), but it was already swapped on for the correct position, so we move ahead to the next element.

Now hold on to the third element (31) and compare with the ones preceding it.

Since 31> 25, no swapping takes place.

Also, 31> 17, no swapping takes place and 31 remains at its position.

The array after the Second iteration looks like:

17, 25, 31, 13, 2

Third Iteration: Start the following Iteration with the fourth element (13), and compare it with its preceding elements.

Since 13< 31, we swap the two.

Array now becomes: 17, 25, 13, 31, 2.

But there still exist elements that we haven’t yet compared with 13. Now the comparison takes place between 25 and 13. Since, 13 < 25, we swap the two.

The array becomes 17, 13, 25, 31, 2.

The last comparison for the iteration is now between 17 and 13. Since 13 < 17, we swap the two.

The array now becomes 13, 17, 25, 31, 2.

Fourth Iteration: The last iteration calls for the comparison of the last element (2), with all the preceding elements and make the appropriate swapping between elements.

Since, 2< 31. Swap 2 and 31.

Array now becomes: 13, 17, 25, 2, 31.

Compare 2 with 25, 17, 13.

Since, 2< 25. Swap 25 and 2.

13, 17, 2, 25, 31.

Compare 2 with 17 and 13.

Since, 2<17. Swap 2 and 17.

Array now becomes:

13, 2, 17, 25, 31.

The last comparison for the Iteration is to compare 2 with 13.

Since 2< 13. Swap 2 and 13.

The array now becomes:

2, 13, 17, 25, 31.

This is the final array after all the corresponding iterations and swapping of elements.

2) Use Euclidean algorithm to find gcd(248, 198)

Ans.

Euclidean Algorithm for finding GCD(A,B) is as follows:

• If A = 0 then GCD(A,B)=B, since the GCD(0,B)=B, and we can stop.
• If B = 0 then GCD(A,B)=A, since the GCD(A,0)=A, and we can stop.
• Write A in quotient remainder form (A = B⋅Q + R) : Q=quotient, R=remainder
• Find GCD(B,R) using the Euclidean Algorithm since GCD(A,B) = GCD(B,R)

• A=248, B=198
• A ≠0
• B ≠0
• Use long division to find that 248/198 = 1 with a remainder of 50. We can write this as:
• 248=198*1+50
• Find GCD(198,50), since GCD(248,198)=GCD(198,50)

A=198, B=50

• A ≠0
• B ≠0
• Use long division to find that 198/50 = 3 with a remainder of 48. We can write this as:
• 198 = 50 * 3 + 48
• Find GCD(50,48), since GCD(198,50)=GCD(50,48)

A=50, B=48

• A ≠0
• B ≠0
• Use long division to find that 50/48 = 1 with a remainder of 2. We can write this as:
• 50 = 48 * 1 + 2
• Find GCD(48,2), since GCD(50,48)=GCD(48,2)

A=48, B=2

• A ≠0
• B ≠0
• Use long division to find that 48/2 = 24 with a remainder of 0. We can write this as:
• 48 = 2* 24 + 0
• Find GCD(2,0), since GCD(48,2)=GCD(2,0)

A=2, B=0

• A ≠0
• B =0, GCD(2,0)=2

So

GCD(248,198) = 2

3) (ABCDEF)₁₆ to binary, octal and decimal

To Binary : (ABCDEF)16

Step 1 : Convert the decimal equivalent of each hexadecimal digit to 4 binary digits.

Step 2 : Combine the binary groups

is the answer.

To Octal:

Step 1: First the individual digits are converted into its binary bits(each having 4 bits)

A B                         C                    D E F

  1010 1011                  1100                 1101 1110 1111

Step 2: After that the subsequents bits are grouped into 3 bits.If.they are unable to form group of 3 the zero padding is done from the left.

101 010 111 100     110 111 101 111

Step 3: After that simply we convert the binary bite to its equivalent octal number.

101   010   111    100    110    111    101     111
 5     2     7      4      6      7      5       7
So, (ABCD)16   =(52746757)8       
To decimal : (ABCDEF)16

To decimal

Multiply each digit of the hex number with its corresponding power of 16( F=16^0, E=16^1,D=16^2........ A=16^5 )
=(Ax165+Bx164+Cx163+Dx162+Ex161+Fx160)
 Since A=10,B=11,C=12,D=13,E=14,F=15 
= (10x165+11x164+12x163+13x162+14x161+15x160)10

= (10485760+720896+49152+3328+224+15)₁₀

= (11259375)₁₀ is answer.