• Implement Majority-Element finding using Algorithm V from lecture slides
• Input:
• array of N positive integers size of the problem is N n Output:
• 1) majority element (M.E.) element occurring more than N/2 times

(order of elements doesnt matter), if M.E. exists n 2) -1, if the majority element does not exist in the array

• Input should be read into array of integers: int[] (do not use

ArrayList) n The code should work on that array, without re-formatting the data e.g. into a linked list or any other data structure

• The algorithm should have O(N) time complexity n Use of any Java built-in functions/classes is NOT allowed n With the exception of functions from Scanner, System.in and

System.out (or equivalent) for input/output

Input-output formats

• -1 if the input array has no majority element
• X if integer X is the majority element of the input array

Algorithm V (from lecture)

• Observation: some pair of elements can be deleted from A without changing M.E. (if M.E. exists) Example:
• Possible pairs and corresponding deletion effects:
  • (non-M.E., non-M.E.) -> result doesnt change
  • (M.E., non-M.E.) -> result doesnt change (M.E., M.E.)-> result can change assuming M.E. exists
• Order in which pairs are deleted is not important
• But we dont know which element is M.E.!

Algorithm V (from lecture)

• Solution:
  • Instead of Delete everything except (M.E., M.E.)
  • Do Delete everything except (X,X)
• Move through the elements from left to right
• Keep deleting pairs of no-equal elements at every opportunity

• E. will be the only one remaining Easy implementation with double-linked list Example:
  • But we can also do these concepts for an array.

How?

Algorithm V (from lecture)

• Array approach:
  • Assign a candidate-M.E. (c-ME) (init:1^st element)
  • As you sweep the array,
• do not delete c-ME, move forward
• delete a non-c-ME with one c-ME.
• If another element becomes most frequent in the array so far (i.e., a new c-ME), all instances of the previous one have already been deleted
  • One approach: keep current position and keep count of c-ME and decrease upon delete
• Location of c-MEs is not important, only their count

Algorithm V (from lecture)

• Boyer & Moore approach
  • Select first element as candidate M.E., set counter to 1 Move forward through the array. When we see:
• another copy of the c-ME -> increase counter
• some other element -> decrease counter
• If the counter becomes 0, assign a new c-ME at current

index

• previous c-ME lost the chance
• Once the entire array is traversed, c-ME will be the only

element left (if exists)

Input/output in Java

• Use Standard I/O to read input and write the result
• For Java, input: System.in, output: System.out
• Do Nots
  • Do not read from a disk file/write to disk file
  • Do not write anything to screen except the result
• Ex: Human centric messages (the result is, please enter..)
• Automated grading via script will be used for checking correctness of your output