CS341 : CLRS CS341.pdf

Part (a) [3 MARKS] Consider this program: Fill in the Python Shell output after this program has executed. >>> X L = [4, 10, 8] X = L. sort L.append(20) L2 = L[1:] >>> L >>> id(L) == id(L2)

Question 11. [5 MARKS] Each code fragment in the table below operates on list L, which has length k where k is very large - at least in the tens of thousands. For each fragment, give an expression in terms of k for how many times happy! is printed, and circle whether the behaviour is constant, linear, quadratic or something else. Code How many times is happy! printed? Complexity (circle one) for i in range (len (L)): print('happy!') for item in L: print('happy!') constant linear quadratic something else for i in range (len(L)) for item in L[:i]: print('happy!' constant linear quadratic something else # Precondition: len(L) % 10 == 0 i = 0 while i < len(L): print("happy!') i = i + len(L) // 10 constant linear quadratic something else for item in L[1000:2000] : print('happy!' constant linear quadratic something else for item in L[10:] : print('happy!' constant linear quadratic something else

Recursion Question 5. In the following question, you will be asked to program the following using recursion. If you have an iterative solution, you may use it, but the most you can get for the question will be half credit. (5) points) Consider the following mathematical function h which operates on integers. (1, if n < 2 h(n) = n(n-1) +n if n > 2 and n is even han -2) +2*n if n > 2 and n is odd In Java, use recursion to write a method h which takes as input an int n and returns h (n). public static int h(int n) {