1
$\begingroup$

Given the following algorithm (pseudocode):

alg1(A[1,..,n])
    i <- 1
    candidate <- NULL
    count <- 0
    while(i <= n)
        if(count = 0)
            candidate <- A[i]
            count <- count + 1
        else if(candidate = A[i])
            count <- count + 1
        else
            count <- count - 1
        i <- i + 1
    return candidate

I need to prove that if a value appears more than $n \over 2$ times (let the value be named $M$) in the array then it will be returned.

$\mathbf{EDIT:}$ here's my 2 attempt. First we assume that the array $A$ contains at least 3 elements (if less then the proof is trivial). The element which appears more than $n/2$ times is $M$ else it's $M'$. Let a two-element combination of $MM'$ or $M'M$ be called $C$. Every time we traverse a $C$ the count decreases by one.

CASE 1: If the pattern is strictly alternating combinations of type $C$ then the first and the last element must be $M$ (otherwise $M$ will not appear more than $n/2$ times) and this means that after the last iteration the candidate is $M$.

CASE 2: We can see that after any number of adjacent $C$'s the counter will be $0$ and the candidate will be either $M$ or $M'$. It is given that more than $n/2$ elements of $M$ do exist in the array, so the number of $C$ combinations must be supplemented by at least $1$ occurrence of $k$ adjacent elements of $M$ either before $C$'s or after $C$'s. If it's after, then the next candidate is $M$ and it will continue to be so as long as we keep traversing $k$ elements of adjacent $M$'s. If it's before than the count will be at least $1$ before it proceeds to iterate through $C$'s and essentially it'll behave just like CASE 1.

I'm still aware that the proof is not perfect but I feel like it's an improvement. Suggestions/advice is very welcome.

$\endgroup$
  • $\begingroup$ Try to give a more formal proof. A proof is more than intuition – it is a convincing argument that leaves no room for doubt. $\endgroup$ – Yuval Filmus Apr 13 '17 at 13:41
  • $\begingroup$ I completely agree that the argument lacks formality but I'm not sure I'm even in the right direction. $\endgroup$ – Yos Apr 13 '17 at 13:49
  • 1
    $\begingroup$ It's not true that every time you traverse a $C$ then candidate changes. $\endgroup$ – Yuval Filmus Apr 13 '17 at 18:10
1
$\begingroup$

Let us prove the following claim by induction:

Suppose that the first $i$ symbols contain $j$ copies of $\sigma$, and let $\delta = j-(i-j) = 2j-i$. After the $i$th iteration of the loop:

(a) If $\delta > 0$ then $candidate=\sigma$ and $count \geq \delta$.

(b) If $\delta \leq 0$ then either $candidate=\sigma$ or $count \leq -\delta$.

This certainly holds for $i = 0$. Given that it holds for $i$, we now show it holds for $i':=i+1$ as well. Let $j,j'$ be the number of copies of $\delta$ in the first $i,i'$ symbols (respectively), and let $\delta=2j-i$, $\delta'=2j'-i'$. Define $candidate,candidate'$ and $count,count'$ as the values of these variables after $i,i'$ iterations (respectively). There are several cases to consider.

Case 1: the $i'$th symbol is $\sigma$.

Case 1a: $\delta > 0$. The induction hypothesis states that $candidate = \sigma$ and $count \geq \delta$. Therefore $candidate' = \sigma$ and $count' = count+1 \geq \delta+1 = \delta'$.

Case 1b: $\delta = 0$, $candidate = \sigma$. This is the same as Case 1a.

Case 1c: $\delta = 0$ and $candidate \neq \sigma$. The induction hypothesis states that $count = 0$. Therefore $candidate' = \sigma$ and $count' = 1 = \delta'$.

Case 1d: $\delta < 0$ and $candidate = \sigma$. This is the same as Case 1a.

Case 1e: $\delta < 0$ and $candidate \neq \sigma$. The induction hypotehsis states that $count \leq -\delta$. Therefore either $candidate' = \sigma$, or $count' = count-1 \leq -(\delta+1) = -\delta'$.

Case 2: the $i'$th symbol is $\tau \neq \sigma$.

Case 2a: $\delta > 0$. The induction hypothesis states that $candidate = \sigma$ and $count \geq \delta$. Therefore $candidate' = \sigma$ and $count' = count-1 \geq \delta-1 = \delta'$.

Case 2b: $\delta = 0$ and $candidate = \sigma$. If $count = 0$ then $count' = 1 = -\delta'$. Otherwise, $candidate' = \sigma$.

Case 2c: $\delta = 0$ and $candidate \neq \sigma$. The induction hypothesis states that $count = 0$, and so $count' = 1 = -\delta'$.

