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.
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
anxn
+ an-1xn-1+ ... + a1x + a0,
where n is a non-negative integer, ak (k = 0.. n) are numbers, and an is a number not equal to 0. n is called the order (or degree) of p(x), ak(k = 0.. n) are called the coefficients of p(x), and an is called the leading coefficient of p(x).
For example:
· p(x) = 12x5 - 3x2 + 7 is a polynomial of degree (order) 5 with leading coefficient 12. -3x2 + 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 = 7x2
-5x + 42
(define p3
(make-NonConstPoly 1 5 p2)) ; p3 = x5
+ 7x2 -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.
b. (15 pts) Write the template for a function that processes a Polynomial.
(define
(f-Poly 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
;;
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:
anxn + an-1xn-1+ ... + a1x + a0
= ((..(anx + an-1) x + an-2)x
+ an-3)x + ... + a1)x + a0
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 an-1 and an-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
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!!