Calculate worst-case run-time complexity of algorithm

Assignment Help Data Structure & Algorithms

Reference no: EM1350523

Q1) Consider a straight road with houses scattered very sparsely along it. You want to place cell phone base stations at certain points along the road, so that every house is within four miles of one of the base stations. Give a greedy algorithm that achieves this goal, using as few base stations as possible. Compute the worst-case run-time complexity of your algorithm and prove the optimality of the solution it gives.
Assume that the road is a straight line with a western end and an eastern end. The input would be the distance of each house from the western end. A sample input would be:

House number 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

Distance 10 36 21 30 47 44 16 31 25 54 13 39 6 19 53

The output should be the locations of the base stations. For this example, you'll need 5 base stations.

Reference no: EM1350523

Questions Cloud

Explain what are the characteristics of each of cultural : Explain What are the characteristics of each of the following pairs of cultural characteristics derived from Trompenaar's research

Calculate the expected return on each stock : Assume you have invested in two stocks, stock Y and stock Z. The returns on the two stocks depend on the following three states of the economy, which are equally likely to happen.

Best forms of employee testing : Determine the types of employee testing that companies may require that are discussed (Personality Testing - measures patterns of though, emotion and behavior.

Illustrate what would be the equivalent value today : A similar helicopter was purchased 4 years ago at a cost of 140,000$. At an interest rate of 7% per year. Illustrate what would be the equivalent value today of that 140,000$ expenditure.

Calculate worst-case run-time complexity of algorithm : Calculate the worst-case run-time complexity of your algorithm and prove optimality of the solution it gives. Suppose that the road is a straight line with a western end and an eastern end.

Concept of territory and aggression : He was fighting to protect what was his (his brother) and him being territorial along with protecting what was his brought this whole thing to a head in the hallway of the school today. What are your thoughts on this?

Examine two additional ways that employee layoffs : Evaluate three ways that employee layoffs can affect other employees in the organization and examine two additional ways that employee layoffs can affect the organization as a whole.

Find the expected earnings : A company currently earns $1 per share. A financial analyst believes that earnings will grow yearly at the rate of 10% for five years and then decline to 5%.

Explanation cash conversion cycle question : Conversion Cycle. What effect will the following have on the cash conversion cycle?

User Account

All Pages