I can't solve this nuts and bolts problem for the life of me, and my Data Structures assignment is due tomorrow. I would hope that someone at Chegg can show me how to solve each question step-by-step as I have spent the last few days on this last problem. Problem 5 You are given n bolts, B = {b1, b2. . . . , bn} all of different diameters, and n matching nuts, M = {m1, m2, . . . , mn}, but the nuts are not ordered to match the order of the bolts. You will be solving the problem of matching the nuts and the bolts. If it helps you may assume that all bolts (and so all nuts) are distinct. The input to the problem are the two arrays B and M .

Hint: The first thing to decide is how to represent a solution of the problem. What you are looking for is a mapping between the list of bolts and the list of nuts. One possibility is to simply re-arrange one or both of them so that the i-th bolt matches the i-th nut.

(10 points) Describe a brute-force (exhaustive search) algorithm for solving the problem, give pseudo code. What is the worst case input? Evaluate the worst case asymptotic time com- plexity of your algorithms, show your work.

Hint: One can simply compare each bolt with each nut and use a single loop to re-arrange the bolts. So we have:

Pre: The arrays: B = {b1, b2. . . . , bn} and M = {m1, m2, . . . , mn}

Post: The array B = {b1, b2. . . . , bn} is re-arranged so that bolt bi, matches nut ni, for each

i = 1, 2, . . . , n.

This brute force approach has worst case scenario complexity (n2). The worst case scenario will be in the case when you have to make the most comparisons between bolts and nuts. You need to describe explicitly what does this mean in terms of the original arrays B and M . To give you an idea how to describe this, think of a best case scenario. One example of a best case scenario is when example when both B and M are already sorted (in increasing order).

(10 points) Assuming that any comparison-based sorting algorithm for solving the nut-bolt matching problem will progress by making comparisons, no other information, (thus can be modeled using a decision tree). Give a lower bound on the worst case asymptotic time complexity for solving the problem. Recall that you need to specify.

Hint: Recall the main steps in our proof of the complexity for the sorting problem using decision tree. The bound is essentially the height of the decision three and that an upper bound for the height of the binary tree can be computed if we know the number of leaves (recall how we did this for the sorting problem and also when we compted the height of recursion threes). So you need to figure out

1. What are the possible outputs?

2. What is the total number of possible outputs? since each leaf of the decision three corresponds to a distinct output.

3. How do we obtain a bound of the height of the decision tree if we know the number of outputs i.e., leaves?

Note, that you do not need to draw a decision tree, just apply the steps we discussed in class. Simplify the expression for the bound as much as you can.

(10 points) Assuming that you can compare a nut to a nut and a bolt to a bolt, describe an algorithms with worst case asymptotic time complexity of O(n log n), briefly justify the complexity.

Hint: Note that in part a you could compare nuts with bolts while in here you can only compare nuts with nuts and bolts with bolts. One solution is to somehow rearrange both arrays so that the i-th element in B matches the i-th element in M .

(10 points)Can you come up with an algorithm with O(n log n) average complexity, if a nut and a bolt can be compared, but a nut and a nut cannot be compared together, and a bolt and a bolt cannot be compared? Explain and briefly justify the complexity of the algorithm you propose.

Hint: This setup is similar to the one in part a you can compare nuts with bolts but very different from c. because you can not compare nuts with nuts and/or bolts with bolts. However, to speed up things you may consider re-arranging both the bolts and nuts arrays. For example, if you manage to sort both arrays then you will get an automatic match between bots and nuts as in part b.. However, the solution from part b. will not work directly because there yo were allowed to compare bolts with bolts and nuts with nuts. One solution is to think how to modify one of the sorting algorithms to work in this situation.

Pre: The arrays: B = {b1, b2. . . . , bn} and M = {m1, m2, . . . , mn}

Post: The array B = {b1, b2. . . . , bn} and M = {m1, m2, . . . , mn} are sorted.