Not sure how to come up with a randomized algorithm. I think the problem would b

Question

Not sure how to come up with a randomized algorithm. I think the problem would be to break up the groundhogs into subproblems of size n/2 and then the base case would be if it is a single groundhog check with all the holes? But that would just end up taking O(n) time for each base case which is inefficient.

n n groundhogs of different sizes and n corresponding holes (burrows). You are 4. You are give allowed to try to stick a groundhog in a hole, from which you can determine whether the groundhog is larger than the hole, smaller than the hole, or matches the hole exactly. However, there is no way to compare two groundhogs together (they squirm too much) or the two holes together (you don t have a ruler with you). The proble divide-and-conquer algorithm for this problem with expected efficiency Oin log(n)) n is to match each groundhog to its hole. Design a randomized (a) Give a brief explanation and pseudocode for your algorithm Solution

Explanation / Answer

1.You sort the holes(burrows)

2.Now for each groundhogs find it location in sorted holes.

Now as the sorting of holes-array will take at least O(nlogn) time

and then finding the one groundhogs position in sorted array of holes will take O(logn) time (Binary Search)

Hence total Complexity T(n)=nlogn + logn

=O(nlogn).

-----------------------------

Now coming to your approach

1.You'r logic is same as Quick sort and hence you can proceed with your logic to find sorting array of either groundhogs or either holes and

2.Then from another array pick one element and find its position which is Binary Search.

---

You can proceed with your logic to build Binary Search tree and then you can reduce complexity.

//If any query then please comment that.

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

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