Your boss gives you a list of n of your company’s facilities (and the distances

Question

Your boss gives you a list of n of your company’s facilities (and the distances between them) which she would like to connect with a special network of roads. You know that: (a) Each facility is a positive integer number of miles away from each other facility. (b) Your boss is sure you don’t need to build any road more than 5 miles in length, so, for each facility, she included a list of all of the neighboring facilities within a 5 mile radius. (c) Each mile of road costs $200, 000.

Give an O(n log*(n)) algorithm to help your boss minimize the cost of your company’s road network.

NOTE: The answer does not need to be coded in any language or pseudocode, just give a step-by-step algorithm in english of how to achieve this so that I may be able to understand it.

Explanation / Answer

The two data structures required for this algorithm are

Distance between every two facilities and

List of neighbors within the 5 miles radius for each facility.

Algorithm:

Provide the above discussed two data structures to the algorithm

Repeat a loop n times ( i.e. for each facility Fi)

Check the smallest distance between Fi, Fj , for ij and check whether it is less than or equal to 5 miles or not. If it is less than 5 miles, print a flag to lay road between Fi and Fj.

Stop when all the facilities or nodes are processed.

Step2 runs n times, therefore, it takes O(n) time.

Step3 takes O(log n) to check the distances between every two facilities.

Thus, the total running time of the algorithm is O(n * log n)

Note:

For a loop that runs n times, time complexity is O(n)

For a loop that consists if- else statements (i.e. choice of execution ) , it takes O(log n) time.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.