Question

fundamental algorithm

AllLessThan1 (int C A, B) return bool for (i-1 to |AI) for (j-1 to B if (A[1] >=B[j]) return FALSE ; return TRUE; AllLessThan2 (int[] A,B) return bool largeAA[1] for (i 2 to |AI) if (A[i] > largeA) largeA A[i]; for (j = 1 to IBD if (largeA >= B[j]) return FALSE; return TRUE; C. For any particular arrays A, B, let ti(A, B) and t2(A, B) be the running times of the two algo- rithms for inputs A, B. Design an algorithm AllLessThan3 (A, B) that has a running time that is no more than 2 min(h (AB), t2(A,B)) for every input A, B.

Answer 1

AllLessThan3(int [] A, B) return bool {

      largeA = A[1]

      for(i = 2 to |A|)

if(A[i] > largeA) largeA = A[i];

       smallB = B[1]

       for(i = 2 to |B|)

            if(B[i] < smallB) smallB = B[i];

       if(largeA >= smallB) return FALSE;

       return TRUE;

}

In this algorithm we are finding largest number in A (say largeA) and smallest number in B (say smallB) . The function will return true if and only if all numbers in A are smaller than all numbers in B. So even largest number (largeA) in A should be smaller than smallest number in B (smallB). Else if largeA is greater than or equal to smallB, function will return false.