Assignment 11

Due Date Thursday 6/20 at 10:00pm

Purpose To practice designing accumulator-based functions.

Remember to explicitly write down your accumulator statements as appropriate.

Finger Exercises

Exercise 1 Consider the following definition:

(define-struct node [left val right])

; A NumTree is one of

; - Number

; - (make-node NumTree Number NumTree)

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

Graded Exercises

Remember to use accumulators in the following exercises.

Consider the following definition for trees with data at the leaves and nodes:

; A [BT X] is one of:

; - (make-node X [BT X] [BT X])

; - X

(define-struct node (data left right))

Exercise 3

• Design a function to find the largest number in a [BT Number]

• Design a function to find the string that comes first lexicographically in a [BT String]

• Abstract the previous two functions to design a function to find the winning X in a [BT X]. The winning X could mean the largest number in a [BT Number] or the first string lexicographically in a [BT String] or the winner according to some other way to compare the data in a tree.

Exercise 4 Design the function palindrome, which accepts a [NEList-of 1String] and constructs a palindrome by mirroring the list around the last item. For example, when given (explode "abc"), it yields (explode "abcba").

Exercise 5 Design a function only-leaves, that takes a [BT X] 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 6 The Fibonacci numbers, which are the numbers in the following sequence: 0 ,1 ,1 ,2 ,3 ,5 ,8 ,13 ,21 ,34 ,55 ,89 ,144 ,... are defined by the recurrence relation: Fn = Fn-1 + Fn-2, with seed values F0 = 0 and F1 = 1.

• Design the function fibonacci, (without accumulators) which consumes a Natural Number and produces its Fibonacci number. For example, (fibonacci 11) should produce 89.

• Use accumulators to design a more efficient version of fibonacci.