Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

What is the loop invariant for this algorithm?

  1. Mar 18, 2012 #1
    Hi,

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

    Code (Text):


    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: Mar 18, 2012
  2. jcsd
  3. Mar 18, 2012 #2
    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?
     
  4. Mar 18, 2012 #3
    If A {1,1,1,2,3,4,1}

    Then the program returns 1.

    Because the majority of A's elements are 1's.
     
  5. Mar 18, 2012 #4
    m is an element of A
    i >= 1 && i <= en(A)-1
    c >= 0 && c <= en(A)-1

    ?
     
  6. Mar 18, 2012 #5

    rcgldr

    User Avatar
    Homework Helper

    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}.
     
  7. Mar 18, 2012 #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 (Text):

    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;

    }
     
  8. Mar 18, 2012 #7

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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)? :grumpy:

    If so, then the triple of values (c,m,i) is just a fancy way of storing a histogram.
     
  9. Mar 18, 2012 #8
    Okay but how does that show m is the "majority" element of A?


    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.



    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: Mar 18, 2012
  10. Mar 18, 2012 #9
    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: Mar 18, 2012
  11. Mar 18, 2012 #10
    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: Mar 18, 2012
  12. Mar 18, 2012 #11

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    There are other cases, the most prominent of which only two different values appear in A.
     
  13. Mar 18, 2012 #12

    rcgldr

    User Avatar
    Homework Helper

    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.
     
  14. Mar 18, 2012 #13
    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.
     
  15. Mar 18, 2012 #14
    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 (Text):
    #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: Mar 18, 2012
  16. Mar 19, 2012 #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 (Text):


    #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: Mar 19, 2012
  17. Mar 19, 2012 #16

    rcgldr

    User Avatar
    Homework Helper

    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: Mar 19, 2012
  18. Mar 19, 2012 #17

    rcgldr

    User Avatar
    Homework Helper

    ... 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 continous strings of the majority element (in order for the majority element to be present in more than 1/2 of the array).
     
    Last edited: Mar 19, 2012
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: What is the loop invariant for this algorithm?
Loading...