Do part 2 please 2. Graded Problem (Page limit: 1 sheet; 2 sides) An element of

Question

Do part 2 please

2. Graded Problem (Page limit: 1 sheet; 2 sides) An element of an array A[1 nl 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 query you can access the elements of A is of the form whether A Aj] in constant time, for any i and j. Solve this problem with a Divide-and-Conquer algorithm that runs in time O(nlogn). Prove your a- 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

Array has n element

Now if we pick any two pairs (x, y) if x != y then this will add 0 to final count of members

two cases

Now if x == y, count is incremented by 1

two cases

count of majority element is greater than half:

so if we pair every non majority element with majority elemeent, then there will atleast be one pair which will have two majority eleement

Simple example

let array size is 10

majority element will occur atleast 6 times

so remaining element are 4

which means there can be max 4 pairs with non majority element and hence one pair will always be there for majority element

Now this proves that there will always be majority element present

Now using this strategy we can check if majority element exist

If majority element exist in array(n), then it will exit in array obtained by this strategy of size n/2

We will reursively apply this untill array size is 2 (or less)

If we get an array of size 2, then we can comapre these element and check if they are same, if yes then they are majority element, if they are different then there is no majority element (if array size is 0 then also no majority element) and if array size is 1 then that is our majority element

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

Solving this will give T(n) = O(n)

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

---

---

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