Longest Biased Interval 

1. Rational BiasProblem:
Given a data sequence, e.g. ACGTAGCAGATAGACAGGTTAGACAATAGAG,
and a "bias" criterion, In the HTMLform below, the fraction is p/q where p and q are small integers which (for given p and q) yields a simple, specialcase, lineartime algorithm (but the multiplier depends on p and q). key: `choice'  acceptable characters. `p' and `q'  p/q is the required fraction of acceptable characters. 2. General BiasGive elements of the sequence a +ve value for "good" and a ve value for "bad". Compute the cumulative sums from the start of the sequence. The sum of a "good enough" interval is nonnegative, i.e. the cumulative sum is flat or increasing across the interval: e.g. required ratio = 1/2
e.g. required ratio = 2/3 (good = +1/3, bad = 2/3) The following HTMLform implements a general algorithm for biases that are not necessarily rational. Its timecomplexity is almost always O(n), but can be O(n^{2}) in the worst case for ``pathalogical'' sequences. Note that some numbers, including some common rational numbers, cannot be represented exactly in floatingpoint. Therefore one might need to give `ratio' a (very, very,) very little ``slack''. 3. NotesUsing binarysearch to search (track) the array of cumulativesum minima would give an O(n.log(n))time, O(n)space algorithm. So of course, one could run both algorithms
in parallel and take the result from the first to finish
(also halting the other one):
O(n)time usually and
O(n.log(n))time worst case 4. ReferenceL. Allison,
Longest Biased Interval and Longest NonNegative Sum Interval,


↑ © L. Allison, www.allisons.org/ll/ (or as otherwise indicated). Created with "vi (Linux)", charset=iso88591, fetched Monday, 03Oct2022 05:19:38 UTC. Free: Linux, Ubuntu operatingsys, OpenOffice officesuite, The GIMP ~photoshop, Firefox webbrowser, FlashBlock flash on/off. 