2
$\begingroup$

A Bitonic Sequence is a sequence of numbers which is first strictly increasing then after a point strictly decreasing.

According to the definition of a bitonic sequence, we know that a graph of a bitonic sequence can have at most one "peak" and one "valley".

So, why is the sequence 1,3,2,4 not a bitonic sequence?

I have referred the book, "Parallel Computing", by M. J. Quinn.

$\endgroup$
  • $\begingroup$ One "valley"? If you define a valley as a number that is smaller than all of its neighbor(s), then there are two valleys in a bitonic sequence, which are the two numbers at both ends of the bitonic sequence. If you define a valley as a number that has two larger neighbors, then there is no valley in a bitonic sequence. Either way, you cannot have exactly one valley in a bitonic sequence. $\endgroup$ – Apass.Jack Aug 22 '18 at 4:51
2
$\begingroup$

In this sequence, lets consider 3 as the bitonic point. So 1,3 makes for a strictly increasing series.

However after we cross the bitonic point 3, 2 and 4 do not make a strictly decreasing series.

Another point in Bitonic Series' is that we have to take into account circular bitonic patterns. So a series like 1 2 5 0 -5 -2 is bitonic since we monotonically increase from 1 to 5, then monotonically decrease from 5 to -5 and again we monotonically increase from -2 to 5.

In the case of 1 *3* 2 *4* 1, there are 2 peaks occurring and hence its not even circularly bitonic.

$\endgroup$
2
$\begingroup$

According to your definition, a sequence $x_1,\ldots,x_n$ is bitonic if there exists an index $i$ such that $x_1 < x_2 < \cdots < x_i$ and $x_i > x_{i+1} > \cdots > x_n$.

In your case, this means that one of the following must holds: $$ 1 > 3 > 2 > 4 \\ 1 < 3 > 2 > 4 \\ 1 < 3 < 2 > 4 \\ 1 < 3 < 2 < 4 $$ You can check that none of these options works.

Another way to see this is to notice that your sequence has an ebb, $x_3 = 2$, which cannot happen in a bitonic sequence.

A third way is to notice that a sequence is bitonic if the $<,>$ pattern is of the form $<^*>^*$ (in regular expression parlance). In your case, $1 < 3 > 2 < 4$, and so the pattern is $<><$, which is not of this form.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.