Lubo and Mike are building a "do all" robot in CS148 and have found that
they have to fit two lego pieces side by side into an opening. The opening is
x inches wide and the sum of the widths of the two pieces has to be exactly
equal to the width of the opening, otherwise, their robot will fall apart during
the demo. They have a huge collection of lego pieces of varying widths at their
disposal and have to pick two pieces which satisfy the above constraint.
Since the Computer Science department at Brown believes in doing every-
thing through a well defined algorithm, you should supply these poor guys an
algorithm for doing the task, and one that is asymptotically efficient! So, here
goes your exact problem.
You are given a set of n real numbers and another real number x. Describe
a O(n log n)-time algorithm that determines whether or not there exist two
elements in S whose sum is exactly x.
Hint : Doesn't the O(n log n) term make you feel that sorting is involved in
some way?
Computer Science Homework Solutions
#70492
Sum of 2 numbers problem: create a O(n log n) algorithm that determines whether or not there exist two elements in S whose sum is exactly z
I need help creating a O(n log n) algorithm that determines whether or not there exists two elements in S whose sum is exactly z. Additionally, the problem indicates that sorting is somehow related to the solution.
What is this?
By OTA - Overall OTA Rating
Israel Kovner, PhD - 5/5
Purchase Cost Now
$2.19 CAD (was ~$19.95)
Included in Download
- Plain text response
Why you can trust BrainMass.com
- Your Information is Secure
- Best Online Academic Help Service
- Students find real academic Success
- explanation of solution - The solution seems to be the the following, but I need a more in-depth explanation, particularly on why we should use merge sort and binary sort. Here is the problem at a high level (you can look ...
- Merging Sorted Lists using Heaps - I need help figuring out an algorithm that will merge k sorted lists into one sorted lists in O(n lg k) time where n is the number of elements in ALL the input lists. I believe we are supposed to u ...
- Understanding a binary search. - What is a binary search, and how does it work?
- Suppose that you have a function Median(L) that takes as input a list - Dear Mr. Xiong, Please show me the details of the two attached questions. Have a good day.
- Describe an Algorithm - The question is attached and there are some clarifications 1. The integers are NOT sorted and you CANNOT sort them. You need to see if the numbers would match the pattern if you were to sort them. ...
