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
#70941
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 at the attachment for more detail):
Describe a (n log_2 n) time algorithm that, given a set S of n real numbers
and another real number x, determines whether or not there exist two
elements in S whose sum is exactly x.
Solution:
Sort the array using an algorithm of order O(n log n) (You can use mergesort but
you cannot use quicksort)
Then for every element y in the array binary search the sorted array for x - y
O(n log n) + O(n log n) = O(n log n)
What is this?
By OTA - Overall OTA Rating
Xiao Liu, MS - 4.7/5
Purchase Cost Now
$2.19 CAD (was ~$15.96)
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
- Here are some recurrence relations that come up in the analysis of Quicksort and or Select. For each recurrence, write one sentence explaining how it relates to Quicksort or Select and give its asymptotic growth rate in Q notation. - see attached file
- Data Structures C++ - Describe the worst case scenario for quick sort algorithm. Any ideas to improve the worst case? Comment on the improvement in running time vs. increase in code complexity.
- Ambiguity in a proposed algorithm - Explain the distinction between an ambiguity in a proposed algorithm and an ambiguity in the representation of an algorithm.
- Data structures C++ -- Quick sort Algorithm - Use the quicksort algorithm to sort vector v. During each pass, list all exchanges of a pair of elements in the lower and upper sublist. List the ordering of the elements after each pass. int arr[] ...
- Sorting Algorithms - We have considered the following sorting algorithms in this book: Heap, Insertion, Merge, Quicksort, Radix, Selection For each sort, give the average and worst case running time and the space re ...
