Quiz ans discussion

[minal]

3. The code for the Insertion Sort algorithm discussed in the class is
reproduced below:

1. InsertionSort(A, n) {
2. for i = 2 to n {
3. key = A[i]
4. j = i - 1;
5. while (j > 0) and (A[j] > key) {
6. A[j+1] = A[j]
7. j = j – 1
8. }
9. A[j+1] = key
10. }
11. }

if in line number 5, while(j > 0)and(A[j] > key)statement is replaced
by the statement while(j > 0)and(A[j] >= key) then what would happen
to time complexity of the algorithm? Justify your answer.

a. Time complexity will remain unchanged
b. Best case performance will change, worst case performance will not
change
c. Worst case performance will change, best case performance will not
change
d. Both worst case performance and best case performance will change

ANS:
ans is a if input is not containing any duplicate element.
and ans is d. if we are considering that the input is containing
duplicate element
in worst case as well as in the best case number of comparisons are
geting increase which is proportional to the two factors
1. how many elements are duplicate
2. number of occurances of each element present in the input.
after changing the condition insertion sort will not remain the stable
sort


4. If there exists three known algorithms to solve a problem having
time complexity of O(nlogn), O( n2)and O(n3/2). Then the Upper bound
and Lower bound for solving the problem can be defined as given below.
Justify your answer.

a. Upper bound will be O(nlogn) and lower bound will be O( n2)
b. Upper bound will be O( n2) and lower bound will be O(nlogn)
c. Upper bound will be O(nlogn) and lower bound cannot be decided
d. There is not enough information to decide on upper and lower bound

ANS:

b
as the growth rate is nlogn, pow(n,1.5), pow(n,2)


5. Consider the recursive function given below:

int calc (int x, int y)
{
if y == 1
return x;
else
calc(x, y-1) + x;
}
Assuming that the invocation call is calc (a,n) where a and n are
positive integers, what result does the function return? Justify your
answer.

a. a * (n-1)
b. a * n
c. a + n
d. an

ANS: c
as function calc will get called n-1 time irrespective of what is the
value of x. suppose time required to do the summation calc(x,y-1)+x is
some constant time a.
then total time requirement will be a+ n

[Venky]

Hi Minal,

First of all let me congratulate you for taking initiative to answer
questions. Question no. 3 is a teaser. In a way you have got the
essence of the question. But this is my argument and explanation. I
would also like others to argue and see if there are any holes in my
justification.

The best or the worst performance of the algorithm depends on the data
that it encounters. For the original Insertion sort algorithm- the
best performance (which is O(n)) will happen when it encounters
already sorted data (in ascending order in this case). This includes
the case when all the elements are the same. But when you make
modifications and replace the statement while(j > 0)and(A[j] > key)
with while(j > 0)and(A[j] >= key) , the best performance will not
happen in the case when all elements are equal. In fact worse
performance will happen in this case (which is O(n^2)) because it will
unnecessarily try and sort the data. But in case all elements are
distinct in ascending order, the best performance (which is O(n)) will
take place. The first algorithm is superior because it not doing any
redundant work. But as far as the best performance and the worst
performance is concerned, it will not change. I do not want to make
any assumption about the dataset. Therefore the answer is a).

Amit I have included your name in the group so that you can play the
role of a refree. Do you think my justification is correct? I am
inviting comments from all.

Minal, your answers to Q4 and Q5 are wrong. Anybody would like to help
Minal?

Venky

[reena pagare]

hi all,

 

if i want to analyze two algorithms what are the parameters i need to consider. can any one give me a link to any Journal paper for the same.

I need to analyze the algorithm to prove that among the set of three algorithm one of them is the optimized algorithm.

 

Regards,

Reena Pagare

[Venkatesh Kamat]

Hi Reena,

 

Two algorithms are compared for performance on Space & Time parameters. The Big-O notation can be used to analyze both space as well as time requirement. Often there is a trade-off between space & time requirement. So, when you are talking about optimal algorithm - you are comparing known algorithms using their worst performance and choosing the one having the best performance among them. The lower bound on a problem is theoretically the best performance that you can ever have (its like a limit on the best performance). But you may not have discovered an algorithm that can give that lower bound.  Lower bound needs to be proved and often it may not be easy. This material you will find in any book on algorithm.

 

Hope this explanation is sufficient at the moment. Any comments?

Venky