Homework 9

Due: Dec 11 (109, Dec 11), prior to 11:59:59 PM

In this assignment you will work again with the Philadelphia Airport data. A smaller file, only 5001 lines, but exactly the same data. Thus, you can reuse the class definitions and methods you wrote last week for Flight and file reading.

This assignment is broken up into 4 parts;

A library class that reads flight information from a data file. You have already done this one!
A program to sort the array of flights. You will adapt one of the sort functions discussed in class to work on the flight data.
A program to filter for uniqueness.
A program to partition the data (without sorting) into two groups based on a given value. For instance, partition the flight data into those flights that have a departure delay less than 5 minutes and those that have a departure delay of 5 minutes or more.

In completing this assignment, you will learn to:

Define a custom class in Java
Read data from an input file using a Java library
Work with arrays of objects
Sort arrays of objects

Code Understandability and Readability

This statement is repeated for the previous homeworks. It still applies

In addition to writing code that correctly implements the specification, you are also asked to write code that is easy to read and understand. In particular, part of your score on this assignment will be determined by: Variable naming: Variables should have meaningful names that indicate what they represent, using full English words or common abbreviations, e.g. "wins" or "votes" instead of "w" or "vot".

Appearance: The code should be formatted so that indentation and spacing make it easy to understand which parts of the code are within the bodies of if-statements and loops. Additionally, there should be spacing between variables and operators to make it easy to read each individual line of code.

Part 1: Reading flights from file

The data file for this assignment is available at

    /home/gtowell/Public/CS113/HW9/phl5001.txt

Use exactly the same code as in HW8 for reading this data. (This is actually just the first 5001 items from HW8.)

Part 2: Sorting

The BubbleSort code discussed in class on Monday (Dec 4) and which is in the lecture notes from Wednesday Nov 29) works only on an array of integers. In this part you will change that code so that it can be used to sort the flight data (the 5000 items flight data from part 1). Sort this data (for this part) so that is ordered by origin airport; in descending order. After sorting, print only the first 50 rows of the sorted array. (The first item printed should be for "PDX".)

You should do something like the following:

Copy code as needed from HW8
Create a new class
Copy the bubble sorting method from the lecture notes into this class
Adapt the bubble sort method so it sorts Flight objects on the basis of origin airport
Write a main method that reads the data file, then sorts it using your adapted bubble sort, and finally prints the first 50 items

Part 3: Filtering for Uniqueness

The goal in this part is to print exactly one flight object for each origin city in the 5001 file. It does not matter which flight object you print for an origin city, but there should be only one for each origin. There are many ways you can accomplish this task; for this assignment start by sorting the data; exactly as in Part 2. Next, print the item in position 0. All that is left is to find and print exactly one item for each origin city. (Hint, use a single for loop; looking at each object in the array at most twice.)

Also keep a count of the number of unique origin cities. Print that count on completing your filtering. (My count was 36.)

Part 4: Partitioning

In this part, you will write a program to partition the data by departure delay. Importantly, this partitioning should be done in place; that is, on the array you are given rather than on a copy of the array. The idea here is that you will get one integer from the command line; I call this number the "target". Then move the 5001 items around so that all of the flights whose departure delay is less than the target are in the array in positions lower than all of the items whose value is greater than the target. When all of the moves are done, print the smallest index in the array of a flight whose departure delay is greater than the target.

You could accomplish this task by sorting on departure delay. Do not. Instead, adapt the following pseudocode to work with your array of flight objects.

    let arr = array of integers 
    let target = the target value to partition the items in arr
    let lw = 0
    let hi = arr.length - 1
    while lw < hi {
        if arr[lw] < target {
            lw = lw +1
        } else {
            swap array items in positions lw and hi
            h1 = hi - 1
        }
    }

For example, given a target of 0, the index that would be printed is 2721.

In your readme include a paragraph discussing:

how this algorithm works. Use english sentences; not pseudocode or actual code.
why this algorithm for partitioning the data is superior to sorting given that you simply want to partition the data into two groups. (Hint, it is faster; your discussion should focus on why it is faster)

Commenting your code

Your code for this assignment should be "commented" as discussed in class on Dec 6. That is, there should be a javadoc style comment describing what the class does, who wrote it, etc. In addition, there should be javadoc style comments about each method that is more than one line of code. Most of the code on the class website includes such comments. Also, see this style guide for suggestions about comments.

Submitting

Create a readme

Use VSC to create another file in your HW9 directory. This file should be named "Readme". The contents of this file should follow this sample Be sure that the Readme has, in addition to the usual stuff, clear instructions on how to do each part of the assignment. Also, be sure your readme has the discussion requested in part 4.

You should have several java files and the readme in the HW9 directory. Exactly how many java files depends on how you have chosen to arrange your code.

Submit

If you did this work on your own computer

You will first need to copy the files from you own computer to a lab computer. To do so, you can go into the lab as with HW2 or use ssh. Either way, you will need to create HW6 directory within you CS113 directory on the Unix machines. Recall, the can be done with the following commands:

    cd
    cd CS113 
    mkdir HW9

Once you have made the HW9 directory in Unix, open a terminal on you own computer and in that terminal use "cd" to navigate to the directory containing your work for this assignment. Assuming you use the same directory structure on your own computer and in the lab, this process can be accomplished with the following commands

    cd
    cd CS113
    cd HW9

Then use the scp command to copy each of the files you want to submit from your computer to the lab. For example:

    scp Readme UNIX_NAME@goldengate.cs.brynmawr.edu:CS113/HW9/Readme

As always, when you read "UNIX_NAME" put in your UNIX user name. Also, with each scp command you will need to enter your UNIX password.

Actually submit

Open a terminal in UNIX (again, you can use SSH to do so from your laptop) and execute the following Unix commands (assuming you put HW8 directory into a CS113 directory in your home directory).

    cd
    cd CS113
    /home/gtowell/bin/submit -c 113 -d HW9 -p 9

In response to the submit command you should see a series of messages ending with:

    
    Submitting archive...
    Submission complete! Submission timestamp is 2023-08-08-15-30-28-EDT.