CS 151 - Introduction to Data Structures

Homework 3

ArrayList - Zipcode lookup

Due Sep 22, prior to 11:59:59 PM

Overview

Rather than using List151Impl you can use the Java-standard ArrayList. If you want to use List151Impl that is OK.

Reuse all of class design from the previous assignment for storing information. If you want to improve your class design that is good. If you lost points in assignment 2 for class design, you will loose only 0.75 times the points in assignment 3. (I will grade assignment 2 before assignment 3 is due.)

Data

shuffzip.csv

      "00705","STANDARD","AIBONITO","PR","PRIMARY",18.14,-66.26,"NA-US-PR-AIBONITO","false",,,
      "09005","MILITARY","APO","AE","PRIMARY",,,"EU-DE-WEISBADEN AAF OMDC","false",,,
      "10029","STANDARD","NEW YORK","NY","PRIMARY",40.71,-73.99,"NA-US-NY-NEW YORK","false",31490,48403,1050141146

0. zip code
1. type -- ignored
2. city name
3. state abbreviation
4. type 2 -- ignored
5. Latitude
6. Longitude
7. long code -- ignored
8. true or false -- ignored
9. population 1
10. population 2
11. another number -- ignored

For this assignment we care about only: zip code, city name, state, latitude, longitude and population 2. Some lines are missing the longitude and latitude (like the second sample line), some are missing population, but all lines have the correct number of commas (11). There are no lines for which the longitude and latitude are not known but the population is known.

Given this final statement, the data falls into 3 groups: 1: those for which location and population are known, 2: those for which only location is known, 3: those for which neither location nor population is known. You first task is to design a set of java classes so that each of these groups can be stored in a instance that is capable of storing the available information, and no more. These java classes MUST be linked to each other using inheritance. For instance, if you define a class Place that stores group 3 data, then you might make a class

      public class LocatedPlace extends Place

      public class PopulatedPlace extends LocatedPlace

Requirements

• (Repeated from hw2) You must store data in classes you create. These classes should hold exactly as much information as is contained a row of the data file. You may use the class design suggested above for your classes.
• (Repeated from hw2) You MUST use inheritance in your class design.
• The only Data Structure you should use in this assignment is ArrayList (or List151Impl). You may use only one instance of ArrayList
• You may read the contents of shuffzip.csv at most once.
• The information in the ArrayList MUST be kept in order by zip code. The contents of the ArrayList should always be in sorted order. Thus, after reading a line from the file, you must determine at what location it should be added to the data already in the ArrayList, and then use the add(iindex, item) function to do that insertion.
• The function you use to determine where to add information must run, on average, in N/2 time. Phrased alternately, the worst case run time for adding one item to the ArrayList should be O(n), where n is the number of items currently in the ArrayList.
• You must write you own search function to be used during user interaction. (It need not be generic; in fact it should not be generic.) The search must take advantage of sorted order to run, on average, in N/4 time. Its worst case run time should be N/2. (Hint, start in the middle of the list.). Later in the semester we will discuss how to do even better, with worst case of O(lg(n)) for an algorithm that knows nothing about the data other than that it is sorted. (If you know that algorithm; do not use it here.)
• (Repeated from hw2) After reading in the data, your program should support user interaction similar to the following:

  Enter a zip code to lookup (00000 to quit): 19380
          West Chester,PA 19380       Pop:43281  Lat:39.95  Lon:-75.60
  Enter a zip code to lookup (00000 to quit): 07040
        Maplewood,NJ 07040       Pop:20973  Lat:40.73  Lon:-74.27
  Enter a zip code to lookup (00000 to quit): 00614
        Arecibo,PR 00614       Lat: 18.45  Lon:-66.73
  Enter a zip code to lookup (00000 to quit): 09848
        Apo,AE 09848
  Enter a zip code to lookup (00000 to quit): 88888
        Not Found
  Enter a zip code to lookup (00000 to quit): q
  Goodbye
        

• (Repeated from hw2) All printing of information about a place should be done from toString. So, for instance, in the above interaction all of the printout of search results (other than "not found") should be done with a single line which might look like
  System.out.println(place);
• (Repeated from hw2) Encapsulation. All classes should expose only that which other classes need. There should be no public instance variables
• (Repeated from hw2) Statics. Do not use any static variables or static methods.
• Use one of the methods discussed in lab (Sep 14) to collect the output of your program. The output should show your program on at least the following zip codes:
  • 19010
  • 07040
  • 09311
  • 81288
  • 16427

Electronic Submissions

1. README:

The following steps for submission assume that you created a project directory named Assignment3 in the directory /home/YOU/cs151/

1. Put the README file into the project directory (/home/YOU/cs151/Assignment3)
2. Go to the directory /home/YOU/cs151/Assignment3/
3. Enter /home/gtowell/bin/submit -c 151 -p 3 -d Assignment3