Divide & Conquer

Numerical answer

Single correct

• A$\Theta(n)$
• B$\Theta(1)$
• C$\Theta(\log^2 n)$
• D$\Theta(\log n)$

Single correct

• A$t > 2n - 2$
• B$t > 3\left\lceil \frac{n}{2} \right\rceil$ and $t \le 2n - 2$
• C$t > n$ and $t \le 3\left\lceil \frac{n}{2} \right\rceil$
• D$t > \lceil \log_2(n) \rceil$ and $t \le n$

Answer key coming soon

Single correct

• A$\Theta(\sqrt{n})$
• B$\Theta(\log_2(n))$
• C$\Theta(n^2)$
• D$\Theta(n)$

Answer key coming soon

Numerical answer

Single correct

• A$O(n)$
• B$O(n \log n)$
• C$O(n^2)$
• D$\Omega(n^2 \log n)$

Numerical answer

Answer key coming soon

int partition(int a[], int n);

int kth_smallest(int a[], int n, int k)
{
    int left_end = partition(a,n);

    if ( left_end+1 == k ){
        return a[left_end];
    }

    if ( left_end+1 > k ){
        return kth_smallest( ____________ );
    } else {
        return kth_smallest( ____________ );
    }
}

Single correct

• A(a, left_end, k) and (a+left_end+1, n-left_end-1, k-left_end-1)
• B(a, left_end, k) and (a, n-left_end-1, k-left_end-1)
• C(a+left_end+1, n-left_end-1, k-left_end-1) and (a, left_end, k)
• D(a, n-left_end-1, k-left_end-1) and (a, left_end, k)

Numerical answer

int ProcessArray(int *listA, int x, int n)
{
    int i, j, k;
    i = 0;
    j = n-1;
    do {
        k = (i+j)/2;
        if (x <= listA[k])
            j = k-1;
        if (listA[k] <= x)
            i = k+1;
    }while (i <= j);

    if (listA[k] == x)
        return(k);
    else
        return -1;
}

Single correct

• AIt will run into an infinite loop when x is not in listA.
• BIt is an implementation of binary search.
• CIt will always find the maximum element in listA.
• DIt will return −1 even when x is present in listA.