CMSC 206: Data Structures
Assignment#3

Due on Tuesday, October 4, 2016

In this exercise, we will essentially do something similar to your Assignment#1 but embellish in two ways:

• [VERY IMPORTANT] Use a different data structure (Java ArrayList) to store the dataset
• [ALSO IMPORTANT] Modify the Place class to store population data (total population, # females, #males) (See description of data set in Assignment#2)

1. First, make a copy of your Assignment#2 (call it Assignment3). Then begin by changing the main data structure from an array to an ArrayList. Make sure your program behaves exactly like the one in Assignment#2, but using an ArrayList of Place objects.
2. Next, modify the program from Step 1 to include, in the Place class, fields (instance variables) for the population data. Warning: some of the entries do not have population data. Why? If any data is missing about a place, assume it is 0.
3. Next, modify your program so that, given an input town name and its state (instead of the Zip code), searches the list for the name of the town and state, and then prints out all the information it knows about it, in the following format:

   Query: Cambridge, MA
   Found...
   Town: Cambridge, MA, 02138
   Population: 36314 (19240 Female, 17074 Male)

[Hint: You will need to modify the equals() method in the place class.]
Also, change your program so that all input and output in this program will be from the Console Window (see page 658 of your text). A user may misspell the name of a town or enter the name of a town that does not exist (i.e. not contained in your database). In that case, just print out a message to that effect and continue to query for the next town. You should be careful about the case-sensitivity of the town/state names. One way to avoid any problems is to convert the strings being compared to all upper or lower case.

Note that you are only searching for the first occurrence of the town querried. Depending upon the size of the town, it may have several zip codes and hence several entries (e.g. Cambridge, MA). Extra Credit for a suggestion to implement when there are multiple zip codes in a town (this is optional and do not attempt this until AFTER you have completed the assignment).

For demonstrating the correctness of your program, test your program for the follwoing inputs:

1. Cambridge, MA
2. Jim Thorpe, PA
3. Your birth place (if in the US), or pick your favorite US town
4. Bryn Mawr, PA
5. Boring, OR
6. Hell, MI
7. Pie Town, NM
8. Surprise, NY
9. Joe, MT
10. Romance, AR
11. Mars, PA
12. Okay, OK
13. Rough and Ready, CA
14. Accident, MD
15. Good Grief, ID

Once you have completed the program, extend it to count the number of comparisons needed to answer a query. Then, for the input data above, compute and output the following:

• the number of comparisons needed to answer each query
• the average number of comparions needed to answer a query
• the average number of comparisions needed to answer a successful query
• the average number of comparisons needed to answer an unsuccessful query

To show your output (only the latest version of your program is sufficient) cut and paste the contents of the Console Window in a text/Word file and print it. Additionally, hand in a prinout of the complete Java program.

Work on your program one piece at a time. And then add the statements to count the number of comparisions.

What to Hand-in:

1. A complete printout of the latest version of your program(s)
2. A prinout of your program showing the outputs from the queries above and the comparison data as described above

Extra Credit:

Many towns have several zip codes. For example, Cambridge, MA has five zip codes, Buffalo, NY has over 40 zipcodes. Each zipcode may have its population data. Extend the program to aggregate the population data for each zipcode in a town when printing results. Do this for these towns: Cambridge, MA; Buffalo, NY; Cut and Shoot, TX; Cool, CA; and New York, NY.

Back to CS206 Course Materials