As input a finite stream stream of numbers is provided. Define an algorithm to find the majority element of the input. The algorithm need not provide a sensible result if no majority element exists. You may assume a transdichotomous memory model.There are a few definitions which may not be immediately clear:

- Stream
- A possibly infinite set of data which may not be reused in either the forward or backward direction without explicitly storing it.
- Majority element
- An element in a set which occurs more than half the time.
- Transdichotomous
- The integer size is equal to the word size of memory. One does not need to worry about storing partial pieces of integers in separate memory units.

## The algorithm (click to view)

Using 3 registers the*accumulator*, the

*guess*and the current element (

*next*):

- Initialize
*accumulator*to 0 - Accept the next element of the stream and place it into
*next*. If there are no more elements go to step #7. - If
*accumulator*is 0 place*next*into*guess*and increment*accumulator*. - Else if
*guess*matches*next*increment*accumulator* - Else decrement
*accumulator* - Go to step 2
- Return the value in
*guess*as the result

An interesting property of this algorithm is that it can be implemented in $O(n)$ time even on a single tape Turing Machine.

## No comments:

## Post a Comment

Have something you want to say? You think I'm wrong? Found something I said useful?

Leave a comment!