patternModerate
Proof of correctness of algorithm to determine whether the elements of an array are repeated an equal number of times
Viewed 0 times
thenumberelementsrepeatedarrayareequalcorrectnessalgorithmdetermine
Problem
I apologize for the long title, but I really didn't know how to write it different without lacking informations about the content.
I recently had an university exam about Parallel Algorithms. One exercise asked me to write an algorithm to determine if the elements of an array, let's call it
For example:
1)
2)
I had to write the algorithm for a particular model of parallel computing, a PRAM: the model required me to use some techniques to avoid read/write conflicts, and other problems, but this is not relevant. What I ended up with was a new array, let's call it
For example:
1)
2)
As you might think and expect, the only thing left to do would be to check if every element of
So, to check if all the elements of
Taking the example above:
1)
2)
I know it's absurd, but that's what I came up to.
I checked this approach with a lot of different combinations of arrays/numbers, and it seems to work. Thing is, I'm having an hard time in finding a (mathematical) proof that the algorithm is
I recently had an university exam about Parallel Algorithms. One exercise asked me to write an algorithm to determine if the elements of an array, let's call it
A, were repeated an equal number of times.For example:
1)
A = 1 8 8 1 8 1 1 8 : the answer is yes, every number is repeated 2 times.2)
A = 7 8 8 5 5 4 7 8 : the answer is no.I had to write the algorithm for a particular model of parallel computing, a PRAM: the model required me to use some techniques to avoid read/write conflicts, and other problems, but this is not relevant. What I ended up with was a new array, let's call it
B, which I can define as follow: Given the array A, B[i] contains the number of repetitions of the element A[i] within A.For example:
1)
A = 1 8 8 1 8 1 1 8B = 4 4 4 4 4 4 4 42)
A = 7 8 8 5 5 4 7 8B = 2 3 3 2 2 1 2 3As you might think and expect, the only thing left to do would be to check if every element of
B is equal to the other, but.. it turns out I'm masochist, and the pressure of the exam (plus I had a bit temperature) led me to take another path. Moreover, comparing elements of an array is not immediate using this computing model.So, to check if all the elements of
B are the same, I summed all of them and divided the result by the number of elements of B: if the result was equal to an element of B (for example the first, B[0]) then the algorithm returned true (false otherwise).Taking the example above:
1)
sum = 4 + 4 + 4 + 4 + 4 + 4 + 4 + 4 = 32 --> 32 / 8 = 4 = B[0] --> Yes.2)
sum = 2 + 3 + 3 + 2 + 2 + 1 + 2 + 3 = 18 --> 18 / 8 ≠ 2 = B[0] --> No.I know it's absurd, but that's what I came up to.
I checked this approach with a lot of different combinations of arrays/numbers, and it seems to work. Thing is, I'm having an hard time in finding a (mathematical) proof that the algorithm is
Solution
No, your algorithm doesn't work. Consider if the array A is
A = [1 1 1 1 1 2 2 3 3 3 3 3 3].
Then the array B will be
B = [5 5 5 5 5 2 2 6 6 6 6 6 6].
The sum of B will be 65, and the length of B will be 13, so after division, we'll get the number 5. This is equal to the first element of B, so your algorithm will output "Yes". Nonetheless, not all elements of B are the same, and the correct answer is "No". So, your algorithm gives the wrong output on this case.
Nice try, though! Figuring out how to build B was probably the hardest part of this problem.
How I found this: I couldn't find a counterexample with two distinct numbers, so next I tried with three distinct numbers. Let $u,v,w$ denote how often each of those numbers appear. Then the array will have length $u+v+w$, and B will contain the value $u$ repeated $u$ times, the value $v$ repeated $v$ times, and $w$ repeated $w$ times, so the sum of elements of B is $u^2+v^2+w^2$. We can find a counterexample if we can find a solution over the positive integers to the Diophantine equation
$${u^2 + v^2 + w^2 \over u+v+w} = u$$
such that $v\ne u$ or $w \ne u$. This is equivalent to
$$u^2 + v^2 + w^2 = u(u+v+w),$$
where $u,v,w$ are positive integers and either $v\ne u$ or $w \ne u$. I then picked a few small values of $u$ and tried solving this Diophantine equation using Wolfram Alpha. The first solution I stumbled across was $u=5$, $v=2$, $w=6$, but there are many others as well. In retrospect I guess I could have simplified further to
$$v^2 + w^2 = uv + uw$$
but I didn't notice and it turned out not to matter.
A = [1 1 1 1 1 2 2 3 3 3 3 3 3].
Then the array B will be
B = [5 5 5 5 5 2 2 6 6 6 6 6 6].
The sum of B will be 65, and the length of B will be 13, so after division, we'll get the number 5. This is equal to the first element of B, so your algorithm will output "Yes". Nonetheless, not all elements of B are the same, and the correct answer is "No". So, your algorithm gives the wrong output on this case.
Nice try, though! Figuring out how to build B was probably the hardest part of this problem.
How I found this: I couldn't find a counterexample with two distinct numbers, so next I tried with three distinct numbers. Let $u,v,w$ denote how often each of those numbers appear. Then the array will have length $u+v+w$, and B will contain the value $u$ repeated $u$ times, the value $v$ repeated $v$ times, and $w$ repeated $w$ times, so the sum of elements of B is $u^2+v^2+w^2$. We can find a counterexample if we can find a solution over the positive integers to the Diophantine equation
$${u^2 + v^2 + w^2 \over u+v+w} = u$$
such that $v\ne u$ or $w \ne u$. This is equivalent to
$$u^2 + v^2 + w^2 = u(u+v+w),$$
where $u,v,w$ are positive integers and either $v\ne u$ or $w \ne u$. I then picked a few small values of $u$ and tried solving this Diophantine equation using Wolfram Alpha. The first solution I stumbled across was $u=5$, $v=2$, $w=6$, but there are many others as well. In retrospect I guess I could have simplified further to
$$v^2 + w^2 = uv + uw$$
but I didn't notice and it turned out not to matter.
Context
StackExchange Computer Science Q#70142, answer score: 11
Revisions (0)
No revisions yet.