Let A[1..n] be an array of n positive integers where the elements of A can only...

Transcribed Image Text:

Let A[1..n] be an array of n positive integers where the elements of A can only be compared for equality. A majority element of A exists if it occurs more than [n/2] times in A. Therefore, if A has size 6 or 7, then the majority element must occur at least 4 times in A. 1. (3 marks) Comment on the validity of the following statement: If the majority element of A exists, then it must also be the majority element of either the left or right half of A. 2. (4 marks) If A is sorted, write a simple algorithm that returns the majority element of A (if one exists) in O(n) time. If the majority element does not exist, then -1 is returned. int majority (int [] A, int n) 3. (8 marks) If A is not necessarily sorted, design a divide-and-conquer algorithm that returns. the majority element for A (if one exists) in O(n log n) time. If the majority element does not exist, then -1 is returned. int majority (int[] A, int low, int high) Let A[1..n] be an array of n positive integers where the elements of A can only be compared for equality. A majority element of A exists if it occurs more than [n/2] times in A. Therefore, if A has size 6 or 7, then the majority element must occur at least 4 times in A. 1. (3 marks) Comment on the validity of the following statement: If the majority element of A exists, then it must also be the majority element of either the left or right half of A. 2. (4 marks) If A is sorted, write a simple algorithm that returns the majority element of A (if one exists) in O(n) time. If the majority element does not exist, then -1 is returned. int majority (int [] A, int n) 3. (8 marks) If A is not necessarily sorted, design a divide-and-conquer algorithm that returns. the majority element for A (if one exists) in O(n log n) time. If the majority element does not exist, then -1 is returned. int majority (int[] A, int low, int high)

Answer rating: 100% (QA)

Comment on the validity of the statement The statement is not valid The existence of a majority elem... View the full answer