CS 5010: Problem Set 07
Out: Monday, 27 February 2017
Due: Monday, 13 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.
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.
This problem set has two purposes. One is to give you some appreciation for abstract data types. Another is to give you some practice with invariants and contexts.
You must use the HtDP Intermediate Student Language + Lambda for this problem set. You should use HOFs wherever appropriate.
As in previous problem sets, you must download a copy of
and push it to the
set07 directory with your solutions.
Then import that library by including the line
at the top of your files with your other
declarations. Following those
provide declarations that provide all of
the functions you are required to provide, without providing any
functions you are not required to provide.
That will allow our testing framework to import your files
and do automated testing on them.
You can use
check-location to double-check that your
files are in the right place.
For the first question in this problem set,
you must also download a copy of
and use that implementation of
instead of the
flight.rkt file you wrote
for Problem Set 06.
Remember that you must follow the design recipe, which is a process, not a list of deliverables. Your deliverables include the artifacts produced by the various steps of the design recipe: data definitions (including interpretation and templates, contracts, purpose statements, definitions, and tests). Be sure to follow our coding conventions. Doing so will make codewalks easier for everyone.
q2.rktprogram of Problem Set 06 to a file named
set07/q1.rkt. Create a plain text file named
set07/q1.txtas well. Modify your
q1.rktprogram as necessary to respect the abstraction barrier associated with the
Flightabstract data types, without changing any of the
providedeclarations, contracts, or purpose statements from Problem Set 06.
Record all of the changes that were necessary in your
q1.txtfile; when you're done, that file will tell you some of the things you did wrong on Problem Set 06. Test your program using the
flight.rktfile given to you for this assignment. When your
q1.rktprogram respects the abstraction barrier of the
FlightADTs, that program should run with either one of the two
flight.rktfiles: the one you wrote for Problem Set 06 and the one given to you by the course staff for this assignment.
After you have modified your
set07/q1.rktprogram as necessary to respect abstraction barriers, make a copy of it in
set07/q2.rkt. Modify that program as necessary to work without the preconditions that say there are no non-trivial round trips.
In other words: Define and
providethe three functions specified below.
;;; can-get-there? : String String ListOfFlight -> Boolean ;;; GIVEN: the names of two airports, ap1 and ap2 (respectively), ;;; and a ListOfFlight 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 ;;; fastest-itinerary : String String ListOfFlight -> ListOfFlight ;;; GIVEN: the names of two airports, ap1 and ap2 (respectively), ;;; and a ListOfFlight 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 ;;; travel-time : String String ListOfFlight -> NonNegInt ;;; GIVEN: the names of two airports, ap1 and ap2 (respectively), ;;; and a ListOfFlight 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