Please help. I don\'t understand what these runs are so I can\'t even start. My

Question

Please help. I don't understand what these runs are so I can't even start. My professor isn't writing me back and it's due in 3 hours.

Let list be a nonempty sequence of nonnegative random integers, each in the range [0, 32767] and let n be the length of list, e.g., list = { 2, 8, 3, 2, 9, 8. 6, 3, 4. 6, 1, 9 } where n = 12. List elements are numbered starting at 0 We define a run up to be a (k+1)-length subsequence list_n list_1 + 1 list_i+2, ..., list_i + k that is monotonically increasing (i.e . list_i + j > (list_i + j + 1 for each j = 1, 2, 3, .... k). Similarly, a run down is a (k+1)-length subsequence list_i, list_i + 1, list_i + 1, ..., list_i + k, that is monotonically decreasing (i.e., list_k + j - 1

Explanation / Answer

Hey it is simple, heres the explanation, read it carefully....

The program is that give some set of integers, for example 2,3,6,4,7,9,8,1 be an array there are 8 elements , now we have to find run_up and run_down.

run_up is nothing but elements that are arranged in increasing order i.e. 2,3,6 (since 2 < 3 < 6) come under one sub list becuase they are in ascending order and 2,3,6,4 will not come under run_up because 6 is greater than 4.So for the above sublist there are three elements but we count them from 0 i.e. for 2 k=0, for 3 k=1 , for 6 k=2 so total k=2. but k wont be 3 since it counts as 0,1,2...so on.Now coming to the next element i.e. 4 , after 4 theres 7 , 9 so now we have another sublist i.e. 4,7,9 ( since 4 < 7 < 9) now k = 2 for this sublist as i said earlier it counts as 0,1... but not 1,2,3 so k=2 but not 3

And if theres some number 3 after 4 then runs_up sublist will be just (4) and k=0 .

Now lets continue to our example after 9 we have 8, after 8 theres 1 so we take (8) as k=0 (as 8 > 1 i.e. decreasing order but we want increasing order) and (1) as k=0 too because theres no number after 1 to check for next bigger number.

Now runs_down is nothing but reverse of runs_up i.e. decreasing order now lets continue with our example 2,3,6,4,7,9,8,1 now starting from first element in list we have 2 and next 3 here 2 < 3 (increasing order) but we want decreasing order so we just stop at 2 and take 2 as runs_down sublist with k=0 now contiuing to read our list ... next element is 3 after 3 theres 6 ( 3<6 increasing order again) stop at 3 and take k=0 for it. Next is 6 and after 6 theres 4 so we have 6 < 4 (oh we got decreasing order!) now take (6,4) as one sublist in runs_down,with k = 1 for this sublist.. similarly:

(7) :     k=0

(9,8,1): k=2

now we have to caculate how many k values we got starting from 1 to n-1 where n is number of array elements

from our example we have to calculate how many times we got k value from 1 to 7 (i.e. 8-1 = 7 since we took 8 elements)

so the result will be total number of times we got of particular k value both in runs_up and runs_down:

k=1:      1 (since we got only one pair whose k value is 1 i.e (6,4) in runs_down)

k=2:       3 ( we got two times in runs_up with k=2 and just once in runs_down so total 2+1 =3)

k=3-7      0 (because we didnt get any pair of runs_up or runs_down for which k=3 or 4 or.... or 7 so its zero)

total       4

this is the result . I hope you understand it.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---