I have been at this problem for the last few days now, and I still have almost n

Question

I have been at this problem for the last few days now, and I still have almost no idea how to approach this particular instance of a nuts and bolts problem in my Data Structures and Algorithms course.

5. You are given n bolts, B bbalof different diameters, and n matehing nuts, M {m1, m2, , ma), but the nuts are not ordered to match the order of the bolts. You will be solving the problem of matehing the nuts and the bolts. If it helps you may assume that all bolts (and so all nuts) are distinet. The input to the problem are the two arrays B and M (a) (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 asymptotie time complexity of your algorithms, show your work. (b) (10 points) Assuming that any comparson-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 i. What an output be? ii. What is the total number of possible outputs? iii. Logarithm of the number of possible outputs gives the lower bound for the problem based on the decision tree technique. Simplify that expression 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. (c) (10 points) Assuming that you can compare a nut to a nut and a bolt to a bolt, deseribe an algorithms with worst case asymptotie time complexity of O(n log), briefly justify (d) (10 points)Can you come up with an algorithm with O(n log n) average complexity, if a nut and a bolt ean 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

Explanation / Answer

package com;
public class ArraySortedPolynomial implements PolynomialInterface

{

ArraySortedPolynomial()

{

}

ArraySortedPolynomial(String pol)

{

}

@Override

public PolynomialInterface add(PolynomialInterface other) {

// TODO Auto-generated method stub

return null;

}

@Override

public PolynomialInterface subtract(PolynomialInterface other) {

// TODO Auto-generated method stub

return null;

}

}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.