One-pass algorithm: Difference between revisions

Revision as of 17:07, 14 April 2021

Revision as of 23:03, 14 April 2021

Line 25:

Given any list as an input:

* Find the ''n''th element from the end (or report that the list has fewer than ''n'' elements).

* Find the middle element of the list. However, this is solvable with two passes: Pass 1 counts the elements and pass 2 picks out the middle one.

Given a list of numbers:

Line 31:

* Find the [[mode (statistics)|modes]] (This is not the same as finding the most frequent symbol from a limited alphabet).

* Sort the list.

* Count the number of items greater than or less than the [[mean]]. However, this can be done in constant memory with two passes: Pass 1 finds the average and pass 2 does the counting. This

The two-pass algorithmalgorithms isabove aare still [[streaming algorithm|streaming algorithms]] but not a one-pass algorithmalgorithms.

== References==