Question

2. (25) [Rising trend] Textbook Exercise 17 in Chapter 6. The problem to solve is, in other words, to select from a sequence of n numbers a subset, including the first number, such that the selected numbers make a longest monotonously increasing sequence. In the exercise b, (i) write an optimal substructure (with an explanation),ii) write the iterative dynamic programming algorithm (pseudocode), and (iii) show the running-time analysis. Hints: the algorithm in the exercise a is a greedy algorithm; the answer returned in the exercise b is the length of the longest rising trend starting from P[1], so think "backward" beginning from P[1] Your friends have been studying the closing prices of tech stocks, looking for interesting patterns They've defined something called a rising trend, as follows They have the closing price for a given stock recorded for n days in succession; let these prices be denoted P[1], P[2],..,PIn].Arising trend in these prices is a subsequence of the prices P[i1], P[i2],... ,P[ik], for days i12 Pl] then Set i-j Add 1 to L Endif Endf or In your example, give the actual length of the longest rising trend, and say what the algorithm above returns (b) Give an efficient algorithm that takes a sequence of prices P[1], P[2],PIn] and returns the length of the longest rising trend

Answer 1

For example, -the sequence is ; ו, 4 ,2 ,3 Actual lenqth is 3 -the lenath2 But though Alaorithm, for 3. G. ormula: lere, We are using the OPT Cs Scanned with