Question 1 (a) Write a Scheme procedure to evaluate the expression...

Question 1
(a) Write a Scheme procedure to evaluate the expression: 3*4-2+(9-4*2)+1.
(b) Write a Scheme procedure to evaluate the expression: -1*(7-2+5)*2/(1+2*3).

Question 2
A function f is defined by the rules:
f(n) = n, if n<4
f(n) = f(n-1) + 2f(n-2) + 3f(n-3) + 4f(n-4), otherwise
(a) Write a procedure that computes f by means of a recursive process.
(b) Write a procedure that computes f by means of an iterative process (i.e., a tail-recursive program).

Question 3
Pascal's triangle - The numbers at the edge of the triangle are all 1, and each number inside the triangle is the sum of the two numbers above it.
Write a procedure that computes elements of Pascal's triangle by means of a recursive process.
E.g., (pascals 0 0) → 1
(pascals 2 1) → 2
(pascals 4 2) → 6

Question 4
Consider the definition of general summation of numbers between two values

(define (sum term a next b)
(if (> a b)
    0
    (+ (term a)
       (sum term (next a) next b))))

Given helper functions inc and identity one can, for example, define a function that sums all integers from a to b:
(define (inc x) (+ x 1))
(define (identity x) x)
(define (sum-integers a b)
(sum identity a inc b))
The general sum procedure above generates a linear recursive process.
Rewrite it as an iterative process.

Question 5
(a) Write a procedure (product term a next b) similar to the summation procedure above. It should return the product of the values of a function at points over a given range. Write this as a recursive process.
(b) Define factorial in terms of product.
(c) Rewrite your product from part (a) to produce an iterative process.

Question 6
The following program can be used to determine if a given interpreter is using applicative-order evaluations or normal-order evaluation:
(define (p)(p))
(define (test x y)
   (if (= x 0)
      0
      y))
(test 0 (p))
(Assume that the evaluation rule for the special form 'if' is the same for both evaluation schemes: The predicate (condition) expression is evaluated first, and the result determines whether to evaluate the consequent (then) or the alternative (else) expression.)
a. What will be the behaviour of this code on an interpreter that uses applicative-order evaluation? Explain why.
b. What behaviour will be observed with an interpreter that uses normal-order evaluation? Explain why.
c. Which style of interpreter does Scheme use (assuming #lang R5RS)?

Question 7
Newton's method for cube roots is based on the fact that if y is an approximation to the cube root of x, then a better approximation is given by the value: (x/y²+2y)/3
Use this formula to implement a cube-root procedure analogous to the square-root procedure.

Question 8
Observe that our model of evaluation allows for combinations whose operators are compound expressions. Use this observation to describe the behaviour of the following procedure:
(define (a-b a b)
   ((cond ((> b 0)+)((= b 0) -)(else *)) a b))
Your answer should describe what happens for all integer values of a and b. Illustrate your answer using the substitution model.

Question 9
(a) Using Newton's approximation for square root finding as shown in the Scheme notes modify the block structured form of the algorithm in order to allow a user-defined procedure for good-enough? to be used in the algorithm. The user-defined procedure should be passed into the square-root-finding procedure.
Demonstrate in your test cases that you can calculate the (my-sqrt 25) using differing 'good-enough?' functions that vary the accuracy of the result.
(b) Extend the solution provided in (a) to force the termination of the algorithm after a maximum number of iterations. This number should be passed in as well (my-sqrt 25 good-enough1 3)→5.406026962727994
(c) [5 marks] Create a new-if procedure as below. Replace the use of if in sqrt-iter with new-if. Does the new version work? Explain why or why not.
(define (new-if predicate consequent alternate)
   (cond (predicate consequent)
         (else alternate)))

Documentation & Testing
Document the purpose of each method including its expected inputs (parameters) and output (return).
It is up to you to make a convincing, documented test plan. There are standard tests that must be done (base case, testing of some upper or lower bounds of the input or results, etc.) but it is up to you to come up with a sufficient testing scheme.

Include evidence of testing your code either in comments at the bottom of your file or in a separate testing.txt file. Comment your testing as to what you are testing and why, giving expected output as well as observed output and explanations for any differences.
Include a readme.txt file with any instructions for your code, including which language you used if not explicitly defined in your code, and any major assumptions you have made.