Tour Guide

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.

Dijkstra's Algorithm

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.

Importing Data

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.

Testing

You will be expected to thoroughly test your solution with both regular tests and an oracle for your tour-guide:

(oracle (guide : ((listof Tour) number number -> (listof string)))) : boolean

Consider 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.

Analysis

You should also hand in an analysis document addressing the following questions:

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?

What to hand in:

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.