5.** Exercise E3.15 of the textbook. There is a highway with n exists numbered 0

Question

5.** Exercise E3.15 of the textbook.

There is a highway with n exists numbered 0 to n - 1. You are given a list of the distances between them. For instance:

Exits: 1 2 3 4 5 6

Distances: 5 3 4 2 8 6

The distance from the start of the highway to exit 1 is 5, from exit 1 to 2 is 3, and so on.

You have to devise an algorithm that would calculate the distance between any two exits. Imagine that this distance function is called millions of times by applications that need this information, so you need to make your algorithm as fast as possible.

Describe your algorithm. What is the worst-case big O running time? Make sure to state all the parameters you use in the analysis and relate them to the algorithm.

Explanation / Answer

Create Global array exitpairDistance[N][N] where N is length of exits

build exitpairDistance

for i = 1 to N do:

for j = 1 to N do:

  exitpairDistance[i][j] = exitpairDistance[i][j-1] + distance[j]

GetDistanceBetweenTwoExits(Exits, Distance, exit1, exit2)

return exitpairDistance[exit1][exit2]

As you can see creating exitpairDistance takes O(N^2) and then getting any exit distance is just constant amount of work

Related Questions

Navigate

• Browse (All)
• Browse 5
• Subjects

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