CPSC 215 — Assignment 5
Rule-Based, Iterative, and Recursive Programming

Fall 2001 — November (27^th), 2001 — C. Jacob

<your name here>
<your student ID here>

Instructions for this Assignment

Welcome to the fifth, and last, assignment for CPSC 215 — Introduction to Programming with Mathematica.

(1) In the following sections, enter your answers as Mathematica commands in the Input cells provided after each problem description or question.

(2) After you have solved all the problems, go to section "How to Submit Your Notebook" and follow the instructions.

Problem 1: Programming a Simple Equation Solver

Suppose we want to implement a solver for simple x-equations such as 2  x - 3 = 0, for the variable x.

Usually, solving these equations is done in a step-by-step manner, following simple rewriting rules (remember the toyIntegrate function from the lecture).

In order to solve the above equation, 2  x - 3=0, the steps are as follows:

2  x - 3 = 0

2  x = 3		: Bring -3 on the right side, with the sign changing from minus to plus.

x = (3/2)		: Bring the scaling factor 2 to the other side, using the operation of division.

Obviously, each step preserves the contents (the "sematincs") of the equation, however, symbols and numbers get rearranged in a way such that, finally, the variable x is the single symbol on the left side of the equation. Hence, we have a solution for x.

Similar steps apply for the equation 5 + (x/3) = 0, which uses the "inverse" operations of addition and division. Therefore, the solution goes as follows:

5 + (x/3) = 0

(x/3) = -5		: Bring the 5 to the right side, changing its sign.

x = -5×3 = -15	: Bring the (1/3)to the right side, using multiplication.

Now here is your task:

Simple Equation Solver: Procedural Programming Style

Write a function equationSolve[eqn], which implements an equation solver for equations in the form as the two examples above. We further assume that an equation is represented by the following expression,

equation[left, right, variable]

such that the two examples from above are written as

equation[2 x - 3, 0, x]

equation[5 + (x/3), 0, x]

Note: One reason why we are using this expression notation is that we cannot use the "="-sign, as it is already reserved for assignments. (There are ways to get around this difficulty, but we won't be concerned about these details here.)

Here is how your equationSolve function should work.

For the first example from above, the equationSolve function should return the solution for x in the form of a rewrite rule:

equationSolve[equation[2  x - 3, 0, x]]

Here is how the second equation would be solved:

equationSolve[equation[5 + (x/3), 0, x]]

Bonus Question:

Can you modify the equationSolve function so that it will give you each step of the rewriting of the equation?

Call your new function equationSolveStepByStep.

Show that it works for the above given examples.

Programming a Simple Equation Solver: Rule-based Style

Reimplement the equation solver function from above, but now using a rule-based style. Set up a list of rules, such that when they are applied to an equation they will transform it into the solved form.

The rules should work as follows. Let us assume we have the transformation rules stored in a list with name transRules.

equation[2 x + 5, 0, x] //. transRules

equation[3 + (x/3) - 5, 0, x] //. transRules

Bonus Question

Can you modify this equation solver function so that it will give you each step of the rewriting of the equation?

Problem 2: Summation — Functional, Iterative, Recursive

Given is the following function

oddSum(n) := (∑_(i = 0)^n) 3 (i^2).

Give implementations of this function in the following requested programming styles.

Test your implementations for the inputs 0, 1, 5, 10, 100.

Mathematical Odd Summation

Give an implementation that uses the mathematical summation (as in the definition above).

oddSum[n_] :=  ...

Iterative Odd Summation (using Do)

Give an implementation that uses the Do[...] command.

oddSumIter[n_] :=  ...

Recursive Odd Summation

Give a recursive definition for oddSumRec[0] and oddSumRec[n] with n > 0.

Problem 3: Weird Numbers: fab — Recursive, Iterative

Assume we have the following definition of a function fab(x):

fab(0) := (1/4)

fab(1) := (1/2)

fab(n) := ((fab(n - 1))^(fab(n - 2))), for n > 1.

Recursive Definition of the fab Function

Give a recursive implementation of a function fabRec[n] which returns the n-th fab number.

Test your function for n = 0, …, 20 and show the graph of the generated numbers.

Show a graph of these values.

How long does it take to evaluate each call of fabRec[n] for n = 0, …, 20? Give a table of these timings.
Note: Use the function Timing.

Iterative Definition of the fab Function

Give an iterative implementation, fabIter[n], of the function fab. Use constructs such as Module[...] and Do[...] to implement your function.

fabIter[n_] :=  ...

Test your function fabIter[n] for n = 0, …, 20.

How long does it take to evaluate each call of fabRec[n] for n = 0, …, 20? Give a table of these timings.

Bonus: Improvement of the Recursive  fab Implementation

How can you speed up the calculation for the fab numbers? Make a suggestion for a faster implementation.

How to Submit Your Notebook

Step 1

Save this notebook under the filename Ass5-<your student id>.nb.

For example, if your student ID is 123456, you would save this notebook as Ass5-123456.nb

Step 2

Send your notebook by email to your Teaching Assistant (TA).