CS 311 Algorithms and Complexity
Spring 2007

Programming Project 4

Introduction

The Manhattan Distance between points is the sum of the differences of their coordinates. In particular, if p₁=(x₁, y₁) and p₂=(x₂, y₂), then the Manhattan distance between p₁ and p₂ is |x_1- x₂| + |y_1- y₂|. In this assignment, you are to implement the O(n log n) closest-pair algorithm using the Manhattan distance metric.

Activities

Write a class called ClosestPairManhattan that takes one argument, the name of a file that contains data representing a number of points on the plane and returns a report that gives a closest pair of points and their distance apart using the Manhattan distance. We will only consider points with integer coordinates. Each line of the file contains the coordinates for one point with the first number as the x-coordinate and the second number as the y-coordinate.

Sample Data

Using the file in.dat, my implementation finds the distance between a closest pair to be 6 with a sample pair of points to be (-23, 251) and (-22,256). I do not know if my implementation is correct. Please let me know if you get different results.

memo.doc

In your memo.doc write a brief report that describes potential applications of the Manhattan distance metric. What is it used for and why?

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.txt

· ClosestPairManhattan.java

· 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
ClosestPairManhattan	Correct implementation of the algorithm	Mostly correct implementation of the algorithm	Mostly incorrect implementation	30
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.txt
Manhattan Distance	Provides a clear description of the significance of the Manhattan distance metric.	Provides a mostly clear description of the significance of the Manhattan distance metric.	Provides a mostly unclear description of the significance of the Manhattan distance metric.	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