I can\'t solve this nuts and bolts problem for the life of me, and my Data Struc

ID: 3603503 • Letter: I

Question

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.

Explanation / Answer

Brute force Way: Start with the first bolt and compare it with each nut until we find a match. In the worst case we require n comparisons. Doing this for all bolts gives us O(n^2) complexity.

Quick Sort Way: We can use quick sort technique to solve this. We represent nuts and bolts in character array for understanding the logic.

Nuts represented as array of character
char nuts[] = {‘@’, ‘#’, ‘$’, ‘%’, ‘^’, ‘&’}

Bolts represented as array of character
char bolts[] = {‘$’, ‘%’, ‘&’, ‘^’, ‘@’, ‘#’}

This algorithm first performs a partition by picking last element of bolts array as pivot, rearrange the array of nuts and returns the partition index ‘i’ such that all nuts smaller than nuts[i] are on the left side and all nuts greater than nuts[i] are on the right side. Next using the nuts[i] we can partition the array of bolts. Partitioning operations can easily be implemented in O(n). This operation also makes nuts and bolts array nicely partitioned. Now we apply this partitioning recursively on the left and right sub-array of nuts and bolts.

As we apply partitioning on nuts and bolts both so the total time complexity will be (2*nlogn) = (nlogn) on average.

A Java based implementation of idea is below:

// Java program to solve nut and bolt problem using Quick Sort

public class NutsAndBoltsMatch

{

//Driver method

public static void main(String[] args)

{

// Nuts and bolts are represented as array of characters

char nuts[] = {'@', '#', '$', '%', '^', '&'};

char bolts[] = {'$', '%', '&', '^', '@', '#'};

// Method based on quick sort which matches nuts and bolts

matchPairs(nuts, bolts, 0, 5);

System.out.println("Matched nuts and bolts are : ");

printArray(nuts);

printArray(bolts);

}

// Method to print the array

private static void printArray(char[] arr) {

for (char ch : arr){

System.out.print(ch + " ");

}

System.out.print("n");

}

// Method which works just like quick sort

private static void matchPairs(char[] nuts, char[] bolts, int low,

int high)

{

if (low < high)

{

// Choose last character of bolts array for nuts partition.

int pivot = partition(nuts, low, high, bolts[high]);

// Now using the partition of nuts choose that for bolts

// partition.

partition(bolts, low, high, nuts[pivot]);

// Recur for [low...pivot-1] & [pivot+1...high] for nuts and

// bolts array.

matchPairs(nuts, bolts, low, pivot-1);

matchPairs(nuts, bolts, pivot+1, high);

}

// Similar to standard partition method. Here we pass the pivot element

// too instead of choosing it inside the method.

private static int partition(char[] arr, int low, int high, char pivot)

{

int i = low;

char temp1, temp2;

for (int j = low; j < high; j++)

{

if (arr[j] < pivot){

temp1 = arr[i];

arr[i] = arr[j];

arr[j] = temp1;

i++;

} else if(arr[j] == pivot){

temp1 = arr[j];

arr[j] = arr[high];

arr[high] = temp1;

j--;

}

temp2 = arr[i];

arr[i] = arr[high];

arr[high] = temp2;

// Return the partition index of an array based on the pivot

// element of other array.

return i;

}

Also, a hashmap based approach can be used.