1. (30 pts) Here is a classical problem that is often part of interviews. You are given n nuts and n bolts, such that one and only one nut fits each bolt. Your only means of comparing these nuts and bolts is with a function TEST(1,y), where I is a nut and y is a bolt. The function returns +1 if the nut is too big. O if the nut fits, and -1 if the nut is too small. Note that you cannot compare nuts to nuts and bolts to bolts. The usual question is to design and analyze an algorithm for sorting the nuts and bolts from smallest to largest using the TEST function. While there are many approaches that work, the smart answer is to combine a pivot operation from quicksort to solve this as follows: Pick a bolt, and partition the nut array into nuts that are smaller, mut that fits, and nuts that are larger. Then, pick the matching nut, and partition the nut array similarly. Below is pseudo-code for this algorithm. Procedure quicknutboltsort (nutarray, boltarray,n,n): if men, return; new_nutarray(0:n-x] - -1; new_boltarray [O:n-m]--1; testbolt -boltarray[n]; low - 0; best_fit = -1; high - n-n; For k in m to n. if Test (nutarray[k].testbolt) 0, neu_boltarray [high--)-boltarray[j]; else continue; new_boltarray[lou) - testbolt; // now recur: quicknutboltsort (new_nutarray, new_boltarray, 0, low-1); quicknutboltsort (new_nutarray, boltarray, lou+1,n-m); for k in m ton: nutarray [k] - newnut_array[k-n) ; boltarray[x] - neubolt_array [k-m); (a) What is the tightest worst-case asymptotic growth of the above function as n + ? (b) To analyze the average case, assume that the value of low in the above algorithm is equally likely to be any number from 0 to m-n. Write a recursion for the average asymptotic run time for quicknutboltsort (nutarray, boltarray,0,n) as a function of n. 1 (c) Solve that recursion, using the following fact: T(n) = cn+T() T(n) (nIn(n)) ke=0 (d) The above algorithm uses lots of extra storage, copying arrays back and forth. Modify the above algo rithm so that you use only the original nutarray and boltarray. You may want to look at implementations of quicksort to see how to sort in place. 1. (30 pts) Here is a classical problem that is often part of interviews. You are given n nuts and n bolts, such that one and only one nut fits each bolt. Your only means of comparing these nuts and bolts is with a function TEST(1,y), where I is a nut and y is a bolt. The function returns +1 if the nut is too big. O if the nut fits, and -1 if the nut is too small. Note that you cannot compare nuts to nuts and bolts to bolts. The usual question is to design and analyze an algorithm for sorting the nuts and bolts from smallest to largest using the TEST function. While there are many approaches that work, the smart answer is to combine a pivot operation from quicksort to solve this as follows: Pick a bolt, and partition the nut array into nuts that are smaller, mut that fits, and nuts that are larger. Then, pick the matching nut, and partition the nut array similarly. Below is pseudo-code for this algorithm. Procedure quicknutboltsort (nutarray, boltarray,n,n): if men, return; new_nutarray(0:n-x] - -1; new_boltarray [O:n-m]--1; testbolt -boltarray[n]; low - 0; best_fit = -1; high - n-n; For k in m to n. if Test (nutarray[k].testbolt) 0, neu_boltarray [high--)-boltarray[j]; else continue; new_boltarray[lou) - testbolt; // now recur: quicknutboltsort (new_nutarray, new_boltarray, 0, low-1); quicknutboltsort (new_nutarray, boltarray, lou+1,n-m); for k in m ton: nutarray [k] - newnut_array[k-n) ; boltarray[x] - neubolt_array [k-m); (a) What is the tightest worst-case asymptotic growth of the above function as n + ? (b) To analyze the average case, assume that the value of low in the above algorithm is equally likely to be any number from 0 to m-n. Write a recursion for the average asymptotic run time for quicknutboltsort (nutarray, boltarray,0,n) as a function of n. 1 (c) Solve that recursion, using the following fact: T(n) = cn+T() T(n) (nIn(n)) ke=0 (d) The above algorithm uses lots of extra storage, copying arrays back and forth. Modify the above algo rithm so that you use only the original nutarray and boltarray. You may want to look at implementations of quicksort to see how to sort in place