What is the loop invariant for this algorithm?

In summary, the conversation is discussing an algorithm designed to find a majority element in an array, with the majority element being defined as an element that appears in more than half of the array locations. The speaker is having trouble writing a loop invariant expression that uses the variables in the algorithm, as c is a counter and i is an iterator, and they don't seem to have anything to do with the majority element m. The other person clarifies that the algorithm is supposed to return m if it exists in A and appears in at least half of the elements, and provides an example of how the algorithm would work on a given array. They also share a code snippet that successfully implements the desired functionality.
  • #1
zeion
466
1
Hi,

I'm having trouble getting a loop invariant expression for this algorithm:

Code: 
Majority(A):
    c = 1
    m = A[0]
    for i = 1 to len(A) - 1:
        if c == 0:
           m = A[i]
           c = 1
       else if A[i] == m:
           c = c + 1
       else:
           c = c - 1
    return m

It's supposed to return m such that m is an element in A that appears in more than half of the array A, if it exists.
I don't see how I can write a loop invariant expression that uses the variables in the algorithm? c is just a counter and i is the iterator, they don't really have anything to do with m?

The exact question:

A majority element in an array is an element that appears in more than half of the array locations.
Consider the following algorithm that finds a majority element in an array, if one exists.
a) Give precise preconditions and post-conditions for this algorithm (I get this part)
b) Write a detailed proof that the algorithm is correct. (This includes, but is not limited to, finding and proving a suitable loop invariant.)
 
Last edited:
Technology news on Phys.org
  • #2
zeion said:
Hi,

I'm having trouble getting a loop invariant expression for this algorithm:

Code: 
Majority(A):
    c = 1
    m = A[0]
    for i = 1 to ;en(A) - 1:
        if c == 0:
           m = A[i]
           c = 1
       else if A[i] == m:
           c = c + 1
       else:
           c = c - 1
    return m

It's supposed to return m such that m is an element in A that appears in more than half of the array A, if it exists.
I don't see how I can write a loop invariant expression that uses the variables in the algorithm? c is just a counter and i is the iterator, they don't really have anything to do with m?

So just to clarify , you want to return all of m that exists in A such that the value is at least in 1/2 of all of the elements in A?
 
  • #3
KingMike said:
So just to clarify , you want to return all of m that exists in A such that the value is at least in 1/2 of all of the elements in A?

If A {1,1,1,2,3,4,1}

Then the program returns 1.

Because the majority of A's elements are 1's.
 
  • #4
zeion said:
Hi,

I'm having trouble getting a loop invariant expression for this algorithm:

Code: 
Majority(A):
    c = 1
    m = A[0]
    for i = 1 to ;en(A) - 1:
        if c == 0:
           m = A[i]
           c = 1
       else if A[i] == m:
           c = c + 1
       else:
           c = c - 1
    return m

It's supposed to return m such that m is an element in A that appears in more than half of the array A, if it exists.
I don't see how I can write a loop invariant expression that uses the variables in the algorithm? c is just a counter and i is the iterator, they don't really have anything to do with m?

m is an element of A
i >= 1 && i <= en(A)-1
c >= 0 && c <= en(A)-1

?
 
  • #5
