Instructions

1. This is a closed-notes, closed-book exam.

2. You will not be penalized on trivial syntax errors, such as a missing parenthesis. Multiple errors or errors that lead to ambiguous code will have points deducted, however.

3. In all of the questions, feel free to write additional helper methods to get the job done.

4. The emphasis is on correctness of the code, not efficiency or on simply generating the right result.

5. Use the back of the sheet the question is on if you need additional space.

6. You may write your functions using either forward or reverse accumulation unless otherwise directed.

7. Unless given, the contract, purpose, and headers are all required.

Please write and sign the Rice Honor Pledge here:

1. (15 pts) Natural Numbers: Write the following function. The contract, purpose, header and test cases are given below.

;; pow: num natnum à num

;; (pow x n) returns x raised to the power of n where n is a

;; non-negative integer

(define (pow x n) ;; fill in the rest.

(define (pow x n)

(cond

[(zero? n) 1]

[(positive? n) (* x (power x (sub1 n)))]))

Scores:

Prob. 1: /15

Prob 2a: /10

Prob 2b: /15

Prob 2c: /20

Prob 2d: /25

Prob 2e: /15

Total: /100

"pow test cases"

(= 1 (pow 0 0))

(= 1 (pow 5 0))

(= 5 (pow 5 1))

(= 25 (pow 5 2))

(= 1 (pow -3 0))

(= -3 (pow -3 1))

(= 9 (pow -3 2))

(= 1 (pow 1.5 0))

(= 1.5 (pow 1.5 1))

(= 2.25 (pow 1.5 2))

2. (85 pts total) Polynomials: Consider the following model of a polynomial.

A polynomial of one variable, p(x),is an expression of the form

a_nxⁿ + a_n-1x^n-1+ ... + a₁x + a₀,

where n is a non-negative integer, a_k (k = 0.. n) are numbers, and a_n is a number not equal to 0. n is called the order (or degree) of p(x), a_k(k = 0.. n) are called the coefficients of p(x), and a_n is called the leading coefficient of p(x).

For example:

· p(x) = 12x⁵ - 3x² + 7 is a polynomial of degree (order) 5 with leading coefficient 12. -3x² + 7 is called the lower order polynomial for p(x).

· p(x) = 7 is a polynomial of degree 0 with leading coefficient 7. This is an example of a constant polynomial. It has no lower order polynomial.

We can describe polynomials in the following manner. There is an abstraction called polynomial. A constant polynomial is a polynomial with a leading coefficient and order (degree) 0. A non-constant polynomial is a polynomial with a leading coefficient, a positive order, and a lower order polynomial. Constant polynomials do not contain lower order polynomials.

In Scheme, we could make the following data definition

; a Polynomial is an abstract structure representing a polynomial

; which is either

; - ConstPoly which is a number representing the constant polynomial, or

; - NonConstPoly which is a structure representing the

; non-constant polynomial

; ConstPoly is a number representing a polynomial of order 0.

; Since this is a number we don’t need a structure definition.

; For convenience, we define

(define ConstPoly? number?)

; - NonConstPoly is a structure representing the non-constant polynomial

; that has

; - a field called coef that is a number

; - a field called order which is a positive integer, and

; - a field called lower which is a Polynomial whose order is less than

; this structure’s order

(define-struct NonConstPoly (coef order lower))

; Example data

(define p0 42) ; p0 = 42

(define p1 (make-NonConstPoly -5 1 p0)) ; p1 = -5x + 42

(define p2 (make-NonConstPoly 7 2 p1)) ; p2 = 7x² -5x + 42

(define p3 (make-NonConstPoly 1 5 p2)) ; p3 = x⁵ + 7x² -5x + 42

a. (10 pts) In a few short sentences, compare this model of a polynomial to the model of a list that we have been using by describing their structural similarity and/or dissimilarity. As a result, what features particular to this kind of data structure should one expect to see in the design template for a Polynomial? Concentrate on the most major, generalizable issues, not small details.

Both the Polynomial and lists are recursive data structures because both the NonConstPoly and the cons structures contain references to their own types, namely Polynomial and list respectively. The template should have both a base case and an inductive case.

b. (15 pts) Write the template for a function that processes a Polynomial.

(define (f-Poly aPoly)

(define (f-Poly aPoly)

(cond

[(ConstPoly? aPoly) …]

[(NonConstPoly? aPoly) …(NonConstPoly-coef aPoly)

…(NonConstPoly-order aPoly)

…(f-Poly (NonConstPoly-lower aPoly)…]))

c. (20 pts) Reverse Accumulation: Write a function that evaluates a Polynomial for a given value of x. Your solution should use reverse accumulation. You may use your pow function from earlier. Follow your template!

; evalRev: Polynomial num à num

; (evalRev aPoly x) evaluates the polynomial aPoly,

; at the given value, x.

(define (evalRev aPoly x) ;; fill in the rest

(define (evalRev aPoly x)

(cond

[(ConstPoly? aPoly) aPoly] ; (number? aPoly) ok too.

[(NonConstPoly? aPoly) (+ (* (NonConstPoly-coef aPoly)

(pow x (NonConstPoly-order aPoly)))

(evalRev (NonConstPoly-lower aPoly) x))]))

;; Tests cases for evalRev – test data defined at beginning of problem

(= 42 (evalRev p0 0))

(= 42 (evalRev p0 1))

(= 42 (evalRev p0 2))

(= 42 (evalRev p1 0))

(= 37 (evalRev p1 1))

(= 32 (evalRev p1 2))

(= 42 (evalRev p2 0))

(= 44 (evalRev p2 1))

(= 60 (evalRev p2 2))

(= 42 (evalRev p3 0))

(= 45 (evalRev p3 1))

(= 92 (evalRev p3 2))

d. (25 pts) Forward Accumulation: Write a function that evaluates a Polynomial for a given value of x. Your solution should use forward accumulation. You may use your pow function from earlier. Follow your template!

The evaluation technique you are required to use is called “Horner’s method” which utilizes the fact that a polynomial can be decomposed as follows:

a_nxⁿ + a_n-1x^n-1+ ... + a₁x + a₀

= ((..(a_nx + a_n-1) x + a_n-2)x + a_n-3)x + ... + a₁)x + a₀

Notice how the factors of x to some power are eliminated. If you look at the right hand side of the above equation as a process going from the innermost parentheses on the left towards the right, Horner’s method can be described as follows:

i) When at the first term

a) When the Polynomial is a constant, then the constant value is the result

b) When the Polynomial is not a constant, the accumulated value so far is simply the coefficient.

