CS 206: Data Structures
Exercise#16

Due on Tuesday, April 17 (New extended date!)

 

Part 1: Redo Exercise 15 so that instead of using 1 enrty in the list per zip code it uses 1 entry per town (with a list of all zip codes). This was discussed in class on Thursday.

For demonstrating the correctness of your program, include a printout that shows the output from following queries:

  1. Cambridge, MA
  2. Crapo, MD
  3. Your birth place (if in the US)
  4. Bryn Mawr, PA
  5. Boring, OR
  6. Hell, MI
  7. Walla Walla, WA
  8. Surprise, NY
  9. Joe, Montana
  10. Romance, Arkansas
  11. Mars, PA
  12. Nuttsville, VA
  13. Rough and Ready, PA
  14. Dynamite, WA
  15. Good Grief, Idaho

After obtaining all the answers, compute 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.

Part 2: Change the list used to store the towns from a LinkedList to an ArrayList. Also, when creating/reading the list, make sure that the data is stored in ascending order of town+state names. This will enable that the resulting list is a sorted town+state list. Implement a binary search algorithm to query the town+state names. Redo the queries above and compute the avarage comparison times.

Hand in a prinout of the complete program from Part 2 and the outputs from Part 1 and Part 2.

Technical Notes:

All the details of implementation were discussed in class on Thursday. Consult your notes.

You will need to use the String method compareTo which can be used as follows:

If s1 and s2 are two strings then

	s1.compareTo(s)

will return 0 if s1 and s2 are equal, <0 if s1 is less than s2, and >0 if s1 is greater than s2.

 

Back to CS206 Course Materials