How to write algorithm?

Question

The median of an ordered set is an element such that the number of elements less than the median is within one of the number that are greater, assuming no ties.
a. Write an algorithm to find the median of three distinct integers a, b, and c.
b. Describe D, the set of inputs for your algorithm.
c. How many comparision does your algorithm do in the worst case? On the average?

Answer 1

The above poster is correct, but I think it can be done with an average of 8/3 comparisons.

First compare a,b then compare b,c. If b lies between a and c, then b is the median and we are done after 2 comparisons.

Otherwise, b is either largest or smallest, and we need to compare a and c to find out which is the median. Thus in these cases 3 comparisons are needed.

To find the average number of comparisons, notice that the probability b is the median is 1/3 (since all elements are equally likely to be the median), so the expected number of comparisons is: (1/3)*2 + (2/3)*3 = 8/3.

Note that in finding the median, we have also sorted the elements. However for larger sets, it is not necessary to sort the elements -- we can find the median more quickly in other ways (eg: algorithms by Hoare, and by Blum et al)

Answer 2

D = {a, b, c}, a <> b <> c <> a

This algorithm should return the middle element of three different numbers.

if (a < b) then
if (a < c) then
if (b < c) then return b else return c
else return c
else
if (b < c) then
if (c < a) then return c else return a
else return b

2 ifs at least, 3 at most. Try it in a computer to check any errors, please. I wrote from memory.

Bonus homework: generalize from 3 elements to an array of n elements. Hint: sort the array first.

Answer 3

I don't know much of the pascal language, but the basic concept is: for N in 10 do read input input -> radius[N] end for N in 10 do print { π * radius[N] * 2 } print { π * radius[N] * radius[N] } end