CS 5010: Problem Set 08
Out: Monday, 13 March 2017
Due: Monday, 20 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 is designed to give you a chance to make your scheduling program run faster.
You must use the HtDP Intermediate Student Language + Lambda for this problem set.
As in previous problem sets, you must download a copy of
and push it to the
set08 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.
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 07 to a file named
flight.rktas necessary to make your program run in polynomial time.
As in Problem Set 07, your program must respect the abstraction barrier associated with the
Flightabstract data types. As in Problem Set 06, you are allowed to implement those ADTs as you see fit.
After you have finished your
set07/q1.rktprogram, analyze its asymptotic running time. In a plain text file named
set08/q2.txt, write a one-sentence summary of its asymptotic running time.
Following that sentence, display a table showing how the running time of your optimized program varies with the parameter
nfor the simple benchmark shown below, using a range of values for
nthat is adequate to illustrate the asymptotic running time you are claiming for your program.
;;; all-airports : ListOfFlight -> ListOfString ;;; RETURNS: A list of all airports served by some flight ;;; in the given list. (define (all-airports flights) (all-airports-loop (append (map departs flights) (map arrives flights)) empty)) ;;; all-airports-loop : ListOfString ListOfString -> ListOfString ;;; GIVEN: two lists of strings ;;; WHERE: the second list is a set (no element occurs twice) ;;; RETURNS: the set union of the given lists (define (all-airports-loop names airports) (if (empty? names) airports (all-airports-loop (rest names) (if (member (first names) airports) airports (cons (first names) airports))))) ;;; visit-all-pairs-of-airports : ;;; (String String ListOfFlight -> X) ListOfFlight -> ListOfX ;;; GIVEN: a function whose arguments are suitable for can-get-there? ;;; RETURNS: a list of the results obtained by calling that function ;;; on all pairs of airports served by the given flights, ;;; passing the given list of flights as a third argument. (define (visit-all-pairs-of-airports visitor flights) (let ((airports (all-airports flights))) (apply append (map (lambda (ap1) (map (lambda (ap2) (visitor ap1 ap2 flights)) airports)) airports)))) ;;; make-stress-test0 : NonNegInt -> ListOfFlight ;;; GIVEN: a non-negative integer n ;;; RETURNS: a list of 2n flights connecting n+1 airports (define (make-stress-test0 n) (if (= n 0) empty (let* ((name1 (string-append "NoWays " (number->string (+ n n)))) (name2 (string-append "NoWays " (number->string (+ n n 1)))) (ap1 (string-append "AP" (number->string n))) (ap2 (string-append "AP" (number->string (+ n 1)))) (t1 (make-UTC (remainder (* 107 n) 24) (remainder (* 223 n) 60))) (t2 (make-UTC (remainder (* 151 n) 24) (remainder (* 197 n) 60))) (t3 (make-UTC (remainder (* 163 n) 24) (remainder (* 201 n) 60))) (t4 (make-UTC (remainder (* 295 n) 24) (remainder (* 183 n) 60))) (f1 (make-flight name1 ap1 ap2 t1 t2)) (f2 (make-flight name2 ap1 ap2 t3 t4))) (cons f1 (cons f2 (make-stress-test0 (- n 1))))))) ;;; benchmark0 : NonNegInt -> List ;;; GIVEN: a non-negative integer parameter n ;;; RETURNS: a list of length n^2 showing the travel time for ;;; every pair of airports in a stress test of size Theta(n) ;;; EFFECT: prints the total running time (define (benchmark0 n) (let ((flights (make-stress-test0 n))) (time (visit-all-pairs-of-airports (lambda (ap1 ap2 flights) (if (can-get-there? ap1 ap2 flights) (list ap1 ap2 (travel-time ap1 ap2 flights)) (list ap1 ap2 -1))) flights))))