In certain island of the Caribbean there are N cities, numbered from 1 to N . For each ordered pair of cities (u, v) you know the cost c[u][v] > 0 of flying directly from u to v. In particular, there is a flight between every pair of cities. Each such flight takes one day and flight costs are not necessarily symmetric. Suppose you are in city u and you want to get to city v. You would like to use this opportunity to obtain a frequent flyer status. In order to get the status, you have to travel on at least minDays consecutive days. What is the minimum total cost c(u, v) of a flight schedule that gets you from u to v in at least minDays days? Design a dynamic programming to solve this problem. Assume you can access c[x][y] for any pair x, y in constant time. You are also given N, u, v and minDays N

Hint: one way to solve this problem is using dynamic states similar to those on Bellman-Fords algorithm.

Answers Needed:

(a) Define the entries of your table in words. E.g., T (i) or T (i, j) is ....

(b) State recurrence for entries of table in terms of smaller subproblems.

(c) Write pseudocode for your algorithm to solve this problem.

(d) Analyze the running time of your algorithm.