# 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.

• The segment without the minimum definitely contains an ascending
sequence of numbers. As a consequence, it satisfies the inequality
`A[j] <= A[k]`.

• The segment with the minimum may also contain the maximum or may
not.

• If it contains the maximum, then the maximum appears immediately
before the minimum (that’s like a cliff), and the sequence of
numbers is not ascending. In particular, it has the property
that `A[j] > A[k]`, which the other segment does not have.

• If it does not contain the maximum, then `A[j]` is the minimum and
`A[j]` is less than the first element of the other segment.

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.