(i) Consider the following code:

int myFunc(int A[], int n)

{

    int i, j, max = 0;

    int msis[n];



    for ( i = 0; i < n; i++ )

        msis[i] = A[i];



   for ( i = 1; i < n; i++ )

        for ( j = 0; j < i; j++ )

            if (A[i] > A[j] &&

                msis[i] < msis[j] + A[i])

                msis[i] = msis[j] + A[i];



    for ( i = 0; i < n; i++ )

        if ( max < msis[i] )

            max = msis[i];

  return max;

}

a)     What is the time complexity of the algorithm?

b)     Consider the following array values and apply quick sort on it. Only dry run is required but you have to show all steps:

10       3         8         5         12       2         15       4         1

(ii) Once there was a competition between expert algorithm designers / programmers to develop a best sorting algorithm / application. One of the genius algorithm designers won the competition. Try to come-up with a possible logic (algorithm or combination of algorithms) the designers might have developed in order to won the competition. Give argument / reasons that why the algorithm (or combination of algorithms) is the best.

pur-new-sol

Related Questions