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 : (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([s -> s * log s]) time where s is the number of nodes in the graph.

Note that if the graph is well-connected, you have to examine s^2 connections, and the algorithm would run in O([s -> s^2]) time. However, the graphs we are working with, and in general any graph representation of a real-world map, are inherently not well connected. Your algorithm should run in O([s -> s * log s]) time with respect the number of vertices, assuming each vertex has only up to some constant number of neighbors.

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 Tuesday. The design checks will take place Tuesday and Wednesday. There is 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 run racket on mobile phones you will be using a new language called Whalesong, which compiles Racket to Javascript that can be run in the browser of any smartphone or desktop machine.

Instructions for using Whalesong can be found at:

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!

Opening the generated HTML file can let you test your application entirely on a desktop machine. 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 will distribute Android phones for you to test on, and we will be using these phones to grade so be sure to test with them.

Importing Data

Once you've run some basic tests on your program, require mapdata.rkt to get the actual Brown map data.

mapdata.rkt contains the following 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.

Using the Phones

To access your generated HTML and Javascript on a smartphone use our cs019-upload script to upload them to the web to be loaded from anywhere. Simply run the script with any necessary files as arguments.

$ cs019-upload tour_guide.html tour_guide.js tour_guide.appcache ...

The script will then output a URL you can visit from another machine or a smartphone for testing.

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 -> Location & Security, and select the option you want.

What to hand in: