Start with your $($ideally working$)$ submission of Deliverable A$.$ Read a file of the name

$$F$[]$b$.$txt$.$ This is a file of distances between cities in which the value of each city is a floating

point number that lists either the latitude or longitude of each city.

Using the algorithm in one of the two papers on bitonic tours that I gave you, find the shortest bitonic tour

going from the highest value to the lowest value, then back to the highest value for each set of cities$\mathrm{.}1$

The $$prog$340$ handout describes the format of the input file for this and all program deliverables.

As will always be the case in this class, the program must be written in Java and must run on the

University Windows computer systems. To ensure this I strongly recommend that you:

$1.$ Use only Oracle Java $18$ SE and earlier constructs, and

$2.$ Test it on the University systems before submission if you have any doubts about its ability to run on

the University Windows.

Submit the Java source code to the open Deliverable B submission folder. You may submit either the

source code or a full Eclipse package.

Algorithm:

The bitonic tour algorithm is described in the two bitonic tour papers uploaded under DelivB. Use

whichever algorithm you find easiest to understand $($they$$re essentially similar and will give identical

results$).$

Output:

The input will be a table of distances representing a graph, like the one below. The largest graph I will

test with will have $49$ cities.

~ val C D F M N S W

Chicago $41\mathrm{.}9$ ~ $1004967398473296863$

Denver $39\mathrm{.}71004$ ~ $79492411588501097$

FortWorth $32\mathrm{.}8967794$ ~ $9446636311297$

Minneapolis $45\mathrm{.}0398924944$ ~ $875557458$

Nashville $36\mathrm{.}24731158663875$ ~ $3091338$

SaintLouis $38\mathrm{.}7296850631557309$ ~ $1013$

Winnipeg $49\mathrm{.}98631097129745813381013$ ~

Yields output:

Shortest bitonic tour has distance $4015$

Tour is W M C S N F D W

Submit:

Submit your code as an Eclipse package, or submit all the $.$java$$ source files in a zipped archive. Do not

include test files.

Test Files:

The $$a$$ test files I uploaded for Deliverable A don$$t work with this deliverable, you will need to test with

some or all of the $$B$$ test files that I upload. Five test files are in the zipped archive I have uploaded. I

will use some of these files for grading, and others, too. I will definitely use file F$5$b$.$txt$,$ the $49-$city file.

$1$ This will correspond to north $$ south $$ north or west $$ east $$ west, depending on the set of cities $($i$.$e$.,$

depending on whether the value is latitude or longitude$).$