Problem 1 [10 + 20 = 30 pts] The code for the selection algorithm has been uploaded to elearn. As pointed out in class, the code is incorrect because there may be multiple elements equal to the one we are partitioning around (x) and while the counts lt, eq, gt are computed correctly, the x may not necessarily occur where they should. On paper submit as problem 1, an example where this incorrect code may lead to incorrect result. Also, change the code (dont change the function names etc.) to fix this. Your modified code should also run the partitioning in linear time. This code should be submitted on dropbox.

i fimport random def swap (L,i,j): "I'Swap list positions i and j" t = L[i] L[i] = L[j] L[j] = t 9 def partition (L): n = len (L) idx = random.randrange(n) #put L[idx] into oth position swap (1,0, idx) x = L[0] #It is number of elements less than L[idx], eq is number of elements equal #gt is number of elements greater than L[idx] (lt,eq,gt) = (0,1,0) (ij) = (0,1) while (j X: gt = gt+1 j = j + 1 else: if L[j] == X: eq = eq + 1 else: #L[j] (3*n)/4 or gt> (3*n)/4: return false return True 48 def select(L,k): "return the kth element in L" def select(L,k): return the kth element in L" n = len(L) if (n == 0): return None elif (k = n): return None #generate a good partition first (lt,eq,gt,x) = partition(L) while (not good_partition(L,(lt,eq,gt))): (lt,eq,gt, x) = partition (L) if k X: gt = gt+1 j = j + 1 else: if L[j] == X: eq = eq + 1 else: #L[j] (3*n)/4 or gt> (3*n)/4: return false return True 48 def select(L,k): "return the kth element in L" def select(L,k): return the kth element in L" n = len(L) if (n == 0): return None elif (k = n): return None #generate a good partition first (lt,eq,gt,x) = partition(L) while (not good_partition(L,(lt,eq,gt))): (lt,eq,gt, x) = partition (L) if k