Explain how to determine line in o-n lg n time

Assignment Help Data Structure & Algorithms
Reference no: EM1372103

A group of n Ghostbusters is battling n ghosts. Each Ghostbuster is armed with a proton pack, which shoots a stream at a ghost, eradicating it. A stream goes in a straight line and terminates when it hits the ghost. The Ghostbusters decide upon the following strategy. They will pair off with the ghosts, forming n Ghostbuster-ghost pairs, and then simultaneously each Ghostbuster will shoot a stream at his chosen ghost. As we all know, it is very dangerous to let streams cross, and so the Ghostbusters must choose pairings for which no streams will cross. Assume that the position of each Ghostbuster and each ghost is a fixed point in the plane and that no three positions are collinear.

a. Argue that there exists a line passing through one Ghostbuster and one ghost such the number of Ghostbusters on one side of the line equals the number of ghosts on the same side. Describe how to find such a line in O(n lg n) time.

b. Give an O(n^2 lg n)-time algorithm to pair Ghostbusters with ghosts in such a way that no streams cross.

Reference no: EM1372103

Questions Cloud

Find profit-maximizing output and price : A company under monopolistic competition faces the demand curve: P = 500 - 12.5Q. The company's marginal cost is MC = 200 + 5Q.
Erikson stages of development : Explain Erikson's stages of development as each applies to your own personality formation. How did success at one stage make you for meeting the next challenge.
Concept of bureaucracy : Making direct reference to your reading assignments, discuss what is meant by the machine metaphor of modern organizations. How does this machine metaphor of organizations apply to Weber's concept of bureaucracy?
Determine average streaming media data rate : Assume we can accurately forecast set of WAPs that the taxi will visit. Determine average streaming media data rate that we can sustain by downloading prefetched data from WAPs?
Explain how to determine line in o-n lg n time : Explain how to determine such a line in O(n lg n) time. Provide the O(n^2 lg n)-time algorithm to pair Ghostbusters with ghosts in such a way that no streams cross.
Theory of human relations : Consider the following scenario: You're a plant foreperson at a highly-productive and competitive factory. Your manager approaches you with a concern about last month's productivity for the unit for which you are responsible.
Explain about supply chain strategies : Cite industry examples for at least two of the six Supply Chain strategies introduced in class and a brief description is expected for each example.
Write program which translates letter grade into grade : Write a C++ program which translates the letter grade into a number grade. Letter grades are A B C D F, possibly followed by + or -. Their numeric values are 4, 3, 2, 1, and 0.
Develop a bipolar transistor amplifier with a voltage gain : The aim of this experiment is to develop a bipolar transistor amplifier with a voltage gain of minus 25. The amplifier must accept input signals from a source impedance of 1 kW and provide an undistorted output amplitude of 5 V when driving a 560..

Reviews

Write a Review

 

Data Structure & Algorithms Questions & Answers

  Create ef?cient algorithm to fnd redundancies

Fnd the redundancies m1, · · · , mn that are within the available budget and that maximize probability that system works correctly. Create an ef?cient algorithm.

  Find terminal nodes in tree nil if pointer is represented

The node's right child. If the nil pointer is represented by 00 and the tree's root pointer contains 53, how many terminal nodes are in tree?

  Create algorithm to perform any sequence of two operations

Let A[1, n] be an array of real numbers. Create an algorithm to perform any sequence of the following two operations: Add(i, x): add the value x to A[i].

  What do you meant by an rfp

Select a specific category of vertical applications to investigate. Use the Internet and any other sources of information you might have to study some of the different products that are available in that category.

  Algorithm to produce schedule for least completion time

What is the best order for sending people out, if one wants whole competition to be over as early as possible? More precisely, provide efficient algorithm which produces schedule whose completion time is as small as possible.

  Determine the mean salary as well as the number of salaries

Determine the mean salary as well as the number of salaries.

  Data structures for a single algorithm

Data structures for a single algorithm

  Determining worst-case time complexity

The recent discovery of the following fragment of uncommented procedural C code in the Sunlab has caused a big scandal. What is the worst-case time complexity of foo(a,1,N,k), and for which inputsdoes it occur?

  Explain method for combining two trees-heap-order property

Assume two binary trees, T 1 and T 2 , hold entries satisfying heap-order property. Explain method for combining T 1 and T 2 into a tree T whose internal nodes hold union of entries

  Create algorithm to calculte and print average earnings

Create the algorithm to calculte and print average earnings, lowest earnings, and highest earnings of group of employees. Each input record will contain name and earnings of one employee.

  Computing minimal length of key-average cracking time given

If Encrypt-It-Rite would like to increase average cracking time to at least 100 years, determine the minimal length of the key?

  Demonstrate a decision tree or table

Demonstrate a decision tree or table

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd