CMSC401 Assignment1- M.E-finding Solved

n   Implement Majority-Element finding using Algorithm V from lecture slides

n   Input: 

n   array of N positive integers - size of the problem is N n Output: 

n   1) majority element (M.E.) – element occurring more than N/2 times 

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

n   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

n   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
•

•
Input Format:

–     First line: a single integer number N>=1, N<=1,000,000 

–     Following N lines: each contains a single positive integer containing the elements of the array 

• Each integer will be <=1,000,000,000 

–     Input will always be correct w.r.t. the specification above

Output format: 

–     A single line, with a single integer: 
Input 1:

5

1

100

100

1

100

Output 1:

100
Input 2:

4

10000

2

10000

3

Output 2:

-1
•      -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)
3
3
4
7
7
7
7
7
7
7
8
•        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 doesn’t change

–     (M.E., non-M.E.) -> result doesn’t change – (M.E., M.E.)-> result can change assuming M.E. exists

•        Order in which pairs are deleted is not important

•        But we don’t 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

3
7
3
7
7
4
7
7
7
7
8
•        M.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?

3
3
3
7
7
4
7
7
7
7
8
Algorithm V (from lecture)

•        Array approach:

–     Assign a candidate-M.E. (c-ME) (init:1st 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 Not”s

–    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