;; DO NOT PUT ANYTHING PERSONALLY IDENTIFYING BEYOND YOUR CWL IN THIS FILE.;; YOUR CWLs WILL BE SUFFICIENT TO IDENTIFY YOU AND, IF YOU HAVE ONE, YOUR;; PARTNER;;
(require spd/tags)
(@assignment pset-09);Do not edit or remove this tag(@cwl qianyunl ???) ;Replace ??? with your cwl,;; ;second ??? is replaced with partner cwl if you have one
;;;; THIS IS THE MOST CHALLENGING PROBLEM SET SO FAR THIS TERM. PLEASE BE;; SURE YOU WORK THROUGH IT CAREFULLY THOUGH. 110 FINAL EXAMS OFTEN INCLUDE;; PROBLEMS BASED ON PROBLEM SETS 9, 10, OR 11.;;;; ALSO NOTE THAT THE AUTOGRADER WILL ONLY GRADE ONE SUBMISSION PER HOUR FOR;; THIS PROBLEM SET. SO START EARLY AND CAREFULLY TEST YOUR WORK ON YOUR OWN;; EACH TIME BEFORE SUBMITTING TO THE AUTOGRADER.;;;; THERE WILL BE A SPECIAL PINNED THREAD ON PIAZZA IN WHICH WE WILL ANSWER;; QUESTIONS ABOUT THIS PROBLEM SET.;;;; In this problem set you are going to work on one of the toughest problems;; we face running 110 - scheduling of TAs. As you may know, we have about;; 45 TAs, and we have to schedule them for many labs, 3 lectures, and office;; hours. We solved this by writing a schedule solver, and that's what you;; are going to do for this problem set.;;;; We are making it a little easier for you, in that all you will be having;; to deal with is labs.;;;; We are giving you two key data definitions, as well as some examples of;; that data. We are also giving you a wish list entry for the main solve;; function you have to design. The function consumes a list of TAs and a;; list of lab slots to fill. It produces a list of assignments. So, for;; example, in the following very simple case, where there are two slots,;; and two TAs, you get an assignment of the TAs to those slots.;;;; (solve (list (make-slot "A" 1) (make-slot "B" 1));; (list (make-ta "Ali" (list "B"));; (make-ta "Azi" (list "A")))) ==>;;;; (list (list "Ali" "B") (list "Azi" "A"));;;; In this simple example there was only one possible assignment. But in;; general there might be more than one assignment, or it might be impossible;; to generate an assignment.
;; By now you know enough about search to know that the first thing you need;; to do is figure out the search space. What does the tree look like? What;; information do you have to represent at each node in the tree? Even though;; The function ends up producing just a list of assignments, it need more than;; just the assignments so far at each node in the tree? What other information;; do you need to represent at each node?;;;; As you consider the search tree, note that a TA can work more than one slot,;; but a slot is filled by one TA. So once you assign a TA to a slot that slot;; is done.;;;; As usual, anything we give you you must use without changing. The autograder;; will want to call solve with arguments as described below.
(@problem 1)
;; Constants:
(define MAX-SLOTS-PER-TA 3) ;this is the max number of labs a TA can work
;; Data definitions:
(@htdd Slot)(define-struct slot (lab n));; Slot is (make-slot String Natural);; interp. the name of a lab - "A", "B", etc.;; the lab's slot number - 1, 2, 3 etc.;; CONSTRAINT:;; a list of slots representing positions that need to be filled;; should not contain duplicate slots (slots with same lab and n);;(define SLOTS1 (list (make-slot "A" 1) (make-slot "A" 2) ;A needs 2 TAs (make-slot "B" 1) ;B needs 1 (make-slot "C" 1) (make-slot "C" 2))) ;C needs 2
(@htdd TA)(define-struct ta (name avail));; TA is (make-ta String (listof String));; interp. A TA with their name and the labs times they are free to work.;; CONSTRAINT:;; a list of TAs should not contain TAs with duplicate names
(define TAS1 (list (make-ta "Ali" (list "A" "B")) (make-ta "Ari" (list "B" "C")) (make-ta "Azi" (list "A" "C"))))
(@htdf solve)(@signature (listof Slot) (listof TA) -> (listof (listof String)) or false);; produce assignments(list (list "ta name" "lab name")...)(define (solve slots tas) empty) ;stub