- #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: