1) Quick sort general idea is as follows.  Select a “random” item in the unsorted part as the pivot  Rearrange (called partitioning) the unsorted items such that:PivotPivot IndexItemAll items < to Pivot All items >= to Pivot Quick sort the unsorted part to the left of the pivot Quick sort the unsorted part to the right of the pivotGiven the following partition function which returns the index of the pivot after this rearrangement. def partition(lyst, left, right): # Find the pivot and exchange it with the last item middle = (left + right) / 2 pivot = lyst[middle] lyst[middle] = lyst[right] lyst[right] = pivot # Set boundary point to first position boundary = left # Move items less than pivot to the left for index in xrange(left, right): if lyst[index] < pivot: temp = lyst[index] lyst[index] = lyst[boundary] lyst[boundary] = temp boundary += 1 # Exchange the pivot item and the boundary item temp = lyst[boundary] lyst[boundary] = lyst[right] lyst[right] = temp return boundarya) For the list below, trace the first call to partition and determine the resulting list, and value returned.54 0 0 1 2 3 4 5 6 7 8 8 left index right boundary26 93 17 77 31 44 55 20lyst:b) What initial arrangement of the list would cause partition to perform the most amount of work?c) Let “n” be the number of items between left and right. What is the worst-case O( ) for partition?Data Structures Lecture 15 Name:__________________Lecture 15 Page 1d) What would be the overall, worst-case O( ) for Quick Sort?e) Why does the partition code select the middle item of the list to be the pivot?f) Ideally, the pivot item splits the list into two equal size problems. What would be the big-oh for Quick Sort inthe best case?g) What would be the big-oh for Quick Sort in the average case?Data Structures Lecture 15 Name:__________________Lecture 15 Page 22) Consider the coin-change problem: Given a set of coin types and an amount of change to be returned,determine the fewest number of coins for this amount of change. a) What "greedy" algorithm would you use to solve this problem with US coin types of {1, 5, 10, 25, 50} and achange amount of 29-cents?b) Do you get the correct solution if you use this algorithm for coin types of {1, 5, 10, 12, 25, 50} and a changeamount of 29-cents?3) One way to solve this problem in general is to use a divide-and-conquer algorithm. Recall the idea ofDivide-and-Conquer algorithms.Solve a problem by: dividing it into smaller problem(s) of the same kind solving the smaller problem(s) recursively use the solution(s) to the smaller problem(s) to solve the original problema) For the coin-change problem, what determines the size of the problem?b) How could we divide the coin-change problem for 29-cents into smaller problems?c) If we knew the solution to these smaller problems, how would be able to solve the original problem?Data Structures Lecture 15 Name:__________________Lecture 15 Page 34) After we give back the first coin, which smaller amounts of change do we have?29 cents1-cent coin5-cent coin10-cent coin12-cent coin25-cent coin50-cent coinPossible First CoinOriginal ProblemSmaller problems5) If we knew the fewest number of coins needed for each possible smaller problem, then how could determinethe fewest number of coins needed for the original problem?6) Complete a recursive relationship for the fewest number of coins.FewestCoins(change) = 1if change CoinSet if change CoinSet min( FewestCoins( ) ) + coin CoinSet7) Complete a couple levels of the recursion tree for 29-cents change using the set of coins {1, 5, 10, 12, 25, 50}.29 cents1-cent coin5-cent coin10-cent coin12-cent coin25-cent coin50-cent coinPossible First CoinOriginal ProblemSmaller problemsData Structures Lecture 15 Name:__________________Lecture 15 Page