Assignment 11
Due Date: Wednesday at 9:00pm (Week 13)
Purpose To practice designing accumulator-based functions.
Remember to explicitly write down your accumulator statements as appropriate.
Exercise 1 Exercise 502 in HtDP.
Exercise 2 Consider the following definition:
(define-struct node [left val right]) ; A NumTree is one of ; - Number ; - (make-node NumTree Number NumTree) ; INTERPRETATION: irrelevant Design the function sum-of-products, that produces the sum of the product of each path of numbers from root to each leaf. For example,
(sum-of-products (make-node 1 2 3)) ===> (+ (* 2 1) (* 2 3))
You can design this function either structurally or with accumulators.
Exercise 3 Design a function only-leaves, that takes a NumTree and produces a list containing only the leaves of the tree. Do not use any list abstractions to solve this problem, especially append. Use an accumulator instead.
Exercise 4 Design the function product-of-sums, that is much like the finger exercise above, but produces the product of the sums of each path. For example,
(product-of-sums (make-node 1 2 3)) ===> (* (+ 2 1) (+ 2 3))
This function must be done with an accumulator. (Technically, you could solve this problem using only structural recursion and several helper functions, but it would be much less efficient, and would have to traverse the tree several times.)
Hint: What changed about the arithmetic in this problem, compared to the finger exercise, that makes the structural solution of the finger exercise incorrect here?
Exercise 5 Exercise 504 in HtDP.