CS 311 Algorithms and Complexity
Spring 2007

Programming Project 7

Introduction

Doris “Granny D” Haddock walked across America at age 89 to bring awareness to the issue of campaign finance reform. I propose another walk visiting all cities in towns in Greater Boston (I’ll do more when I’m 89!) to bring awareness to another important issue of our times – eliminating the designated hitter in American League baseball.

The idea of this project is to help me plan my walk across eastern Massachusetts. The idea is to write code that will find an approximate shortest tour that visits all of a collection of geographic places.

Activities

Here are things you will need to work on this project:

Data

The file greater_boston_concise.txt contains geographic data about cities in Greater Boston from the US Geographic Names Information Service. They provide several text file formats for data about geographic features in the US.

We will be using the concise format. Each 132-byte line in a concise format file contains data about one geographic feature. The data are organized in columns as follows:

Columns	Contents
1-50	Feature Name
52-60	Feature Type
62-92	County
94-109	State
111-117	Latitude
118-125	Longitude
127-131	Elevation

You will need to know how to calculate the distance between two coordinates on the earth’s surface. You could use Great Circle Distance that takes into account the curvature of the earth. Instead, we’ll assume the earth is flat and use the usual formula for calculating distance on a plane, using the (x,y) coordinate for each location to be (latitude, longitude).

Data Structure

The idea is to build a Euclidean Graph based on the cities and towns in Massachusetts. A Euclidean Graph is a complete graph where vertices represent locations (a city or town), and edges represent the geographic distance between each pair of vertices. You can use net.datstructures.AdjacencyListGraph class in your implementation.

Algorithms

There are two graph algorithms you will need to implement:

· Kruskal’s mimimum spanning tree algorithm. Use Kruskal’s Algorithm (Section 7.3.1) to find a minimum spanning tree of the graph. You will use the minimum spanning tree you find to determine an approximation of a traveling salesperson tour of the cities and towns.

· Approximation of a traveling salesperson tour. A tour of a graph is a spanning cycle (e.g., a cycle that goes through all the vertices). A traveling salesperson tour of a weighted graph is a tour that is simple (i.e., no repeated vertices or edges) and has minimum weight. No polynomial-time algorithms are known for computing traveling salesperson tours. The traveling salesperson problem (TSP) is a major open problem in computer science, i.e. find a polynomial-time algorithm computing a traveling salesperson tour or prove that none exists.

A good approximation of a traveling salesperson tour on a Euclidean graph can be found quickly using a minimum spanning tree. The idea is to find a Eulerean circuit around the spanning tree which is a non-simple cycle formed by walking along the tree, keeping the edges of the tree to the left (page 81-82 in the text). We convert the Eulerean circuit C to an approximate TSP cycle M by using the following algorithm: suppose v is a vertex already on M. Follow C from v and add the edge (v,w) where w is the first vertex on C following v that is not already in M. The following diagram demonstrates the algorithm:

Visualizing Your Result

We provide you with three classes that you should use to generate a kml file of your results that can be viewed with Google Earth. You will need to take these classes into account in the design of your solution:

· Place.java – represents a place on the map. These correspond to vertices in the graph

· Connection.java – represents a connection between places. These correspond to edges in the graph

· KMLGenerator.java – a utility class that generates KML for your solution. You will need to pass this class 4 lists that you should construct during the execution of your algorithm:

· a list of places representing each cite

· a list of connections in the original graph

· a list of connections in the MST

· a list of connections in the final route

memo.doc

In your memo.txt describe your design. In particular, explain how you chose the classes and methods you use. What choices did you make? Also, explain how to run your application.

Turn in

By the due date and time, zip and email me a directory that contains any files you want me to consider. This directory should have in it:

· memo.doc

· Any other java files we need to run your application

Assessment

We will use the following rubric to assess your work on this project:

Attribute	Advanced	Proficient	Needs Improvement	Maximum Pts
Behavior
Kruskal’s Algorithm	Correct implementation of the algorithm	Mostly correct implementation of the algorithm	Mostly incorrect implementation	15
Approximate TSP	Correct implementation of the algorithm	Mostly correct implementation of the algorithm	Mostly incorrect implementation	15
Design & Code
Class Design	Uses a clear and understandable class design.	Uses a clear and understandable class design.	Uses an unclear and/or non-understandable class design.	7
Code Style	Uses good code style.  Code is mostly self-documenting.  Javadoc comments for each class and method.	Mostly correct with some comments.	Mostly not correct.  Poor code style.	3
memo.doc
Design Description	Provides a clear description of design choices	Provides a mostly clear description of design choices	Provides a mostly unclear description of design choices	8
Grammar and style	Well written. No obvious grammar or punctuation errors. A pleasure to read.	A few grammatical errors such as punctuation or spelling, although most errors do not interfere with the overall message or the substance of the text.	May grammatical errors including punctuation, spelling or usage problems.	2
Total				50