Exam 3
This assignment is due on Monday, May 3 at 9:00pm. Submit each section using Handin as a separate assignment.
Until you finally submit all your work on this exam, you are not allowed to consult anything other than material written before the exam is posted. For example, you may consult the Beginning Student Language reference or rewatch any videos, but you may not read the newswire or talk to any person.
If you have a question, make a post on CampusWire that is "visible to instructors to TAs only". The course staff will post any announcements about the exam to CampusWire.
Unless otherwise stated, you are not required to use anything particular provided by Intermediate Student with Lambda.
If you define something, you can use it in subsequent answers in the same section.
Remember to follow the design recipe whenever you design or write a function. In particular, every type mentioned in a signature must be introduced by a data definition, except for these well-known types: Number, Image, String, Boolean, Number, String, KeyEvent, MouseEvent, Anything, Posn, NaturalNumber, [ListOf X], [Maybe X]. It may also be helpful to design helper functions.
If they are given to you, you do not need to write the signature and purpose statements again. Likewise, you do not need to repeat any test cases given to you, but you should add tests wherever appropriate.
You do not need to write separate templates unless the problem explicitly asks for them. We expect that the functions you write follow the appropriate template, however.
Some basic test taking advice: Before you start answering any problems, first read every problem, so your brain can think about the harder problems in background while you knock off the easy ones.
The Challenge is bonus. Solve it to complement any possible lost points The maximum score for the exam is 16 + 10 + 25 = 51 points. Any points you get from the challenge section (total 10) is gonna be added to your score, maxing out at 51.
1 Do the Splits (16 points)
A QuadTree is a common data structure for representing collections of points, in applications like graphics or astronomy. Here, we’ll work with a simplified version, describing points on a line.
; A SplitTree is one of: ; - Number ; - (make-no-points) ; - (make-split Number SplitTree SplitTree) (define-struct no-points ()) (define-struct split (middle left right))
We represent a collection of points in a range with a Split. If there are no points in the range, we use (make-no-points). If there’s just one point, we use just a Number. Otherwise, we divide the range in two pieces, marking the middle with a make-split. All the points in the left will be smaller than the middle, and the points in the right will be larger.
For example, to represent the numbers 1 2 3 10 we could use the SplitTree
(define st1 (make-split 5 (make-split 1.5 1 (make-split 2.5 2 3)) 10))
(define st2 (make-split 2.5 (make-split 0 (make-no-points) (make-split 1.5 1 2)) (make-split 5 3 10)))
(2 points) Write two ways of writing down the collection of points -1 5 10 100 as a SplitTree.
(4 points) Design the function count-points, which takes a SplitTree and counts the total number of points. It should produce 4 for both of your examples.
(4 points) Consider the following function.
; closest: SplitTree Number -> Maybe[Number] ; find the closest number in the tree to the given number, or false if ; the tree is empty (define (closest st n) (cond [(no-points? st) false] [(number? st) st] [else (cond [(<= n (split-middle st)) (closest (split-left st) n)] [else (closest (split-right st) n)])])) Write two examples where closest gives the correct answer. Both examples must include a make-split.
Write one example where closest gives the wrong answer.
(6 points) Design a fixed version of closest. This function should follow the template for SplitTree closely.
2 Indiana Jones and the Missing Specification (10 points)
(5 points) The following function was found without a signature, purpose statement, termination statement, or examples and tests. Recreate them based on the function definition.
(define (selection-sort l) (cond [(empty? l) empty] [else (cons (minimum l) (selection-sort (remove-minimum l)))])) Here is the signature and purpose for the helper functions:; minimum : [NEListof Number] -> Number ; find the smallest element of a list (check-expect (minimum (list 1 2 3)) 1) ; remove-minimum : [NEListof Number] -> [ListOf Number] ; remove the smallest element from a list, producing the remaining list (check-expect (remove-minimum (list 1 2 3)) (list 2 3)) You do not need to implement these functions.
(5 points) The following function was found without a signature, purpose statement, accumulator statement, or examples and tests. Recreate them based on the function definition.
(define (average/a l sum count) (cond [(empty? l) (/ sum count)] [else (average/a (rest l) (+ sum (first l)) (+ count 1))])) This function was used as a helper for the following function:; average : [NEListof Number] -> Number ; find the average of a list (define (average l) (average/a (rest l) (first l) 1)) (check-expect (average (list 1 2 3)) 2)
3 To the Max (25 points)
(6 points) Design the function largest-square, which takes a [NEListOf Number] and produces the element of the list that has the largest square. The function sqr will be useful.
(6 points) Design the function furthest-from-point, which takes a Posn and a [NEListOf Posn] and produces the posn in the list that is the furthest from the given Posn.
The function dist will be helpful:(6 points) Abstract largest-square and furthest-from-point into a new function maximize, which should take two inputs. One input will be a list, and one input will be a function.
You do not need to write any new examples or tests, but you do need to write a signature and purpose statement.
(4 points) Define largest-square2 and furthest-from-point2 using maximize. Copy the signatures, purpose statements, and examples from earlier.
(3 points) Your definition of maximize likely makes the same recursive call twice. This can make it a lot slower. Try it out on a big list (length at least 40, use build-list) and see. Then use local to make the recursive call only once. Your example should get faster. Include your example as a check-expect test.
If your function already makes only one recursive call, include a large example as a test, but you do not need to change your function.
4 Bonus Challenge: End of Class Evaluation (10 points)
Here is the data definition for a simple programming language.
; A Expression is one of ; - (make-add Expression Expression) ; - (make-multiply Expression Expression) ; - Number (define-struct add (left right)) (define-struct multiply (left right))
An add Expression produces the results of evaluation the two contained Expressions. A multiply Expression produces the results of evaluation the two contained Expressions. A Number produces itself.
(4 points) Design the function evaluate, which takes an Expression and produces the number that is the result.
- (6 points) Extend the definition of Expression with one additional possibility:
; - (make-read-write Expression) (define-struct read-write (expr)) This expression saves the result of evaluating the expression, and produces the previous saved result. If there is no previous saved result, it produces 0.Extend your definition of evaluate to handle this new case. Be sure to write relevant examples.
Hint: you will need an accumulator. You will also need another trick.
Note: this problem is hard. Don’t feel bad if you don’t get it.
Aaand you’re done! Good job! Now celebrate!
Before that, though, make sure you submitted everything in the appropriate assignment on the handin server, so we can find your answers. Recall that you can check it by "retrieve"ing your submission and see if you’re able to get it back from the server. If you can, then you’re good!
Excellent job! Well done! Cheers you all!