Resumen
Summary CPSC 110 - PSET 9 SOLUTIONS - 2022
- Grado
- Institución
Solutions to CPSC 110 Pset 9 2022
[Mostrar más]Vista previa 2 fuera de 6 páginas
Vista previa 2 fuera de 6 páginas
Añadir al carrito
Añadir al carrito
Vendedor
Seguir
travissmith1
Comentarios recibidos
Vista previa del contenido
;; The first three lines of this file were inserted by DrRacket. They recordmetadata
;; about the language level of this file in a form that our tools can easily
process.
#reader(lib "htdp-intermediate-lambda-reader.ss" "lang")((modname pset-09-solution)
(read-case-sensitive #t) (teachpacks ()) (htdp-settings #(#t constructor repeating-
decimal #f #t none #f () #t)))
;; 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 psets/pset-09);Do not edit or remove this tag
(@problem 1)
;;
;; 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.
;; 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"))))
;;!!! below here is solution
(@htdf solve)
(@signature (listof Slot) (listof TA) -> (listof (listof String)) or false)
;; produce list of lab assignments of form: (list "ta name" "lab name")
(check-expect (solve empty empty) empty)
(check-expect (solve empty (list (make-ta "Ali" (list "A"))))
empty)
(check-expect (solve (list (make-slot "A" 1)) empty) false)
(check-expect (solve (list (make-slot "A" 1)
(make-slot "A" 2))
(list (make-ta "Ali" (list "A" "B"))))
false)
Los beneficios de comprar resúmenes en Stuvia estan en línea:
Garantiza la calidad de los comentarios
Compradores de Stuvia evaluaron más de 700.000 resúmenes. Así estas seguro que compras los mejores documentos!
Compra fácil y rápido
Puedes pagar rápidamente y en una vez con iDeal, tarjeta de crédito o con tu crédito de Stuvia. Sin tener que hacerte miembro.
Enfócate en lo más importante
Tus compañeros escriben los resúmenes. Por eso tienes la seguridad que tienes un resumen actual y confiable. Así llegas a la conclusión rapidamente!
Preguntas frecuentes
What do I get when I buy this document?
You get a PDF, available immediately after your purchase. The purchased document is accessible anytime, anywhere and indefinitely through your profile.
100% de satisfacción garantizada: ¿Cómo funciona?
Nuestra garantía de satisfacción le asegura que siempre encontrará un documento de estudio a tu medida. Tu rellenas un formulario y nuestro equipo de atención al cliente se encarga del resto.
Who am I buying this summary from?
Stuvia is a marketplace, so you are not buying this document from us, but from seller travissmith1. Stuvia facilitates payment to the seller.
Will I be stuck with a subscription?
No, you only buy this summary for $18.49. You're not tied to anything after your purchase.
Can Stuvia be trusted?
4.6 stars on Google & Trustpilot (+1000 reviews)
45,681 summaries were sold in the last 30 days
Founded in 2010, the go-to place to buy summaries for 15 years now
Vistos recientemente
Resumen ·
CPSC 110 - PSET 5 SOLUTIONS - 2022
Notas de lectura ·
TEMA 2 - HISTORIA JURIDICA
Lote ·
MARK KLIMEK EXAM BUNDLE 2025
