1. Compare the performance by computing the time (in hrs, min, sec) taken by two machines A and B. A executes 108 instr./sec and B executes 105 instr./sec. A runs bubble sort with c1=5 and B runs insertion sort with c2=5. Both are given an array of sorted input of size 1 billion numbers.

2. Is the following sorting algorithm stable. Give exact reason for your answer.

for i=1 upto n-1

for j=n downto i+1

if(A[j]

Swap A[j] with A[j-1]

3. Prove or disprove the following: 4n2-5n+3 is O(n)

4. Sorting the following array A using MergeSort goes through the following intermediate sequence ordered from 1 to 7. Identify and fix if you find any problem in this timing sequence. A = [9, 4, 8, 1, 7, 3, 5, 2]

Time sequence:

1. [4, 9, 8, 1, 7, 3, 5, 2]

2. [4, 9, 1, 8, 7, 3, 5, 2]

3. [1, 4, 8, 9, 7, 3, 5, 2]

4. [1, 4, 8, 9, 3, 7, 5, 2]

5. [1, 3, 4, 7, 8, 9, 5, 2]

6. [1, 3, 4, 7, 8, 9, 2, 5]

7. [1, 2, 3, 4, 5, 7, 8, 9]