Exercise 2. DYNAMIC PROGRAMMING: COMPUTING THE OPTIMAL STAR. We are given a matrix of pairwise distances D[i,j] between cities i and j, where 1 Sij Sn. These must be connected in a star, i.e., there is a central city (the core of the star), which, when it is removed, leaves one or more chains. The objective is to design a dynamic programming algorithm to find the connection of smallest total length. Observe that we restrict the star to one tentacle (chain), then this is the shortest traveling salesman path problem that we solved in class. Please make sure that your solution does not use more than exponential time (in n). Exercise 2. DYNAMIC PROGRAMMING: COMPUTING THE OPTIMAL STAR. We are given a matrix of pairwise distances D[i,j] between cities i and j, where 1 Sij Sn. These must be connected in a star, i.e., there is a central city (the core of the star), which, when it is removed, leaves one or more chains. The objective is to design a dynamic programming algorithm to find the connection of smallest total length. Observe that we restrict the star to one tentacle (chain), then this is the shortest traveling salesman path problem that we solved in class. Please make sure that your solution does not use more than exponential time (in n)