Velocity Reviews > C++ > Accelerated C++ exercise

# Accelerated C++ exercise

utab
Guest
Posts: n/a

 02-13-2006
Suppose we wish to find the median of a collection of values. Assume
that we have read some of the values so far, and that we have no idea
how many values remain to be read. Prove that we cannot afford to
discard any of the values that we have read. Hint: One proof strategy
is to assume that we can discard a value, and then find values for the
unread—and therefore unknown—part of our collection that would cause
the median to be the value that we discarded.

As a try;

Lets say we have read so far

5 10 34 72

and we want to read 6 more values as an example

43 32 45 56 78 89

Actually I did not understand what is meant above? Could you please
give an explanation for this problem.

Thx.

Mark P
Guest
Posts: n/a

 02-13-2006
utab wrote:
> Suppose we wish to find the median of a collection of values. Assume
> that we have read some of the values so far, and that we have no idea
> how many values remain to be read. Prove that we cannot afford to
> discard any of the values that we have read. Hint: One proof strategy
> is to assume that we can discard a value, and then find values for the
> unread—and therefore unknown—part of our collection that would cause
> the median to be the value that we discarded.
>
> As a try;
>
> Lets say we have read so far
>
> 5 10 34 72
>
> and we want to read 6 more values as an example
>
> 43 32 45 56 78 89
>
> Actually I did not understand what is meant above? Could you please
> give an explanation for this problem.
>
> Thx.
>

The point is that after you've read n values, if you don't know how many
more are coming, *any* of those n values could be the median depending
upon what's read next. Here's a simple example:

Say you've read {10 20 30}

Suppose the remaining numbers are: {40 50} OR {15 25} OR {0 5}. In each
of these cases, what's the resulting median value?

Diego Martins
Guest
Posts: n/a

 02-14-2006