Sample Solutions for Lab 6
Question 1: Minimum in a Rotated Sorted Array
Idea:
We narrow down the segment of the array where the searchedfor
element can occur until we a have a oneelement 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
thatA[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 worstcase 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 k1;
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: Kth 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: kth 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 kth smallest element of A is in the segment A[l..r] OUTPUT: kth 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 kth 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,m1);
Note that the actions in the code guarantee that for each recursive call, the kth 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.