Question 3 Consider a list, for instance, [3, 4, 5, 3, 2, 5, 6, 4]. A subsequence or sublist of a list is a list you obtain by removing zero or more elements from the original list. For example, subsequences of the above list are: [4, 5, 6] [3, 4, 5, 5, 6] [3, 5, 2] A nondecreasing subsequence is a sequence in which a value is not smaller than any of the previous ones. In the examples above, the first three subsequences are nondecreasing the last one is not, as the last 2 is smaller than 3 and 5. Your task is to write a function nondecsub(1) which, given a list 1, returns a list consisting of all the nondecreasing subsequences of 1. Hint: It is easier to write a function nondecsub(1, threshold=None), and we have set up the problem for you in this way. The idea is that threshold represents a threshold, below which you should not select elements from 1. Remember your goal is to reduce the problem to one that is smaller, for example, one that involves a list that is shorter by one. Look at how the code for permutations was done. Reduce your problem to one that is smaller, and use threshold parameter to ensure that the generated subsequences are nondecreasing 1) 1 def nondecsub (1, threshold-None): 2 ### YOUR CODE HERE 4 # This code helps in testing, as it transforms a list of lists into a set of tuples. 5 6 def normalize(11): 7 5 - set() 8 for 1 in 11: s.add(tuple(1)) 10 returns 12 def n(1): 13 return normalize(nondecsub(1, threshold=None)) 1 # This is a place where you can write additional tests to help you test 2 # your code, or debugging code, if you need. You can also leave it blank. 4* YOUR CODE HERE 1 ### 5 points: simple tests 2. 3 check_equal(n([4]), normalize([[], [4]]). 4 5 check_equal(n([]), normalize((()))) 6 7 check_equal(n([3, 4]), normalize([ 8 [], [3], [4], [3, 4] 9 ])) 10 11 check_equal(n([4, 3]), normalize(/ 12 [], [3], [4] 13 ])) 14 1 ( 1 ### 10 points: more complicated tests 2 3 check_equal(n([-1, , 3, 4, 3, 5]), normalize([ 4 (3, 4, 5), (2, 4, 5), (-1, 0)) (-1, 0, 3, 3, 5), (-1, 0, 3, 4), 5 (-1,), (-1, 5), (0, 3), (3, 3), (-1, 3, 3), (3,), (-1, 3, 4), 6 (3, 3, 5), (-1, 4, 5), (-1, 0, 3, 4, 5), (-1, 0, 3, 5). 7 (-1, 3, 3, 5), (-1, 3, 5), (0, 4), (5,), (-1, 0, 3, 3), 8 (-1, 2, 3), (0, 3, 3), (e, 3, 3, 5), (-1, 0, 4, 5), (4, 5), (-1, e, 5), 9 (0, 5), (-1, 0, 4), (3, 5), (0,), (, 3, 4), (-1, 3), (0, 3, 5), (4,), 10 (), (0, 3, 4, 5), (-1, 3, 4, 5), (-1, 4), (3, 4) 11 ])) 12 13