Median and Order statistics chapter 9.

Problem 9.1-1

We will use tournament sort and keep track of the elements which has a match with smallest element, then find minimum within them will need n-1 comparisons and then in the tournament tree we have \log n numbers to keep track with, comparing in them will need \log n - 1 comparisons. So the total will be as asked n + \log n -1 -1 comparisons .

Problem 9.1-2

As the hint suggests we will make two lists S_{1} and S_{2} . We pairwise compare the elements and store the greater ones in S_{1} and smaller ones in S_{2} . So we need \lfloor n/2 \rfloor comparisons. Now we will find maximum in S_{1} set and minimum in S_{2} set . that will take exactly \lfloor n/2 \rfloor + \lfloor n/2 \rfloor - 2 comparisons. Now If n is odd and one element is left then we have to compare this element with new min and max element, so it will need again 2 for odd .

So if the number is even then we need n/2 + n/2 + n/2 – 2 comparisons or 3 n/2 – 2 on the other hand if it is odd we need 3\lfloor n/2 \rfloor -2 + 2 which makes it 3\lceil n/2 \rceil - 2 comparisons . ( I am not still satisfied with this analysis.. It may contain a flaw )

2012
03/01
CATEGORY
Algorithm Problems
TAGS

Leave a comment

latex test

latex is really important for scientific publications so I am testing latex compatibility in that post .. If this does not work that means I have to find some place else…

\int_0^1 f(x) \, \mathrm{d}x

—- well it works .. I am staying here .. 😀

some more tests

\displaystyle\sum_{n=1}^\infty \frac{1}{n^2} = \frac{\pi^2}{6}

looks like it is buggy but anyway working …cool

 

2011
12/17
CATEGORY
curve-reconstruction algorithms
Leave a comment