Programming with
Data Structures and Algorithms

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.

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.


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.


You should also hand in an analysis document addressing the following questions:
  1. Analyze the worst-case running time of your dijkstra and tour-guide functions. Show your work, as always!
  2. 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.
  3. 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:

Your analysis must be in a pdf file on Letter-sized paper. Mathematical content must be formatted appropriately. Please, no Arial.