Homework 12

Due Date Monday 11/29 at 7:00pm (Week 12)

Note: Late submissions will get zero credit.

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

NOTE: This assignment is to be completed and submitted individually. For full credit on this homework, please complete ANY FIVE of the six exercises below. If you complete all six exercises, the best five will be used to compute your homework grade and the worst one will go towards extra credit.

For all problems, if you use an accumulator helper function, make sure you explain what the accumulators mean and how you use them. If you use a generative recursive function, make sure you explain why your function is guaranteed to terminate.

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 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

Note that if n is 0, we want to return the smallest element in the list.

Exercise 3 Consider a typical binary tree of numbers:

; A NumBinTree is one of

; 'leaf

; (make-node Num NumBinTree NumBinTree)

(define-struct node [val left right])

When we draw a binary tree in a diagram, all the values in the left subtree of the root appear to the left of the root, and all the values in the right subtree of the root appear to the right of the root, and the root’s value itself appears in the middle. Design a function flatten-tree that produces a list of all the numbers in the binary tree in that left-to-right order. (I.e., if the binary tree happens to also be a binary search tree, then the result of flattening the tree should be a sorted list of numbers.) Note: This function is pretty easy to design using append or foldr, but those aren’t the interesting solutions we are looking for on this assignment. Do not use any list functions except for cons in your solution.

Exercise 4 Consider a binary tree again. Design a function nth-value that takes a binary tree and a non-negative natural number n, and produces the n’th number counting from the left of the tree (where 0 indicates the leftmost element of the tree). I.e. (nth-value a-tree index) should produce the same answer as (list-ref (flatten-tree a-tree) index)...but without actually using flatten-tree to do it! (You can use flatten-tree in your tests, if you like.)

Exercise 5 Consider a list of numbers: we can break it up into “run”s of repeated numbers. (If every number in the list is different, then each run is only one number long; if some number is repeated several times, then its run is longer.) Define “cutting the list” to mean removing one number from each run. Define the “cut resistance” of the list to mean how many times we can cut the list (and then cut the result, and then cut that...) until the list is empty.

Design a function to compute the cut-resistance of a list. Here are a few (but not sufficient) test cases to get you started:

(check-expect (cut-resistance (list 0 0 0 1 1 0 3 3 3 2 2))

(add1 (cut-resistance (list   0 0   1     3 3   2))))

(check-expect (cut-resistance (list 0 0 1 3 3 2))

(add1 (cut-resistance (list   0     3))))

(check-expect (cut-resistance (list 1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 1 0))

(add1 (cut-resistance (list     0   1   0     0     0))))

If you use accumulators, explain what they mean; if you use generative recursion, explain why your function terminates.

Exercise 6 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)