zeion said:
It's supposed to return m such that m is an element in A that appears in more than half of the array A, if it exists.
What happens if you use that loop on A[] = {1,1,2,2,2,1,1}? It seems that what this loop does is find the longest sequential sub-array composed of the same number (it would return 2 for {1,1,2,2,2,1,1}.
 
  • #6
Ok this does what I think you want it to do...it is in c you will have to port it to your language


Code: 
int Majority ( )
{
    const int elementSize = 7;
    int location = 0;
    int elementCounter = 0;
    int elements[elementSize] ={ 1 , 2 , 24, 4 , 3 , 4 , 1 };
    int  elements2[elementSize]= { 1 , 2 , 4 , 4 , 3 , 4 , 1 };
    int i,j;
    int counter;
    counter = 0;

    for ( i = 0 ;  i < elementSize ; i++ )
    {
        counter = 0;
        for ( j = 0 ; j < elementSize ; j++ )
        {
            if(elements[i] == elements2[j])
            {
                counter++;
            }

        }
        if ( counter > elementCounter )
        {
            location = i;
            elementCounter = counter;
        }


    }
    if ( elementCounter >= elementSize / 2 )
    {
        return elements[location];
    }
    return 0;

}
 
  • #7
zeion: did you forget to tell us that the array only stores two different numbers (e.g. it's an array of 0's and 1's)?

If so, then the triple of values (c,m,i) is just a fancy way of storing a histogram.
 
  • #8
jreelawg said:
m is an element of A
i >= 1 && i <= len(A)-1
c >= 0 && c <= len(A)-1

?

Okay but how does that show m is the "majority" element of A?
rcgldr said:
What happens if you use that loop on A[] = {1,1,2,2,2,1,1}? It seems that what this loop does is find the longest sequential sub-array composed of the same number (it would return 2 for {1,1,2,2,2,1,1}.

From what I've gathered we're only interested in m if m exists (ie. there is an element in A that occurs in more than half the array locations)
Otherwise the output doesn't matter.
Hurkyl said:
zeion: did you forget to tell us that the array only stores two different numbers (e.g. it's an array of 0's and 1's)?

If so, then the triple of values (c,m,i) is just a fancy way of storing a histogram.

I believe that the array can store any objects for which the operator "==" is defined.
I'm going to add the exact question to the first post...

So far, questions I've done have loop invariants that modifies the return value each time the loop is ran, and the return value is dependent on the number of iterations of the loop.
But here, the loop is checking for the number of occurrence of an element in A by using the count c, and m is an element of A, which doesn't change...
I guess the index for the majority (i) would change? But I'm not sure how to express that using just math symbols...
 
Last edited:
  • #9
zeion said:
Okay but how does that show m is the "majority" element of A?

To be an invariant, the condition must be true at the start and end of each iteration of a loop. All I can think of to say about m, is that it is guaranteed to be an element of A.
 
Last edited:
  • #10
zeion said:
But here, the loop is checking for the number of occurrence of an element in A by using the count c, and m is an element of A, which doesn't change...
I guess the index for the majority (i) would change? But I'm not sure how to express that using just math symbols...

The loop is actually not really checking for the number of occurrences of an element in A, and c doesn't really count elements.

rcgldr's example.

A={1,1,2,2,2,1,1}

When the loop finishes, m=2, and c=1.

If A={1,1,2,2,2,1,1,1,6,1}

When the loop finishes, m=6, and c=0.

It is only guaranteed that the program will return the majority, if there exists an element which occurs consecutively in A for a number of times greater than half the amount of elements in A.
 
Last edited:
  • #11
jreelawg said:
It is only guaranteed that the program will return the majority, if there exists an element which occurs consecutively in A for a number of times greater than half the amount of elements in A.
There are other cases, the most prominent of which only two different values appear in A.
 
  • #12
Hurkyl said:
There are other cases, the most prominent of which only two different values appear in A.
We already tried that, for A={1,1,2,2,2,1,1}, there are 4 1's out of 7 numbers, but when the loop finishes, m=2, and c=1.
 
  • #13
rcgldr said:
We already tried that, for A={1,1,2,2,2,1,1}, there are 4 1's out of 7 numbers, but when the loop finishes, m=2, and c=1.

Not sure if I did something wrong but for this array I get:

Initialize c = 1, m = 1
Then go in the loop, read A[1]: c = 2, m = 1
Second iteration, read A[2]: c = 1, m = 1
Third iteration, read A[3]: c = 0, m = 1
Fourth iteration, read A[4]: c = 1, m = 2
Fifth Iteration, read A[5]: c = 0, m = 2
Sixth iteration, read A[6]: c = 1, m = 1

So c = 1, m = 1
As for the LI, I think that for each iteration, m must always be the "majority" element from A[0 ... i - 1].
If len(A[0 ... i - 1]) is even, then m occurs at least half of the positions in A[0 ... i - 1], if it is odd, then m occurs at least more than half the positions.
 
  • #14
zeion said:
Not sure if I did something wrong but for this array I get:

Initialize c = 1, m = 1
Then go in the loop, read A[1]: c = 2, m = 1
Second iteration, read A[2]: c = 1, m = 1
Third iteration, read A[3]: c = 0, m = 1
Fourth iteration, read A[4]: c = 1, m = 2
Fifth Iteration, read A[5]: c = 0, m = 2
Sixth iteration, read A[6]: c = 1, m = 1

So c = 1, m = 1
As for the LI, I think that for each iteration, m must always be the "majority" element from A[0 ... i - 1].
If len(A[0 ... i - 1]) is even, then m occurs at least half of the positions in A[0 ... i - 1], if it is odd, then m occurs at least more than half the positions.

Your right. I wrote a quick c++ version to test it. Given my track record now in this forum, you might want to check for mistakes. But, I get m=1, c=1 for {1,1,2,2,2,1,1}, and for {1,1,2,2,2,1,1,1,6,1} I get m=1, c=2.
Code: 
#include <iostream>
using namespace std;

int main() {
    int c = 1;
    int A[]={1,1,2,2,2,1,1,1,6,1};
    int m = A[0];
    
    for (int i=1; i <= 9; ++i){
        if (c == 0) {
           m = A[i];
           c = 1;
	}
        else if (A[i] == m) 
           ++c;
        else
           --c;
    }
    cout << "m=" << m;
    cout << endl << "c=" << c << endl << endl;
	
    cout << "press enter to continue";
    cin.get();
    return 0;
}
 
Last edited:
  • #15
I wrote a program which fills A with random numbers between 1 and n, and first uses the algorithm you posted, shows the value for m, and c.

Then it executes a function I wrote to show the number of occurrences of each element.

I haven't done that many tests, but it seams like the algorithm you posted does what you said it does.

Code: 
#include <iostream>
#include <time.h>
#include <vector>
using namespace std;

void Majority(int Numb_Elements, vector <int> Element) {     
	vector <int> ElementCount;         
	vector <int> ElementTemp;     
	int TMP=0;    
	int Majority=0;
	int m=0;
	bool AlreadyCounted=false;
	bool NoMajority=false;
	
	for (int i=0; i < Numb_Elements; ++i){                     
	    ElementTemp.push_back(Element[i]);         
	    ElementCount.push_back(0);
	}      

	for (int i=0; i < Numb_Elements; ++i) {        
		for (int ii=0; ii < Numb_Elements; ++ii){             
			if (Element[i]==ElementTemp[ii])                 
		        ++ElementCount[i];      
		}
	}
	
	TMP=0;

	for (int i=0, TMP=0; i < Numb_Elements; ++i) {        
		if (ElementCount[i] > TMP){            
			TMP=ElementCount[i]; 
			Majority=i;
		}
	} 
        TMP=0;
	for (int i=0; i < Numb_Elements; ++i){
		for (int ii=1;  ii <= i; ++ii){
			if (Element[i]==ElementTemp[i-ii])
				AlreadyCounted=true;
		}
	    if (AlreadyCounted==false) {
			cout << Element[i] << " occures " << ElementCount[i] << " times " << endl;
			if (ElementCount[i]==ElementCount[Majority])
				++TMP;
		}
		AlreadyCounted=false;
	}

	if (TMP > 1) 
		NoMajority=true;

	if (NoMajority==false) {
	    cout << endl << "Majority: " << Element[Majority] <<  "   Occurrences: " << ElementCount[Majority] << endl << endl;
		m=Element[Majority];
	}
	else {
		cout << endl << "No single majority exists." << endl << endl;
		m=-1;
	}
	
	cout << "Press Enter To Continue" << endl;
	
	cin.get();
} 

int main() {
    int c = 1;
	vector <int> A;
	int array_length;
	int range;

	cout << "enter an array lenght: ";
	cin >> array_length;

	cout << endl << endl << "each element a random number between 1 and :";
	cin >> range;

	srand( time(NULL) );

	for (int i=0; i < array_length; ++i) 
		A.push_back(rand()% range + 1);

	int m = A[0];
    for (int i=1; i <= array_length-1; ++i){
        if (c == 0) {
           m = A[i];
           c = 1;
		}
       else if (A[i] == m) 
           ++c;
       else
           --c;
	}

	cout << endl;

	for (int i=0; i < array_length; ++i) 
		cout << "A[i]=" << A[i] << endl;

        cout << endl << "m=" << m;
	cout << endl << "c=" << c << endl << endl;
	
	cout << "press enter to continue" << endl;
	cin.get();
	cin.get();

        Majority(array_length, A);
	return 0;
}
 
Last edited:
  • #16
rcgldr said:
What happens if you use that loop on A[] = {1,1,2,2,2,1,1}? return 2 ...
My fault, I initialized c to 0 instead of 1. I should have caught that sooner.

If c == 0, then the most common element encountered so far was encountered for exactly 1/2 of the elements tested, and the algorithm just starts over with the next element in the array, and c = 1. This could continue until the very last element of an array with an odd number of elements, in which case the algorithm starts over with the very last element, setting m to that element and c = 1 then returning with m = last element. Since the rule is that the most common element is more than 1/2 of the elements in an array, then if c == 0 on the next to last element, the last element must be the most common element.

If c != 0, then m = an element that was encountered more often than 1/2 of the elements tested so far.

I'm not sure how to state this as a loop invariant.
 
Last edited:
  • #17
rcgldr said:
If c == 0, then the most common element encountered so far was encountered for exactly 1/2 of the elements tested
... either from the start of the array or since the last time c == 0 and the algorithm started over. So there can be intermediate strings (c == 0) without the majority element. If there are any intermediate strings without the majority element, then those strings must be preceded or followed by continuous strings of the majority element (in order for the majority element to be present in more than 1/2 of the array).
 
Last edited:

Related to What is the loop invariant for this algorithm?

What is a loop invariant in an algorithm?

A loop invariant is a condition that remains true before and after each iteration of a loop in an algorithm. It helps to prove the correctness of the algorithm by showing that the desired outcome is achieved at each step of the loop.

Why is a loop invariant important in algorithm design?

A loop invariant is important because it helps to ensure the correctness of an algorithm. By proving that the loop invariant is true before and after each iteration, we can be confident that the algorithm will produce the desired result.

How do you determine the loop invariant for an algorithm?

To determine the loop invariant for an algorithm, you need to analyze the algorithm and identify the condition that remains true before and after each iteration of the loop. This condition should be relevant to the desired outcome of the algorithm.

Can a loop invariant be changed during the execution of an algorithm?

No, the loop invariant should remain the same throughout the execution of the algorithm. If the loop invariant changes, it means that the algorithm is not performing as intended and may lead to incorrect results.

What happens if the loop invariant is not satisfied during the execution of an algorithm?

If the loop invariant is not satisfied, it means that the algorithm is not working correctly. This could result in incorrect output or an infinite loop. It is important to ensure that the loop invariant remains true throughout the execution of the algorithm to ensure its correctness.

Similar threads

Challenge: Find the minimum amount of draws possible for a list of integers
    • Programming and Computer Science
Replies
9
Views
1K
Fast reciprocal square root algorithm
    • Programming and Computer Science
Replies
30
Views
4K
MHB Dynamic programming: which recurrence relation do we use?
    • Programming and Computer Science
Replies
2
Views
1K
XOR algorithm to find the missing number in a given array
    • Programming and Computer Science
Replies
13
Views
3K
What is the fastest algorithm for finding large prime numbers?
    • Programming and Computer Science
Replies
14
Views
2K
MHB Booth algorithm for multiplying signed numbers
    • Programming and Computer Science
Replies
1
Views
1K
Java FileFinder using Breadth First Search algorithm fails
    • Programming and Computer Science
Replies
2
Views
785
Can Sorting Ever Be Done in Time Proportional to n?
    • Programming and Computer Science
Replies
12
Views
1K
Switch Argument Outside While Loop Execution Explained
    • Programming and Computer Science
Replies
9
Views
1K
What's wrong with this Python program on Euler's forward algorithm?
    • Programming and Computer Science
Replies
2
Views
956

Hot Threads

Recent Insights

Back
Top