Week 13 Set a

Due Date Monday 11/26 at 5:00pm (Week 13)

Purpose To practice using accumulators, generative recursion, and higher-order functions.

NOTE: This assignment is to be completed and submitted individually. It is due at 5:00pm on the due date. Late policy for this assignment only: 25% off for every 15 minutes late, which means that after 6:00pm, you get zero credit.

Graded Exercises

Exercise 1 You are a cashier at a movie theater where all of the tickets cost 5 dollars (if only). All customers approach the ticket window with either a credit card, a 5 dollar bill, a 10 dollar bill, or a 20 dollar bill. Today, your manager left n 5 dollar bills in the cash register to start the day. Design a function, as well as any data definitions you may need, that takes in n as well as a list of payments, where the first customer is at the head of the list, and returns how many tickets you will be able to sell. Tickets can only be sold so long as change, if needed, can be made. Customers you cannot sell to will go to a different movie theater in protest.

Exercise 2 Very often we are interested in knowing the nth biggest smallest element in a list of numbers (such as quartiles or medians). A naive approach to this problem would sort the entire list in ascending order and get the nth element. However, this does much more work than necessary.

Design the function nth-smallest, which takes in n and a non-empty list of real numbers, where n is assumed to be less than the length of the given list. It works as follows:

1. If there is only one element in the list, return it

2. Partition the list into sublists of size 5 (with one possibly smaller list at the end)

3. Get the exact median of each of these sublists by individually sorting them and then selecting the middle element (as these sublists are all very small, this won’t be a large computational cost)

4. Get the median of these medians using nth-smallest; this is now the pivot element

5. Partition the initial list into everything less than or equal to the pivot (besides the pivot itself), the pivot, and everything bigger than the pivot

6. Based on the number of elements that are less than or equal to the pivot and n, either return the pivot element or make the appropriate recursive call to nth-smallest

Edit: the problem used to state nth biggest. This mistake was pointed out on Piazza (thank you, Anonymous) and has since been fixed. In other words, if n is 0, we want to return the smallest element in the list. We apologize for the confusion.

Exercise 3 Some of you come from an object-oriented background and have seemed to miss objects. Well, it turns out objects were with you the whole time!

From a functional perspective, an object is a function which takes a message (a symbol) and then outputs some value based on the message; this value could be some property about the object, often called a "field", or a function that will carry out some task, often called a "method". If this terminology is unfamiliar to you, do not worry, you do not need any experience with objects to complete the exercise.

For this homework, we will design a Circle object:

; A Circle is a [CircleMessage -> Any]

; A CircleMessage is one of:

; - 'center

; - 'radius

; - 'resize

; - 'equal

; and represents a message to circle, requesting either:

; its center (a Posn)

; its radius (a Number)

; how much to addtively change its radius by (a [Number -> Circle])

; whether or not it has the same size and position as another circle (a [Circle -> Boolean])

Your task is to design new-circle, which consumes a posn and a number for the circle’s center and radius, respectively, and produces a Circle. The following tests should pass on the following examples:

(define c0 (new-circle (make-posn 10 20) 4))

(define c1 (new-circle (make-posn 10 20) 9))

(check-expect (c0 'radius) 4)

(check-expect (c0 'center) (make-posn 10 20))

(check-expect (((c0 'resize) 10) 'radius) 14)

(check-expect ((c1 'equal) c0) #f)

(check-expect ((((c1 'resize) -5) 'equal) c0) #t)