current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top
up vote 5 down vote favorite

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 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 8

B = 4 4 4 4 4 4 4 4

2)A = 7 8 8 5 5 4 7 8

B = 2 3 3 2 2 1 2 3

As 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 correct. Besides the result of the exam, which I still don't know yet, I'm very interested in knowing if there's some mathematical proof/explanation which states that this approach is correct or not, and that's why I need an help.

I hope I have posted the question in the right StackExchange site. If not, please redirect me to the right site.

Thank you in advance.

share|cite|improve this question
2  
How about (3+2+4)/3=3? – Yuval Filmus 2 hours ago
up vote 9 down vote accepted

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.

share|cite|improve this answer
    
Thank you for the explanation! I understood everything. (Sad :( ) – Alessandro 4 hours ago
up vote 4 down vote

[2,2,5,5,5,5,5,6,6,6,6,6,6] is a counterexample.

how I found that: ​ ​ ​ (The last step of this was a Python script.) ​ For them to not all be equal, there need to be at least two distinct numbers that appear. ​ However, averages are strictly between the min and the max, so to pass your criterion there must be at least three distinct numbers. ​ I simply figured there ought to be a counterexample with only three distinct numbers. ​ For the reason I gave two sentences ago, with just three distinct numbers, one only needs to check for whether-or-not the average is the middle number. ​ With that observation, I wrote a Python script to try triples with respect to the lexicographic order of [sum,largest,middle,smallest], and the array I gave corresponds to the smallest counterexample that script found.

share|cite|improve this answer
    
Nice! This looks correct and helpful. I like the explanation of how you found it; that seems really helpful. I'm hoping the deletion is only temporary -- if you choose to undelete, I'd gladly upvote it. – D.W.♦ 5 hours ago
    
(I had deleted mine because it didn't seem to add anything to yours.) ​ ​ – Ricky Demer 4 hours ago
    
Thank you! Very nice way. – Alessandro 4 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.