4
$\begingroup$

I have created the algorithm below...

        String A = v[0];
        int val = 1;

        for (int i = 1; i < v.length; i++) {
            if (val == 0) {
                A = v[i];
                val++;
            } else if (v[i].equals(A))
                val++;
            else
                val--;
        }

The goal of the algorithm is to find the item that occurs in more than half the array.

Let v = {"one", "two", "one", "three", "one", "two", "two", "one", "one"}

The string "one" occurs 5 out of 9 times. So, at the end of the loop, the String A will be equal to "one".

I'm lost as to how to derive a loop invariant from this. Could someone provide me with some direction?

$\endgroup$
  • 3
    $\begingroup$ What is the goal of this loop, in words? $\endgroup$ – Dave Clarke Sep 13 '12 at 19:15
  • 6
    $\begingroup$ I can't see how the algorithm does what you claim it does. $\endgroup$ – Dave Clarke Sep 13 '12 at 19:49
  • $\begingroup$ what if no such string exists as in {"one","two","three"} $\endgroup$ – miracle173 Sep 14 '12 at 6:18
  • $\begingroup$ @miracle173 I think that in that case, the result is undefined. In other words, it's allowed to be anything. $\endgroup$ – svick Sep 14 '12 at 9:06
  • $\begingroup$ yes, if nothing occurs more than half the time, it is undefined. $\endgroup$ – MCR Sep 14 '12 at 15:43
3
$\begingroup$

See this question on Stack Overflow. You should provide reference for an algorithm when you did not write it, at least explain how you came up with it if you "created" it.

Terminology: this question is about finding the majority element of an array.

The invariant at step $i$ is:

  • A occurs at least in val cells of v[0..i]
  • The remaining (i + 1 - val) cells can be discarded without changing the majority element.

The algorithm is easy to accept as correct when you understand that if you remove two different elements of the array, then it keeps its majority element.

$\endgroup$

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.