ii) When in the middle of an evaluation,

a) When at the constant Polynomial the final evaluation of the whole Polynomial is the previous accumulated value times x raised to the power of the previous term plus the current constant value.

b) When at a NonConstPoly, the accumulated value so far is the previous accumulated value time x raised to the power of the difference between the previous order and this order (may not be 1 if there are missing terms; for example, in the above equation, what if a_n-1 and a_n-2 are both zero?) plus the current coefficient.

Write your solution on the following page

;; Tests cases for evalRev – test data defined at beginning of problem

(= 42 (evalFwd p0 0))

(= 42 (evalFwd p0 1))

(= 42 (evalFwd p0 2))

(= 42 (evalFwd p1 0))

(= 37 (evalFwd p1 1))

(= 32 (evalFwd p1 2))

(= 42 (evalFwd p2 0))

(= 44 (evalFwd p2 1))

(= 60 (evalFwd p2 2))

(= 42 (evalFwd p3 0))

(= 45 (evalFwd p3 1))

(= 92 (evalFwd p3 2))

Write the contract, purpose and header for any additional function that you write. You may omit the test cases.

; evalFwd: Polynomial num à num

; (evalFwd aPoly x) evaluates the polynomial aPoly,

; at the given value, x.

(define (evalFwd aPoly x) ;; fill in the rest

(define (evalFwd aPoly x)

(cond

[(ConstPoly? aPoly) aPoly]

[(NonConstPoly? aPoly) (evalHelp (NonConstPoly-lower aPoly)

x

(NonConstPoly-coef aPoly)

(NonConstPoly-order aPoly))]))

; evalHelp: Polynomial num num pos_int à num

; Evaluates the given polynomial, p, at the given value, x, where

; the initial coefficient of the polynomial is incremented by

; acc times the quantity x to the power of deg – order of

; this polynomial.

(define (evalHelp p x acc deg)

(cond

[(number? p) (+ p (* acc (pow x deg)))]

[(NonConstPoly? p) (evalHelp (NonConstPoly-lower p)

x

(+ (NonConstPoly-coef p)

(* acc

(pow x (- deg

(NonConstPoly-order p)))))

(NonConstPoly-order p))]))

e. (15 pts total) Critiquing existing code: Consider the following forward accumulation implementation of a function to evaluate a Polynomial:

; evalBad: Polynomial num à num

; (evalBad aPoly x) evaluates the polynomial aPoly,

; at the given value, x.

(define (evalBad aPoly x)

(cond

[(ConstPoly? aPoly) aPoly]

[(NonConstPoly? aPoly) (evalBadHelp aPoly x 0)]))

; evalBadHelp: Polynomial num num à num

; Evaluates the given polynomial, p, at the given value, x, where

; the initial coefficient of the polynomial is incremented by

; acc times x.

(define (evalBadHelp p x acc)

(cond

[(ConstPoly? p) (+ p (* acc x))]

[(NonConstPoly? p)

(evalBadHelp (NonConstPoly-lower p)

x

(* (+ (NonConstPoly-coef p)

(* acc x))

(pow x

(- (sub1 (NonConstPoly-order p))

(cond

[(ConstPoly? (NonConstPoly-lower p)) 0]

[(NonConstPoly? (NonConstPoly-lower p))

(NonConstPoly-order

(NonConstPoly-lower p))])))))]))

Even though the above function always yields the correct results, do you see any unsound programming practice in the above code body? If so, please explain clearly and completely what you feel is improperly implemented about this code and why it is unsound. Assume that you are given the contract, purpose and header for the evalBad function only and thus have no control over them. Do not waste your time verifying that the math is correct. Look for more fundamental issues.

2-3 sentences maximum!!

The helper function violates the encapsulation of the lower polynomial.