Loading ...
Sorry, an error occurred while loading the content.

Please help me with this Unimodal sequence problem

Expand Messages
  • jsmithalgo
    A unimodal sequence is a sequence for which there exists a t such that strictly increases and then strictly
    Message 1 of 1 , Apr 26, 2005
    • 0 Attachment
      A unimodal sequence is a sequence <a0,a1,a2,...an-1> for which there
      exists a t such that <at,at+1,at+2,..., at+n-1> strictly increases
      and then strictly decreases, where the subscript calculations are
      performed modulo n. That is, if the sequence <a0,a1,a2,...an-1> is
      rotated to the left t positions, if strictly increases to a maximum
      and then strictly decreases. An example of a unimodal sequence is
      given below. Design an efficient algorithm to find the maximum value
      in the unimodal sequence. Define tight asymptotic upper bounds for
      your algorithm's running time.
      (For a reduction of a letter grade on this problem, consider only
      unimodal sequences for which t=0).


      i 0 1 2 3 4 5 6
      3 2 1 3 5 6 4


      Rotate left t = 2
      i 0 1 2 3 4 5 6
      1 3 5 6 4 3 2

      Thanks & Regards,
      JSmith.
    Your message has been successfully submitted and would be delivered to recipients shortly.