Skip to main content

Homework 4: HW04 Binary Search - Zipcodes again

Due: 2024-10-20 23:59:00EDT

Overview

Lab 6 (Iterators)

Since Lab06 was more involved than the other labs, Lab06 will count towards this homework grade.

Rewrite your HW 1 to use more efficient searching techniques. In order to use binary search, your list must be sorted. Depending on your implementation (which file you scanned in first), your ExpandableArray may already be in lexicographic order after you are done processing. If it is sorted, you can move on. Otherwise, sort your list after processing.

LookupZip

Modify the lookupZip method to use binary search instead. You must implement a binary search from scratch and you are not allowed to use Java’s built-in Collections.binarySearch. Note also that object comparisons should be done via compareTo.

If you didn’t call lookupZip when you were weaving in the data from ziplocs.csv, you should rewrite that other lookup method to use your binary search too.

Requirements.

The rest of the restrictions and requirements for Assignment 1 remain. Testing should use the same test inputs and outputs as Assignment 1 as well.

Testing

For this assignment you do not need to write any JUnit tests. However, your code must pass the checkstyle.

In this assignment we will use commandline redirection.

Instead of typing zipcode inputs as you are prompted, you can write them in a file and pass them to your program as follows:
java DriverHW04 uszipcodes.csv ziplocs.csv < in.txt

Where in.txt contains the zipcodes you will to test with one on each line. You can download in.txt with: wget https://raw.githubusercontent.com/BMC-CS-151/BMC-CS-151.github.io/main/hws/hw04/in.txt

Time your old and new implementation by running: time java DriverHW04 uszipcodes.csv ziplocs.csv < in.txt

Compare the result with your Assignment 1 implementation. Is there a speedup? Report your findings in your README.

Submitting

Submit the following files to the assignment called HW04 on Gradescope

  1. DriverHW04.java
  2. Place.java
  3. LocatedPlace.java
  4. PopulatedPlace.java
  5. LookUpZip.java
  6. ExpandableArray.java
  7. README.txt

and Lab files:

  1. ArrayList.java
  2. List.java
  3. MyIterator.java
  4. TestIterator.java
  5. TestMyListIterator.java
  6. TestRemovePositions.java

Make sure to name these files exactly what we specify here. Otherwise, our autograders might not work and we might have to take points off.
DO NOT submit a .docx or .pdf file.
DO NOT submit any .class files or any of the csv files.
DO NOT submit any of the provided interfaces. We will use the ones we provide for testing.

Copying the files

You will likely want to submit the files from your own laptop/computer. To copy the files from goldengate to your own machine, open up a terminal on your own computer. If you have a mac or linux, you can use the Terminal application, if you have a windows you can use the Powershell app.

Run the following command:

$ scp <username>@goldengate.cs.brynmawr.edu/home/<username>/cs151/homeworks/hw00/*

Make sure to replace <username> with your username. scp is a command to secure-copy files from one server to another. In this case, from goldengate to your own machine.