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?

Improve this question
$\endgroup$
7
  • 3
    $\begingroup$ What is the goal of this loop, in words? $\endgroup$ Commented Sep 13, 2012 at 19:15
  • 6
    $\begingroup$ I can't see how the algorithm does what you claim it does. $\endgroup$ Commented Sep 13, 2012 at 19:49
  • $\begingroup$ what if no such string exists as in {"one","two","three"} $\endgroup$ Commented Sep 14, 2012 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$ Commented Sep 14, 2012 at 9:06
  • $\begingroup$ yes, if nothing occurs more than half the time, it is undefined. $\endgroup$ Commented Sep 14, 2012 at 15:43

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.