Extra Credit Assignment 1

This extra credit assignment is worth 5 points (the same amount as a homework). You wont get any credit until you get the full credit (i.e., if you turn in a half completed project, you wont get any credit). You may submit it as many times as possible. This assignment must be completed by November 31st.

Your task is to create a mapping program for Maryland. Your program will use A* to calculate the shortest path from city to city. For example, when the program is asked to go from D.C. to Ocean City, the output gives D.C.->Annapolis->Cambridge->Ocean City - 120 miles (results may vary!).

First, generate a data set. For each city, figure out where it is. For example, you can find the coordinates on wikipedia. This way, you can calculate "as the bird flies" distances from between cities. Then, figure out how long google maps says it takes to get from place to place. For example, Baltimore to D.C. is 38.6 miles.

Create a data set of cities (small and big) and connections. Pick 20 cities in the Maryland area and figure out their coordinates on the globe. The connections between cities specified should be very local. For example, there is no direct route from D.C. to Ocean City so there should not be an edge between these two without going through other nodes (Cambridge and Annapolis). If you want some suggestions on how to set up this data file, send Don an email.

Reminder:
Given a node x... f(x) = g(x) + h(x)
g(x) is the shortest path from the start location to the node x. This is an exact calculation that adds up the google maps driving distances from the start node to x.
h(x) is the heuristic -- the straight direction distance from x to the final node.

What to turn in:
- Your source code implementation of A*, in the language of your choice. Your algorithm should print a lot of information about how the algorithm is running -- e.g., nodes explored, heuristic values, etc.
- Your data set that gives the cities, their locations, and edge information in a text file.
- A user manual that describes how to compile, run and use your program.
- A write-up that discusses how many nodes on average are explored, a few example runs that show how well your algorithm works, any challenges, etc. you might want to talk about.

Send these things to Don when your project is complete.