Case 2d: $\delta < 0$ and $candidate = \sigma$. This is the same as Case 2b (with $1 \leq -\delta'$ in the first case).

Case 2e: $\delta < 0$ and $candidate \neq \sigma$. If $candidate = \tau$ then $count' = count + 1 \leq -(\delta-1) = -\delta'$. If $candidate \neq \tau$ then $count' = 1 \leq -\delta'$.


Given the claim, we see that if $\sigma$ appears more than $n/2$ times, then when $i=n$ we have $\delta > 2(n/2)-n > 0$, and so $candidate = \sigma$.

$\endgroup$
  • $\begingroup$ @ Yuval Filmus: thank you for your post! I'd like to understand some of the concepts you have: is $\sigma$ the element which appears more than $n/2$ times? Also it's easy to understand that $i-j$ is the number of non-$\sigma$ elements. But what does $\delta$ really represent? $\endgroup$ – Yos Apr 13 '17 at 18:20
  • 1
    $\begingroup$ The symbol $\sigma$ can be any symbol, though the intended usage is indeed the symbol that appears more than $n/2$ times. The value $\delta$ is the difference between $\sigma$ symbols and non-$\sigma$ symbols so far. Intuitively, the worst case is when there are only two types of symbols, and in that case you can read off the value of count from $\delta$. $\endgroup$ – Yuval Filmus Apr 13 '17 at 18:24
  • $\begingroup$ Are a) and b) loop invariants that we want to prove? $\endgroup$ – Yos Apr 13 '17 at 18:43
  • 1
    $\begingroup$ The idea of my proof is to show that the worst case (in some sense) is when there are only two symbols. Perhaps this can be shown directly. I don't see anything "unnatural" about my proof, which is a straightforward case analysis. The main criticism should be that it's a bit long, and one would hope for a shorter argument not involving a long case analysis. $\endgroup$ – Yuval Filmus Apr 13 '17 at 19:05
  • 1
    $\begingroup$ If count decreases then candidate stays the same. When candidate changes, count increases from 0 to 1. $\endgroup$ – Yuval Filmus Apr 13 '17 at 20:16
1
$\begingroup$

Note: In my opinion, although the answer given by @Sunny Wang is slightly hard to follow, it is in the right direction. Maybe the author would like to come back and improve his/her answer. Therefore, I will only give some high-level hints here.

Playing with some examples, you will find that the program amounts to keeping eliminating (by decreasing the counter, of course) a pair of distinct elements. Therefore, if a value appears more than $\frac{n}{2}$ times, it (and only it; this is also important) survives and will be returned.

$\endgroup$
0
$\begingroup$

I'd like to try to use contradiction to prove your algorithm.

The algorithm can be described with a stack model. The procedure is equal to the operation of pushing and popping elements while scanning an array. As for each element scanned, if the stack is empty or the element is equal to the element at the top of the stack, push it; or pop an element. Since we initialize the stack with the array's first element and we push one element as soon as the stack is empty, our popping one element operation in each loop will remain the stack operations legal.

For the elements in the stack meantime are equal, the value which appears more than $\frac{n}{2}$ times must be returned. We can prove it by contradiction. Assume the value is not returned, any element of this value will lead to another element of a different value be popped. But it is impossible. We do not have so many elements. So the assumption is not correct. In this way, we prove that the algorithm is correct.

$\endgroup$
  • $\begingroup$ I find this rather hard to follow. Could you explain how the stack corresponds to the actual program? What dod you mean by "For the elements in the stack meantime are equal"? $\endgroup$ – David Richerby Apr 13 '17 at 14:59
  • $\begingroup$ @DavidRicherby I guess that the actual program amounts to keeping eliminating a pair of distinct elements. This corresponds to the "pop an element" thing in such a stack model. "For the elements in the stack meantime are equal" may be "In all time, the elements in the stack are equal (are the same)". (BTW, I agree with you that the stack model here makes the proof slightly hard to follow. A clearer proof can be found.) $\endgroup$ – hengxin Apr 13 '17 at 15:25
0
$\begingroup$

Proof by induction:

If $n=1$, the algorithm returns A[1], which is correct.

if $n>1$, and $M$ appears $t$ times in A, then either:

  • it appears $t$ times in A[1],...,A[n-1] and A[n]!=M, in which case the nth iteration of the while loop takes candidate=M and count$=t-(n-1-t)=2t-n+1$, but $t>n/2$ implies $2t-n+1>0$ therefore count>0 and alg1 returns $M$.
  • it appears $t-1$ times in A[1],...,A[n-1] and A[n]=M, in which case, in the nth iteration of the while loop, either candidate=M and alg1 returns M, or candidate!=M and count=0 and alg1 returns A[n] which is $M$.
$\endgroup$
  • 2
    $\begingroup$ This proof is a bit telegraphic. In particular, in the first case, why is $count=2t-n+1$? $\endgroup$ – Yuval Filmus Apr 13 '17 at 18:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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