Dynamic Programming toll booths Suppose that you are managin

Dynamic Programming (toll booths)

Suppose that you are managing the construction of a toll road which is M miles long, and you are faced with the task of picking locations for toll booths from a set of n possible locations. The possible locations for toll booths are given as positive integers x_1, x_2, ..., x_n which denote the distance of the location from the beginning of the road (assume that the x_i\'s are in increasing order). Further suppose that for each location x_i, you are given a value t_i which denotes the amount of money you would make in tolls from this location per day. Finally suppose that regulations require that each of the toll booths be at least 10 miles apart. What is the optimal choice of toll booths that makes as much money as possible without violating the constraint on the distance between the booths? Example: Suppose that M = 50 and n = 4 such that {x_1, x_2, x_3, x_4} = {10, 15, 23, 30} and {t_1, t_2, t_3, t_4} = {50, 60, 50, 10}. Then the optimal solution would be to place toll booths at x_1 and x_3 for a total gain of 100. (a) Consider a brute force algorithm that checks every possible placement of toll booths. What is the running time of this algorithm? Justify your answer. (b) Let a[j] denote the optimal solution when considering only the first j possible toll booth locations. Using the example above, we would have a[l] = 50, a[2] = 60, a[3] = 100, and a[4] = 100. Write a recursive definition of a[j] (do not forget the base case). (c) Describe a dynamic programming algorithm based on your recursive definition. Be sure to avoid computing the value for a sub problem more than once. (d) What is the running time of your algorithm? Justify your answer.

Solution

c)recursive definitions are recursive algorithms:
let us consider recursive definiton of fibonaci series
   recFib(num):
       if(num<2)
           return n
       else
           return recFib(n-1)+recFib(n-2)

Here the running time is O(n)
now considering dynamic programming:
   iterfibo(num)
       f[0]<- 0
       f[1]<- 1
       for i <- 2 to n
       f[i]<- f[i-1]+f[i-2]
       return f[n]
d)we can say time analysis as it uses O(n) additions and stores O(n) integers which is our first explicit dynamic programming algorithm