Answer Happy

Suppose we have a sequence of numbers: 1, 8, 5, 2, 6, 3, 9, 7, 4, 2, 3. We aim to find a longest turbulence in the sequence. Turbulence' is a consecutive sub-sequence where the numbers rise and drop alternately. Every sub- sequence of a turbulence is also a turbulence. For example, 1 and 8 and 5 are all turbulences because each of them contains only one number. 1,8 and 8,5 are both turbulences because 1 rises to 8 in the first sequence and 8 drops to 5 in the second. 1, 8,5 is a turbulence because 1 rises to 8 and then drops to 5. 8,5, 2 is not a turbulence because 8 drops twice (first to 5 and then to 2). The longest turbulence in the given sequence is 5, 2, 6,3,9,7. Can you design a brute-force algorithm to find the longest turbulence in a given sequence of numbers (such as the sequence provided above)? What is its time complexity in terms of big-O? (word limit: 200) Question 21 (3 Marks) Can you describe an algorithm that is likely to achieve better running time than brute-force for Question 20? (word limit: 200).