2. Graded Problem (Page limit: 1 sheet; 2 sides) An element r of an array A[1: n

Question

2. Graded Problem (Page limit: 1 sheet; 2 sides) An element r of an array A[1: n] is called a majority element if more than half of A are equal to x. Your task is to find whether a given array has a majority element and if so, what it is. We do not assume the elements of A are integers, or otherwise ordered; the only access the elements of A is of the form whether A[i] = A[j] in constant time, for any i and j query you can Solve this problem with a Divide-and-Conquer algorithm that runs in time O(n log n). Prove your al- gorithm is correct, and prove the time bound. (Hint: By dividing A into two halves Al and A2, does the knowledge of whether Al and/or A2 have a majority element help? You must be rigorous in your reasoning.) . Here is another Divide-and-Conquer approach: We will pair up elements of A arbitrarily. If the pair of elements are different, then discard them both. If the pair of elements are the same, then keep exactly one of them. This produces an array of at most n/2 elements. Prove that if A has a majority element, then no matter how the pair is done, the reduced array also has a majority element and it must be the same. Does the converse hold? Now devise a Divide-and-Conquer algorithm following this strategy that runs in time O(n)

Explanation / Answer

We split the array A into 2 subarrays A1 and A2 of half the size. We choose the majority element of A1

and A2. After that we do a linear time equality operation to decide whether it is possible to find a majority

element.

procedure GetMajorityElement(a[1...n])

Input: Array a of objects

Output: Majority element of a

if n = 1: return a[1]

k = n/2

elemlsub = GetMajorityElement(a[1...k])

elemrsub = GetMajorityElement(a[k+1...n]

if elemlsub = elemrsub:

return elemlsub

lcount = GetFrequency(a[1...n],elemlsub)

rcount = GetFrequency(a[1...n],elemrsub)

if lcount > k+1:

return elemlsub

else if rcount > k+1:

return elemrsub

else return NO-MAJORITY-ELEMENT

T(n) = 2T(n/2) + O(n)

GetFrequency computes the number of times an element (elemlsub or elemrsub) appears in the given array

a[1...n]. Two calls to GetFrequency is O(n). After that comparisons are done to validate the existence of

majority element. GetFrequency is the linear time equality operation.

(b)

Using the proposed divide-and-conquer operation, indeed it is possible to give a linear time algorithm.

Idea is to pair up the elements arbitrarily to get n/2 pairs. In each pair if the two elements are different we

discard both of them. If they are same only one of them is kept.

Let m be a majority element of A. Frequency of m is greater than n/2 where n is the number of

elements of A. Since we are forming pairs of 2, there has to be at least one pair where both the elements of

the pair are m since otherwise frequency of m in A cannot be greater than n/2. At most all pairs can have

both the elements of the pair as m. So after the procedure at least one element m will be left or at most n/2

will be left where each of them is m. Therefore out of at most n/2

elements, one of the element must be m.

procedure GetMajorityElementLinear(a[1...n])

Input: Array a of objects

Output: Majority element of a

if n = 2:

if a[1] = a[2]

return a[1]

else

return NO-MAJORITY-ELEMENT

Create a temporary array temp

for i = 1 to n:

if a[i] = a[i+1]:

Insert a[i] into temp

i = i+1

return GetMajorityElementLinear(temp)

procedure CheckSanity(a[1...n])

Input: Array a of objects

Output: Majority element of a

m = GetMajorityElementLinear(a[1...n])

freq = GetFrequency(a[1...n],m)

if freq > [n/2]+ 1:

return m

else

return NO-MAJORITY-ELEMENT

T(n) = T(n/2) + O(n)

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.