Purchase Solution

Sum of 2 Numbers from a Set in O(n log n) Algorithm

Not what you're looking for?

Ask Custom Question

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(nlogn)-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?

Purchase this Solution

Solution Summary

This solution discussed how you can arrange to sort to sort the legal structure for actual programming, defines the comparison, sorts the structures and provides an example for the coding using the lego blocks of hypothetical length. This solution is 736 words.

Solution Preview

Yes it is done by sorting

I assume that you have some familiarity with algorithms.

First, let us note, that if you look at a particular Lego piece of length y, you can
calculate what should be the length of another piece to complement it:
it should be (x-y).

Every piece can be either primary or complementary.
Therefore, if we can arrange so that we sort some structures in which every piece enters in two copies of a suitably defined structure, in one with its length (y), and in another with its complementary length (x-y), we can find a needed couple in O(n log n) moves, because a matching couple, if any exists, would be one next to another in the sorted list.

Here is an example of how to organize such structures for actual programming.

Let the structure be

struct Triplet {
int Length ;
bool bPrimary ;
int ID
}

Here, the ID is just the number of the block needed to find it again if you want it,
and the couple (Length, bPrimary) can be either

(y, ...

Purchase this Solution


Free BrainMass Quizzes
Basic Networking Questions

This quiz consists of some basic networking questions.

Basic UNIX commands

Use this quiz to check your knowledge of a few common UNIX commands. The quiz covers some of the most essential UNIX commands and their basic usage. If you can pass this quiz then you are clearly on your way to becoming an effective UNIX command line user.

Java loops

This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.

Inserting and deleting in a linked list

This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.

Word 2010: Table of Contents

Ever wondered where a Table of Contents in a Word document comes from? Maybe you need a refresher on the topic? This quiz will remind you of the keywords and options used when working with a T.O.C. in Word 2010.