$2$ Return to $Oz$

Upon returning to Kansas, Dorothy complains that she didn't get to see much of the Land of Oz$.$ She just followed the Yellow Brick Road and missed all the lovely sights off that well$-$worn path. She makes a list of $n$ destinations she would like to visit and asks you to take her. Why? Because you have a blimp $($which is much better than a hot$-$air balloon$).$

So$,$ here is the plan. You approximate $Oz$ as a two$-$dimensional plane. Each of Dorothy's $n$ destinations can be specified by its two$-$dimensional coordinates $(x_i,y_i).$ Although, the blimp is powered and steerable, it is best to drift along with the prevailing winds. From the Munchkins, you find out that in the next month or so$,$ the winds will blow east to west. After that the winds will switch directions and blow west to east. So$,$ you can start in Munchkin Land on the eastern end of $Oz$ and travel west visiting some of the $n$ destinations. You'll end the first portion of your journey at the Wicked Witch's castle and hang out with the flying monkeys for a bit. After the winds start blowing eastward, you will travel east and visit the remaining destinations $($the ones you didn't visit during your westward flights$).$ You end your trip at Dorothy's house which had landed on the eastern edge of the map.

That's a good plan, but you are worried about the available fuel for your blimp and also your carbon foot print. $($Let$\text{'}$s keep Oz green!$)$ Thus, you want to plan this trip so the total distance traveled is minimized. Here are some constraints:

Both Munchkin Land and Dorothy's house are on the eastern edge of Oz$.$ There are no destinations east of these points. Let's say Munchkin Land is at $(x_1,y_1)$ and Dorothy's house is at $(x_2,y_2)$ and $x_1$ is a teeny bit larger than $x_2.$

The distance between two destinations is just the Euclidean distance between their coordinates.

During the first part of your journey, you must fly westward. The destinations that you visit must have decreasing $x$ coordinate. $($Let$\text{'}$s just assume that none of the destinations have the same $x$ coordinate.$)$

Similarly, during the second part of your journey, you must fly eastward and visit destinations with increasing $x$ coordinate.

The Wicked Witch's castle is the most western destination and has the smallest $x$ coordinate. For convenience, let's just assume that the destinations are sorted by decreasing $x$ coordinate. That means the Wicked Witch's castle is located at $(x_n,y_n).$

This all seems rather complicated, but when you meet up with the Scarecrow and he says, "You know, ever since the Wizard gave me that diploma, I've found dynamic programming to be much easier $-$ even though I don't really have a brain!"

Questions:

Define a function, MinDist, that can be used to solve this dynamic programming problem. To do this, you must describe the input parameters to MinDist and its "return value" using English sentences. $($Consider figures on the next page.$)$ Note: describe the value that MinDist must return in relation to its parameters, not how to compute it$,$ that's the next question.

Give a mathematical formula that shows how MinDist can be computed recursively. Then, explain the main parts of the formula in English. Remember to include the base cases.

Describe how MinDist can be computed bottom up using a dynamic programming table. Be sure to include a description of the dimensions of the table and the order that the entries of the table are to be filled. Draw a diagram. Which entry has the solution to the original problem?

State and briefly justify the running time of your dynamic programming algorithm.