- #1

zeion

- 466

- 1

Hi,

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

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.)

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: