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 virtual tour guide that will run on a visitor's cell phone. Users can select the type of destinations they wish to see and receive real-time directions from their current location to the nearest destination.

Specifically, the Admissions Office wants an application with the following features:

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 footpaths between them, form a graph. Since these sites are fairly large, each site will have a specified radius; if the user's current location is within this radius, your program should assume that the user has reached this site (this also helps compensate for GPS inaccuracies).

When the program starts and tours are first selected, your program should find the user's current location. If the user is at a site on the Admissions Office map, your program can give directions from that site to the closest tour stop. Otherwise, your program should first direct the user on the straight-line path toward the nearest site on the map. Once the user has reached a map site, you can proceed to give directions from that site to the desired tour stop.

Once the user reaches a tour stop, your program should display the description until the user is ready to progress. When the user is ready to travel to the next tour stop, the program should construct the shortest route and lead the user to the map sites on this route in order. While directing the user from one map site to the next, your program should give constantly updating heading and distance to the next map site. This way, if the user starts walking in the wrong direction, the distance to travel should increase to reflect the increasing distance to this next map site.

However, if the user gets way off track or decides to take an alternate route, your program should notice and respond accordingly. If the user gets far enough off track that they arrive at a site on the map other than the one they were being directed to, your program should recalculate the closest unvisited tour stop and route of map sites to reflect the user's new location. Your program should also allow the user to tell the program to recalculate if, for instance, the user gets lost. When this happens, your program should once again direct the user on the straight-line path toward the nearest site on the map.

Dijkstra's Algorithm

In order to find routes of map sites from the user's location to a tour stop, your program will need to find shortest paths on a weighted graph. You should use Dijkstra's algorithm, which you will learn about in class, to achieve this functionality.

Your implementation of Dijkstra's Algorithm should have roughly the following signature:

Dijkstra: graph node -> collection of distances and previous nodes

The exact data definition is up to you, but Dijkstra's algorithm needs to take in a graph and a starting node from that graph and return some collection (vectors work well) of information about each node. This information should include both the total distance from the start node to the node in question and the previous node along the shortest path from the start node to that node. Your algorithm should run in O(nlogn) time with respect to the number of nodes in the graph.

Design Check

Once you have a working implementation of Dijkstra's algorithm, start thinking about how to apply it to the problem at hand. Remember that you need to lead the user between many different tour stops and dynamically update the directions. Plan out your user interface, and think about what GUI functionality you will need to produce a satisfactory product.

This assignment will have a design check, in which you and your partner meet with a TA to discuss what you have completed and your design for the remainder of the assignment. The design check will be part of your grade, so make sure you sign up for a slot by Sunday. There is be a sign-up sheet on the door to the Fishbowl (CIT 271, at the top of the front stairs).

At the design check you will be asked to:

Make sure you have thought about all the edge cases that can come up. For example, the same location might end up being part of two tours–what issues might this cause? Do some real brainstorming. There are a lot of little things you can add and/or fix to make your program better. Doing well on this project requires thinking of and implementing a good number of them (though not necessarily specific ones, or even one's we've thought of!).


To make your application run on a cell phone, you'll need to use Moby, a specialized Scheme compiler. To do so, you will need to switch DrScheme to the Module language, and include the line:

#lang planet dyoo/moby:2:20

at the top of your main source file (and any files you include; see below.)

DrScheme will install Moby the first time you run a Moby program. If issues with Moby, which is still under development, arise during the course of this project, the '20' might change; this will be announced to the course list.

Moby comes with a version of Universe, which you will need to use to create an interactive user interface. Moby's Universe is different from the one you used earlier in the course; in particular, it adds the functions js-big-bang and on-location-change and the contract of on-draw to take two two handlers. For further details, visit and click on the 'docs' link for the latest version.

Note: Some of this documentation assumes knowledge of HTML and CSS. We do not assume you already have this knowledge, so if you need help please come talk to us!

You can test your application entirely in-browser by providing test coordinates. When you click 'Run' in Moby, your program will open your default browser. You will of course eventually need to do actual field tests on a phone to ensure that your program works with real-world coordinates and tours as you think it should. We have several Android phones for you to work with; a schedule for checking them out will be discussed in class or emailed to the list in a few days.

Importing Data

Once you've run some basic tests on your program, grab the actual Brown map data from You can use the include keyword to pull in content from an external file so you don't have to paste the whole mess of data into your program. contains the following struct definitions and helper functions. The map data is given in terms of the structs, and you will find the functions provided very useful.


This is a very large project. It is your job to nail it down a set of concrete specifications, and the best way to do this is to build yourself an extensive testing harness before you dive into coding. Make sure you can quickly find out, for instance, whether a given version of your code still correctly handles the user getting lost and pressing recalculate, or adding a tour, visiting some of its stops, dropping the tour, and then re-adding it.

A further complication is that you have very limited access to the phones. This makes testing even more important! You would be wise to build yourself a testing harness.

Using the Phones

To install your application on the phone, you first need to download the .apk file from the page that pops up when you run your code with Moby. Once you have the file, plug the phone into a USB port on the machine. This may be a little tricky with some of the sunlab machines, but the ports are there. Once you have the phone pluged in, open a terminal and type

adb install <apk-file>
where <apk-file> is the path to the apk you just downloaded.

When you are ready to turn the phone back in, you must uninstall your application. This prevents the next group from looking at your work, it prevents other people from having trouble installing their app if it has the same name, and it insures the phone does not have tons of apps on it later.

To uninstall your app, hit the Menu button on the phone. From there go to Settings -> Applications -> Manage applications. Then scroll down until you find your app, click on it, and hit Uninstall.

Note on Getting Coordinates: The phones have two ways of getting coordinates: GPS and WIFI. Unfortunately, the GPS is extremely unreliable when it is cloudy, and the WIFI is extremely inaccurate. Feel free to try either option, but be aware of these problems. To switch between them, hit the Menu button on the phone. Then go to Settings -> Security & Location, and select the option you want.

What to hand in: