What is the loop invariant for this algorithm?

Click For Summary

Discussion Overview

The discussion revolves around finding a loop invariant for an algorithm designed to identify a majority element in an array. Participants explore the algorithm's mechanics, its variables, and the implications of its logic, focusing on the conditions under which it correctly identifies a majority element, if one exists.

Discussion Character

  • Exploratory
  • Technical explanation
  • Debate/contested

Main Points Raised

  • Some participants express confusion about how to formulate a loop invariant that incorporates the algorithm's variables, particularly the role of the counter 'c' and the iterator 'i' in relation to 'm'.
  • Others question whether the algorithm correctly identifies a majority element, citing examples where it appears to return incorrect results based on the input array.
  • One participant suggests that the algorithm may only work correctly under specific conditions, such as when the array contains only two distinct values.
  • There is a discussion about the necessity of 'm' being a majority element, with some participants arguing that the algorithm's logic does not guarantee this outcome in all cases.
  • Several participants attempt to clarify the algorithm's behavior with specific examples, leading to further exploration of the conditions under which 'm' is considered a majority element.
  • One participant proposes that the loop invariant should state that 'm' must always be the majority element from the subarray considered up to the current index 'i'.

Areas of Agreement / Disagreement

Participants do not reach a consensus on the correctness of the algorithm or the formulation of a suitable loop invariant. Multiple competing views remain regarding the algorithm's effectiveness and the conditions necessary for it to return a valid majority element.

Contextual Notes

Participants note that the algorithm's correctness may depend on specific characteristics of the input array, such as the presence of only two distinct values or the distribution of elements. There is also uncertainty about how to express the loop invariant mathematically, particularly in relation to the variables involved.

zeion
Messages
455
Reaction score
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
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?
 
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.
 
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

?
 
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}.
 
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;

}
 
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.
 
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:
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:

Similar threads

Challenge: Find the minimum amount of draws possible for a list of integers
  • · Replies 9 ·
Replies
9
Views
3K
XOR algorithm to find the missing number in a given array
  • · Replies 13 ·
Replies
13
Views
5K
Python Simple code example of transforming matrix into upper triangular form
  • · Replies 3 ·
Replies
3
Views
2K
Fast reciprocal square root algorithm
  • · Replies 30 ·
2
Replies
30
Views
7K
MHB Dynamic programming: which recurrence relation do we use?
  • · Replies 2 ·
Replies
2
Views
2K
What is the fastest algorithm for finding large prime numbers?
  • · Replies 14 ·
Replies
14
Views
3K
Loop Invariant in Analysis of Algorithm
  • · Replies 1 ·
Replies
1
Views
3K
Can Sorting Ever Be Done in Time Proportional to n?
  • · Replies 12 ·
Replies
12
Views
2K
JavaScript Algorithm to return all subarrays of a given array
  • · Replies 8 ·
Replies
8
Views
4K
Python Questions about the for loop, iterable, iterator in Python
  • · Replies 16 ·
Replies
16
Views
3K