Data Structures and Algorithms

No doubt you remember the campus tour—the walking backwards, the explanation of meal plans, the intramural sports speech... It's a fine tradition, but the admissions department is running out of willing volunteers. That's where you come in–you've been asked to write a program to calculate tours for campus visitors.

It should accept a list of predefined 'tours', such as a 'Campus Art Tour' or a 'Freshman Dorm Tour'. These tours will be supplied by the Admissions Office. If a stop appears multiple times in the list, it need only be visited once.

Unlike normal tours, these tours have no fixed order. Your program should simply move toward the closest unvisited selected stop, even if this results in tours being interleaved.

Locations in the map will be represented by the `Loc`

type.
A `Loc`

includes its name and location, as well as its neighbors and the distances
in meters to those neighbors. Every location will have a unique, unambiguous name.

(define-type Loc [loc (name : string) (latitude : number) (longitude : number) (neighbors : (listof Loc)) (distances : (listof number))])Tours will be represented by the

`Tour`

type.
A `Tour`

stores the name of a tour and a list of its stops' names.
(define-type Tour [tour (name : string) (stops : (listof string))])

The Admissions Office wants a program that provides the following tour-calculating function:

(tour-guide (tours : (listof Tour)) (start-lat : number) (start-lon : number)) : (listof string)

`tour-guide`

produces a list of location names to walk through,
ordered from first to last (including intermediate sites like street corners),
to complete the given tours according to the specifications above.
Since the user might not begin their tour standing at a site on the map, your
`tour-guide`

should first find the site closest to the starting position,
and then continue to the nearest selected tour stop. Remember, you will be
outputting a single path that visits all stops in all the selected tours.
The map data you receive will contain many sites that are not tour stops, such as intersections and intermediate landmarks. All map sites, together with the paths between them, form a graph.

In order to find routes of map sites, your program will need
to find shortest paths on a weighted graph. You should use Dijkstra's
algorithm to take in a starting location from the map and
return a collection of information about each site, including
the length of the shortest path from the starting site to
the current site, and the previous site along that path.
Your implementation of Dijkstra's algorithm should have the
following contract, where `'m`

is a type with the
above site information:

(dijkstra (start : Loc)) : collection of 'm

Your `dijkstra`

should run in O([`s` -> `s * log s`]) time,
where `s` is the number of vertices in the graph.
Note that a complete graph (with an edge between every pair of vertices) would
have `(s(s-1))/2` edges, making this impossible.
However, graph representations of real maps are not so densely connected,
and you may assume that each vertex has only some constant number of neighbors.

In addition to the types `Loc`

and `Tour`

described above, mapdata.rkt contains the following definitions and helper
functions.

loc-list : (listof Loc)

`loc-list`

provides a complete list of all the locations on the Brown map that your program will be processing.tours : (listof Tour)

`tours`

provides a list of the tours from the Admissions Office.(get-dist (latA : number) (lonA : number) (latB : number) (lonB : number)) : number

`get-dist`

takes the latitude and longitude of two locations, and returns the approximate distance in meters between them.(get-loc (name : string)) : Loc

`get-loc`

returns the`Loc`

in`loc-list`

with the given name.

`tour-guide`

:
(oracle (guide : ((listof Tour) number number -> (listof string)))) : booleanConsider what criteria you might test to consider a tour-guide result to be a valid tour and how you might test its optimality by using a brute-force search instead of Dijkstra's algorithm.

- Analyze the worst-case running time of your
`dijkstra`

and`tour-guide`

functions. Show your work, as always! - As is, your
`tour-guide`

always visits nearest unvisited selected stop. Is this optimal? That is, does this algorithm create the shortest path visiting all the selected tour stops? If so, explain why this is true. If not, provide a counter-example. - Explain your testing strategy. How did you design your oracle, and how do your oracle testing functions evaluate the correctness of your tour guide?

`tour_guide.rkt`

, which contains your implementation of the entire Tour Guide program.`analysis.pdf`

, which has your answers to the analysis questions

Your analysis must be in a `pdf`

file on Letter-sized paper. Mathematical content
must be formatted appropriately. Please, no Arial.