Please guys, this is not a homework question, this is an old exam question and I
ID: 3558829 • Letter: P
Question
Please guys, this is not a homework question, this is an old exam question and I would like to know its solution. PLEASE solve it if you're 100% sure you know what you are doing.
I.(40 points) Basic Concepts in Algorithmic Analysis
1.(20 points) The following algorithm finds the kth smallest integer in an unordered array of integers
int selectKth (int a[], int k, int n) {
int i, j, min_i, tmp;
for (i = 0; i < k; i++) {
min_i = i;
for (j = i+1; j < n; j++) {
if (a[j] < a[min_i])
min_i = j;
}
tmp = a[i];
a[i] = a[min_i];
a[min_i] = tmp;
}
return a[k-1];
}
a.(8 points) Find the number of element comparisons that are carried out by the algorithm.
b.(6 points) Find the number of element assignments that are carried out by the algorithm.
c.(6 points) Express the complexity of the algorithm in terms of () notation when finding the largest element in the array. Is it an efficient way of finding the largest element? Justify your answer.
Explanation / Answer
We have two for loops. Outer for loop goes from i=0 to i=k-1 and inner for loop goes from j=i+1 to j=n-1
(a)- at the worst case every time an element would be compared. At first iteration n-1 elements would be compared. At second iteration n-2 elements would be comapred and this elemet comparison will reduce by one until outer loop ends. And outer loop runs k times. (i=0 to i=k-1)
so total number of comparisons performed by this algorithm =
(n-1)+(n-2)+(n-3)+...........(n-k)
= (nk)-k*(k+1)/2
(b)- we can see at every iteration of outer loop only one swap operation is performed.
So number of elements assignments= k
(c) this array would take O(nk-k2) time to find k smallest elements. and the same time would be taken to find the kth largest element. And this way is not better. We can do it in O(n+klogn) time if we make an max-heap out of given array in log(n) time and then pick 1 largest element each time till k iterations.