Sample Solutions for Lab 6


Question 1: Minimum in a Rotated Sorted Array

Idea:
We narrow down the segment of the array where the searched-for
element can occur until we a have a one-element array. Then we return
the current position. It may be that we find the minimum earlier.
Then we return it before the segment has shrunk to length 1.

In each recursive step, we have a segment A[l..r]. We choose a
midpoint m. Then the minimum is either in A[l..m], or in A[m+1..r].

We have to find out in which of these two segments we can find the
minimum. We have two segments of the form A[j..k]. We distinguish
between the segment without the minimum and the one with the minimum.

In summary, we can recognize the segment with which to continue as
follows:

Case Analysis:

A[l] > A[m]:  continue with A[l..m]  
              // the cliff from max to min is in the segment
A[m+1] > A[r]: continue with A[m+1..r]
              // the cliff from max to min is in the segment
else // there is no cliff, that is, 
     // A[l] <= A[m] and A[m+1] <= A[r]
     // then the minimum is at the beginning of one of the segments
if A[l] < A[m+1] 
    then return l;
else return m+1;

Recursive version:

INPUT: rotated array A
OUTPUT: minimum in A

int minRotated(A)
   return minRotatedRec(A,1,A.length);



INPUT: rotated array A, 
    integers l, r such that l < r and the minimum is in A[l..r]
OUTPUT: minimum in A[l,r]

int minRotatedRec(A,l,r)
   if l=r
      then return l;

   m:= floor((r+l)/2);

   if A[l]>A[m]
      then return minRotatedRec(A,l,m);
   else if A[m+1] > A[r]
      then return minRotatedRec(A,m+1,r);     
   else if A[l] < A[m+1]
      then return l;
   else return m+1;

Iterative version:

INPUT: rotated array A
OUTPUT: minimum in A

int minRotatedIter(A)
   l:=1; 
   r:=n;
   while l < r do
      m:= floor((r+l)/2);
   if A[l]>A[m]
      then r:=m;
   else if A[m+1] > A[r]
      then l:=m+1;
   else if A[l] < A[m+1]
      then return l;
   else return m+1;

The running time for both algorithms is theta(log(n)).
We can find that by solving the recursion

T(n) = T(n/2) + theta(n^0)

using the Master Theorem with the parameters a=1, b=2, c=0.


Question 2: Intersection of Arrays

The straightforward solution (indicated by “SF”) compares every
element in A with every element in B.

INPUT:  arrays A, B 
OUTPUT: array C that is the intersection between A and B

int[] intersectionSF(int[] A, int[] B)
  minlength := min(A.length, B.length);
  D := new int[minlength];
  int n := intersectionSFAux(A,B,D);
  // returns the length of the intersection
  // and writes the intersection into D
  C := copy(D,n);
  // copies the part of D that contains the intersection
  // into a new array of length n
  return C;

Here, intersectionSFAux returns the length of the intersection and
writes as side effect the intersection into D. Then copy copies the
first n elements of D into C.

First the pseudocode for copy:

INPUT:  array D, size n
OUTPUT: array C that is the copy of the first n elements in D

int[] copy(int[] D, n)
  int[] C := new int[n];
  for i:=1 to n do
    C[i] := D[i];

Now the pseudocode for intersectionSFAux:

INPUT:  arrays A, B
OUTPUT: array D that is the intersection between A and B (and that may contain also possibly unallocated places at the end)

int intersectionSFAux(A,B,D)
  k := 1;
  for i:=1 to A.length do
    j := 1;
    while j <= B.length and A[i] != B[j] do
      j++;
      if j<= B.length
        then D[k] := A[i];
             k++;

Clearly, this algorithm has a worst-case running time of theta(n^2).

We can do better by first sorting A and B. Then intersectionAux walks
through them in parallel. Otherwise, the clever algorithm is like the
straightforward one.

INPUT:  array A,array A
OUTPUT: array C that is the intersection between A and B
(efficient version)

int[] intersection(int[] A, int[] B)
  minlength := min(A.length, B.length)
  D := new int[minlength];
  int n := intersectionAux(A,B,D);
  C := copy(D,n);
  return C;

Now, we show the implementation of intersectionAux. As the previous
version, also this one returns the length of the intersection and
writes as side effect the intersection into D.

INPUT:  array A, array B
OUTPUT: array D that is the intersection between A and B (and that may contain also possibly unallocated places at the end)
(efficient version)

int intersectionAux(A,B,D)
  heapSort(A); 
  heapSort(B);

  int i := 1; 
  int j := 1;
  int k := 1;

  // copy common elements into D 
  // as long as A and B are not exhausted
  while i <= A.length and j <= B.length do
    // find the next common element
    // by moving i and j to same value in A and B
    while i <= A.length and j <= B.length and A[i] != B[j] do
      if A[i] < A[j]
         then i++;
         else j++;
      if i <= A.length and j <= B.length 
      // the loop condition failed because A[i] != B[j] failed,
      // that is, a common element was found
          then D[k] := A[i]
          i++; j++; k++;
  // the condition failed because one of A, B was exhausted,
  // the variable k, however, points to the next position in D
  // where common elements could be inserted

  return k-1;

The running time of this version of intersectionAux is theta(n.log n) for
the sorting, followed by theta(n) for the parallel scan. The overall running time of intersection, which also includes the call to copy, is therefore theta(n.log n)


Question 3: K-th Smallest Element in an Array

We start immediately with the more clever version, often called
quickselect. The idea is again to keep a segment A[l..r] that contains
the element we are looking for. One should note that in an
application, one may want to first copy A into an auxiliary array,
since quickselect destroys the order of A.

INPUT:  array A, number k
OUTPUT: k-th smallest element in A

int select(A,k)
  return quickselect(A,k,1,A.length);


INPUT:  array A, number k, indices l, r such that 
     the k-th smallest element of A is in the segment A[l..r]
OUTPUT: k-th smallest element in A

int quickselect(A,k,l,r)

  if l=r
    // the segment A[l..r] has only one element, which must be
    // the k-th smallest element of A, according to the input condition
    then return A[l];

  m := partition(A,l,r);
  if m = k
     then return A[m];
  else if k > m
     then return quickselect(A,m+1,r);
  else return quickselect(A,l,m-1);

Note that the actions in the code guarantee that for each recursive call, the k-th smallest element of A is in the segment A[l..r].

Under the assumption that the selection always takes place more ore
less in the middle, the running time satisfies the recurrence

T(n) = T(n/2) + theta(n)

The parameters to plug into the formula of the Master Theorem are
therefore

a = 1, b = 2, c = 1.

That gives the comparison

log_b a = log_2 1 = 0 < 1 = c.

That is, c wins and the overall running time is theta(n^1) = theta(n).

As for quicksort, a situation where the worst case occurs is the one where A is sorted. If then we ask for the n-th greatest element, that is, the maximum, the running time is quadratic.