CS 5010: Problem Set 09

Out: Monday, 20 March 2017
Due: Monday, 27 March 2017 at 6pm

This is a pair programming assignment. You are required to complete this problem set in collaboration with your assigned partner, but neither of you are allowed to discuss this problem set with any other person. You are also not allowed to search for or to view any solutions to similar problems that may be available on the World-Wide Web or in other resources that might otherwise have been available to you.

We have created a repository for you and your partner to use in this problem set and for the next two problem sets as well. The name of that repository is of the form pdp-ID1-ID2, where ID1 is either your CCIS ID or your partner's CCIS ID, and ID2 is the other CCIS ID for your team.

In those repositories, we have created files named ID1-log.txt and ID2-log.txt for you to use when filing work session reports, as in previous problem sets. You and your partner are required to push your files at the end of every work session. (You may push your files several times during a work session, but we do not require you to do so.)

At the end of every work session, you are required to update your log file to record the time you spent in that work session. (Please do not include the time you spent in any previous work sessions, as those times will already have been recorded in previous versions of your log file.) If both of you work together during a work session, both of you must update your log files, recording only the time you spent working. Do not include your partner's time in your log file, but be sure to push the updated versions of both log files.


The main purpose of this problem set is to give you practice applying what you have learned in previous assignments to object-oriented programming in Java.

You must use Java 8 for this assignment. All of your code must reside within the default package. You may use/import anything in the java.lang and java.util packages, but you are not allowed to use any other packages.


Problem Specification

You will translate your polynomial-time solution to the flight scheduling problem from Racket to Java. Your translation will use the data types specified in this problem set, which will allow us to write black-box tests we can use to test all of the solutions submitted by students taking the course.

We have divided that problem into two parts. In the first part, you will implement three abstract data types. In the second part, you will use those ADTs in your solution to the scheduling problem.

  1. We are giving you three Java files, which define three abstract data types: UTC, Flight, and RacketList<E>. You must copy those three files into your team's set09 directory without changing them in any way.

    In a file named UTCs.java, define a public class named UTCs that defines the following public static factory method:

            // GIVEN: the hour in [0,23] and the minute in [0,59]
            // RETURNS: a UTC with that hour and minute
            
            public static UTC make (int h, int m) {
                ...
            }
          

    In a file named Flights.java, define a public class named Flights that defines the following public static factory method:

            // GIVEN: the name of a flight, the name of the airport from
            //     which the flight departs, the name of the airport at
            //     which the flight arrives, the time of departure in UTC,
            //     and the time of arrival in UTC
            // RETURNS: a flight value that encapsulates the given information
            
            public static Flight make (String s, String ap1, String ap2,
                                       UTC t1, UTC t2) {
                ...
            }
          

    In a file named RacketLists.java, define a public class named RacketLists that defines the following public static factory method:

            // GIVEN: no arguments
            // RETURNS: an empty RacketList<E>
            
            public static <E> RacketList<E> empty () {
                ...
            }
          

    You may add more static methods to those three classes if you wish.

    Complete your implementation of the three ADTs specified above by defining more classes. You will probably want to put at least some of those classes in separate files, but all files must be added to your set09 directory and pushed to your team's repository.

  2. In the second part of this problem set, you will translate your polynomial-time solution to the scheduling problem from Racket to Java.

    We are giving you a FlightExamples.java file that defines the lists of flights used in the examples below. You will need to define more lists of flights for use in your own testing. In particular, you will need to write benchmarks that test the performance of the three methods specified below.

    In a file named Schedules.java, define a public class named Schedules that defines the following public static methods:

            // GIVEN: the names of two airports, ap1 and ap2 (respectively),
            //     and a RacketList<Flight> that describes all of the flights a
            //     traveller is willing to consider taking
            // RETURNS: true if and only if it is possible to fly from the
            //     first airport (ap1) to the second airport (ap2) using
            //     only the given flights
            // EXAMPLES:
            //     canGetThere ("06N", "JFK", FlightExamples.panAmFlights)  =>  false
            //     canGetThere ("JFK", "JFK", FlightExamples.panAmFlights)  =>  true
            //     canGetThere ("06N", "LAX", FlightExamples.deltaFlights)  =>  false
            //     canGetThere ("LAX", "06N", FlightExamples.deltaFlights)  =>  false
            //     canGetThere ("LGA", "PDX", FlightExamples.deltaFlights)  =>  true
            
            public static boolean canGetThere (String ap1,
                                               String ap2,
                                               RacketList<Flight> flights) {
                ...
            }
                    
            // GIVEN: the names of two airports, ap1 and ap2 (respectively),
            //     and a RacketList<Flight> that describes all of the flights a
            //     traveller is willing to consider taking
            // WHERE: it is possible to fly from the first airport (ap1) to
            //     the second airport (ap2) using only the given flights
            // RETURNS: a list of flights that tells how to fly from the
            //     first airport (ap1) to the second airport (ap2) in the
            //     least possible time, using only the given flights
            // NOTE: to simplify the problem, your program should incorporate
            //     the totally unrealistic simplification that no layover
            //     time is necessary, so it is possible to arrive at 1500
            //     and leave immediately on a different flight that departs
            //     at 1500
            // EXAMPLES:
            //     fastestItinerary ("JFK", "JFK", FlightExamples.panAmFlights)
            //         =>  RacketLists.empty()
            //
            //     fastestItinerary ("LGA", "PDX", FlightExamples.deltaFlights)
            // =>  RacketLists.empty().cons
            //         (Flights.make ("Delta 2163",
            //                        "MSP", "PDX",
            //                        UTCs.make (15, 0), UTCs.make (19, 2))).cons
            //             (Flights.make ("Delta 0121",
            //                            "LGA", "MSP",
            //                            UTCs.make (11, 0),
            //                            UTCs.make (14, 9)))
            //
            // (Note: The Java syntax for a method call makes those calls
            // to cons look backwards from what you're used to in Racket.)
            
            public static
                RacketList<Flight> fastestItinerary (String ap1,
                                                     String ap2,
                                                     RacketList<Flight> flights) {
                ...
            }
            
            // GIVEN: the names of two airports, ap1 and ap2 (respectively),
            //     and a RacketList<Flight> that describes all of the flights a
            //     traveller is willing to consider taking
            // WHERE: it is possible to fly from the first airport (ap1) to
            //     the second airport (ap2) using only the given flights
            // RETURNS: the number of minutes it takes to fly from the first
            //     airport (ap1) to the second airport (ap2), including any
            //     layovers, by the fastest possible route that uses only
            //     the given flights
            // EXAMPLES:
            //     travelTime ("JFK", "JFK", FlightExamples.panAmFlights)  =>  0
            //     travelTime ("LGA", "PDX", FlightExamples.deltaFlights)  =>  482
            
            public static int travelTime (String ap1,
                                          String ap2,
                                          RacketList<Flight> flights) {
                ...
            }
          

For debugging: Click here to validate.