Accelerated C++ exercise

Discussion in 'C++' started by utab, Feb 13, 2006.

  1. utab

    utab Guest

    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.
     
    utab, Feb 13, 2006
    #1
    1. Advertising

  2. utab

    Mark P Guest

    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?
     
    Mark P, Feb 13, 2006
    #2
    1. Advertising

  3. no homeworks, please :(
     
    Diego Martins, Feb 14, 2006
    #3
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Pete
    Replies:
    14
    Views:
    933
    Roland Pibinger
    Jan 3, 2006
  2. utab
    Replies:
    3
    Views:
    395
  3. utab
    Replies:
    8
    Views:
    539
    Default User
    Apr 16, 2006
  4. arnuld
    Replies:
    10
    Views:
    757
  5. Xernoth
    Replies:
    10
    Views:
    1,077
    James Kanze
    Apr 15, 2007
Loading...

Share This Page