I do not understand the meaning of these two statements:
"M can't be negative because when we haven't read in a numbers we can discard a number."
"If M = N +1 then there are no values more to read in so the value of M is not important anymore because N is now known"
so I cannot tell you if they are correct. They make no sense to me.
Hello,
What I trying to say is that M (the numbers which are read in) can't be negative because when you don't have read in any number you can't discard one. Also array's always begin with O.
I assumed that all the numbers are read in of a file. If M is then 1 more then the numbers which are the content of the file then a programm cab't read more values.
So then you know that you have read in all the numbers. If you know that then the value of N is known. Then the value of M is not important anymore.
Roelof
Again, I can't figure out what you are trying to say. You say that "M (the numbers which are read in)..."
M is not the numbers which are read in -- M is how many numbers have been read so far. The numbers themselves are A[0] through A[M-1].
You may think that I am being too picky when I say things like this, but if you are going to try to prove something, it is important to do so in a way that makes it unnecessary for anyone to guess what you are trying to say.
Oke,
Lets rephrase : M can't be negative because you can't count negative numbers.
Also if you don't have to read in any value. You can't discard anything.
When you have nothing, you can't discard anything.
I think the biggest problem is that Englisch is not my home language so sometimes I try to say something and apparently on the wrong way or the wrong words.
Roelof
Roelof
Right. M and N cannot be negative because they are counters -- they represent the number of elements in a set -- and a set cannot have a negative number of elements.
oke,
Then now I have to puzzle out how to prove that sometimes you can discard any number when M < N. When M = N then the median can be calculate bij N/2 when N is a even number and ((N/2)-1 + (N/2)+1)/2) when N is not a even number. Then I can prove it I think.
Roelof
Here is a hint. You have no idea what N is, except that N >= M. In particular, N might be much larger than M. So supppose you discard a single number, say A where 0 <= i < M. Can you imagine a set of values A[M] through A[N-1] that might make the median of A[0] through A[N-1] depend on the value A that you discarded?
yes,
I found a serie of numbers if I understand your question right.
When we have read in the numbers 1,5,8 and image that the unknown numbers are 1,1,5,5,8,8. Then the median of the unknown numbers will be 5. When we discard one 5 of the unknown numbers then the median will still be 5 which is the number that we discarded.
Am I right here ?
Roelof
If you have for example:
1,2,3,4,5,6 = 4+3/2 = 3.5
Then if you miss one number you got for example:
2,3,4,5,6 = 4
or
1,2,3,4,5 = 3
So in most cases the median will be wrong if you discard/miss one number.
Therefore its proved that you cant discard any values.
Hello Andreas,
But if you have this 1,1,1,5,5,5,7,7,7
And you discard any number the median will still be 5,
This proves that on some accosions you can discard a number.
Roelof
Hello Andrew,
What's your opipion about this ?
Roelof
If you can not discard it in some cases then you can not discard it ever, because you do not know what input you will get, as it says in the task.
"This proves that on some occasions you can discard a number."
Indeed it does. But those occasions depend on the numbers you have not yet read.
So, for example, imagine that you have read 1,5,7,9. You cannot discard the 5 because the numbers you have not seen yet might be 2,3,4,6,8. If they are, and you have discarded 5, then you have no way of knowing what the median actually was.
So we have just shown that for this particular input (1,5,7,9), we cannot discard 5.
Your job is to find a similar argument that shows that we cannot discard 1, nor can we discard 7, nor 9.
Then you have to extend the argument to show that for *any* numbers you have read, you cannot *ever* afford to discard *any* of them because the numbers you have not read yet *might* make it necessary to know the value of the number you discarded in order to figure out the median.
This is a subtle kind of argument, but if you spend the effort needed to fill in the details, you will learn quite a bit about how to write a proof.
Oke,
Might I use the whole serie : so 1,5,7,9 and 2.3.4.6.8.
Roelof
Oke,
We have read in the numbers 1,5,7,9,
Assume the numbers we have to read in are 2,3,4,6 and 8.
First we have to sort the values : 1,2,3,4,5,6,7,8,9
The median of this numbers is : 4.5
Now we discard the 1: Now the numbers are 2,3,4,5,6,7,8 and 9.
The median will now be 5. That's different when we don't discard 1
Now we discard the 5. Now the numbers are 1,2,3,4,6,7,8,9.
The median will now be 6. That's also different when we don't discard the 2.
So when N is even. The median will be the value of a[n/2]
When we discard any number then we can calculate the median by using a int.
So we only have the number and not the numbers behind the . so 2.5 will be 2.
Then we can do median = (a[n/2] + a[((n/2)-1)]) / 2
So only if the value of a[n/2] and the value of a[((n/2)-1) and the value of a[(n/2)+1] are equal the median will not change. But because you don't know how many numbers you have to read you never can know the median. So you can't check this.
When N is not even.
then we can calculate the median by using a int.
So we only have the number and not the numbers behind the . so 2.5 will be 2.
Then we can do median = (a[n/2] + a[((n/2)-1)]) / 2
When we discard any number. The median can be found here a[n/2].
Only when a[(n/2)+1)] and a[(n/2)-1)] and a[n/2] are equal then you can discard any numbers. But because you don't know how many numbers you have to read in , you can't calculate the median and you can't check if these numbers are equal.
Roelof
Hello,
Of course when we discard a number n=n-1.
Roelof
Hello Andrew,
Is this correct or do i have to change something ?
Roelof
It seems to me that the question you are trying to answer is a completely different question from the original exercise.
I think you are trying to answer the following question: Suppose we have a set of numbers and we throw one of those numbers away. Prove that the median of the reduced set (i.e. the set of numbers after we discarded one of them) will not always be the same as the median of the original set.
This is a very easy claim to prove, because in order to prove it, all you have to do is find one example--as you have done.
But it has nothing to do with the original problem. The original problem asks you to prove that there is no way to find the median of the original set no matter what you do. So any answer you give that talks about taking the median of the set after you have discarded a value is wrong, because it does nothing to prove that you might not be able to find the median of the original set in some other way.
Hello Andrew,
Then I'm giving up.
As far as i know you can only calculate the median of a set by using the formula that we are using. But that's not proving that such a method does not exsist.
So I don't know any way i can prove that. For my feeling this is more a math question that a logical question.
But I want to thank you for the help so far.
Roelof
The way to know that such a method does not exist is to show that the values of A{M] through A[N-1] might be such that you cannot find out what the the median of A[0] through A[N-1] is without using the value that you threw away.
In other words, suppose you have already read A{0] through A[M-1] and you have not read A[M] through A[N-1]. Suppose further that you intend to discard A{i], with 0 <= i < M. Then what you need to prove is that it is always possible to find a single value x, together with values for A[M] through A[N-1] with the property that
the median of A[0] through A[N-1]
is not equal to
the median of (A[0] through A[i-1]), x, (A[i+1] through A[N-1])
Notice that in the process of finding these values, you can also determine the value of N. In other words, you can put as many values in A[M] through A[N-1] as you like.
Once you have figured out how to do this, you have solved the problem, because if the median of A[0] through A[N-1] depends on a number that you have thrown away, there is no way to figure out what that median might have been without knowing the discarded number.
I will leave as an exercise the problem of determining appropriate values for x and A[M] through A[N-1].
This problem is somewhat strange, in that it asks you to prove the obvious: That you need simultaneous access to the full dataset in order to compute its median. Normally, it is the opposite claim that should require proof, that is to say, that it is possible to compute the median of the dataset while only storing some "compressed" version of the information available in the complete dataset.
In any case, suppose that at any given point you know the first M values, sort them and throw away the Nth (N<=M). Then you have M-N remaining numbers to the "right" of the discarded value and N-1 remaining numbers to the left. There are three possibilities:
1) N-1>M-N then if the unknown set comprises 2N-M-1 values larger than the value discarded, the median is the value discarded and there is no way to find it.
2) N-1<M-N then if the unknown set comprises M-2N+1 values smaller than the value discarded, the median is the value discarded and there is no way to find it.
3) N-1==M-N, then if the unknown set comprises an equal number of larger and smaller values than the value discarded, the median is the value discarded and there is no way to find it.
Thus, there can always be a set of hidden values that make it so that the discarded value is required in order to compute the median.
8 years later....I will give a try.
Said that we have already read numbers which sorted sequence is (0, 1, 2, 3, 4, 5). Said that we still have 3 more numbers to read (6, 7, 8). The mean value of the complete vector would be 0, 1, 2, 3, (4), 5, 6, 7, 8. Number 4 is part of the already read numbers. This means that we can not discard any already read number as it can potentially be part of the source number/s for the mean calculation.
We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.