Subject: Data Structures and Algorithms, C++ programming
please help with these 2 take-home
questions (20 and 21). Need
full marks please double-check answers cannot take any chances NEED
THE FULL ANSWERS AND CORRECT ANSWER, also within the word
limit with 10% lenience on the word limit. will give an upvote if
correct. Need answer within 6 hours.
- Subject Data Structures And Algorithms C Programming Please Help With These 2 Take Home Questions 20 And 21 Need 1 (107.57 KiB) Viewed 57 times
Question 20 (3 Marks) 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).