Design an algorithm that calculates the minimum distance people would have to wa

Question

Design an algorithm that calculates the minimum distance people would have to walk, under the best selection of walkways.

a) Define a quantity A[k] that you will compute and store in a table. Describe in English what this quantity represents.

b) Give a reccurence for A[k], as well as the base case. Also, describe the order in which the table should be filled in.

c) Give the pseudocode & running time of the algorithm.

----------------------------------------------------

To help you, imagine the following example:

Suppose you are given N and a set of m pairs { (s1, t1),(s2, t2), . . . ,(sm, tm) } indicating all the places it would be possible to install the walkways. Pair (si , ti) indicates that it would be possible to install a walkway going from point si to point ti You may assume that si < ti in all pairs (si , ti). Important: You may also assume that the pairs are sorted in increasing order of ti, so ti ti+1.

Note: The values si and ti might not be integers and the running time of your algorithm should NOT depend on N.

The hallway is N feet long, and it stretches from [0,N]. For example, suppose N = 10 and the installation pairs are { (1, 4), (3, 8), (5, 9), (8.5, 10) }.

Installing the walkways corresponding to (1, 4) and (5, 9) would result in people having to walk a distance of 3 feet, the minimum distance possible. So your algorithm should return the value “3 feet” on this example.

Explanation / Answer

Best algorithm is Brute force algorithm

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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