CS 378 Assignment 2: Symbolic Algebra
Due: February 18, 2021.
Files: cs378.clj formulas.clj
The following functions that operate on trees should be recursive.
Some useful functions that you may need are provided in the file
cs378.clj, and you will need some of your functions from the
- You have been assigned to explore a cave to see whether it
contains a treasure. The treasure is too heavy for you to carry out;
you must return instructions to get to the treasure.
Each room of the cave is either a junction, with two connecting passages
called first and rest, or it is a dead end that may or
may not be a treasure.
- Write a search function (findpath item cave) that finds a path
to a part of cave that matches item; we will asssume
that = can be used to test. findpath returns
nil or false if item does not occur in
it returns a list of first and rest that describes the
path to the item.
findpath is easily written as a recursive function.
(findpath 'a 'b) = nil
(findpath 'a 'a) = ()
(findpath 'a '(a)) = (first)
(findpath 'gold '(rocks gold (monster))) = (rest first)
- Write an interpreter (follow path cave)
that will follow a path as returned by findpath and retrieve the
contents of cave at the location specified by path.
An interpreter reads a list of instructions and performs the action
specified by each instruction.
(follow '(rest first) '(rocks gold (monster))) = gold
- Write a function (corresp item tree1 tree2)
that finds the item, corresponding to item in tree1,
in tree2. Example:
(corresp 'light '((my eyes) (have seen (the light)))
'((my ears) (have heard (the music))))
- Write a recursive function (solve e v) that
attempts to solve the equation e for variable v.
We assume that any variable occurs at most once in e, and that the
equation initially has a left-hand side that is a single variable.
The basic idea of solve is to test for equations that are
already solved or unsolvable (base cases); otherwise, solve
will search for a solution by applying laws of algebra to transform the
equation into different forms. solve is a kind of tree
recursion -- not recursion on first and rest, but
recursion whose branches are the allowable algebraic transformations
of the input formula into new
formulas. The functions op, lhs and rhs
You should handle the operators + - * / sqrt exp log and
(expt x 2). exp (e to the given
power) and log (logarithm to the base e)
are inverses, and (expt x 2) and sqrt are inverses
(we will assume that expt is only used with the power 2).
The operator - can be either unary (having only one argument,
i.e. minus) or binary (having two arguments, i.e. difference),
which must be treated differently. We will assume that all other operators
will have a fixed number of arguments (either one or two).
- If the left-hand side (lhs) of e is v,
(solve '(= f (* m a)) 'f) => (= f (* m a))
- If the right-hand side (rhs) of e is v, return
a new version of e with its lhs and rhs reversed.
(solve '(= (* m a) f) 'f) => (= f (* m a))
- If the rhs is not v and not a seq?,
- If the rhs of e is a seq? (i.e. an operation),
try to solve the equation by applying algebraic
laws, which will make a new equation by moving things to the left side.
Then try to solve that equation. For binary operators, there will
be two possibilities, both of which must be tried. For example, given the
original equation x = y - z, we could (a) add z to both sides
to give x + z = y, or (b) subtract y from both sides to give
x - y = - z and then negate both sides to give y - x = z
(these two operations can be combined as a single transformation).
(solve '(= x (- y z)) 'y)
(solve '(= (- y x) z) 'y) ; first try: nil
(solve '(= (+ x z) y) 'y) ; second try: succeeds
=> (= y (+ x z))
Demonstrate that you can solve the following equations for any of their
variables. These equations are defined in the file.
(= s (* 0.5 (* a (expt t 2))))
(= s (+ s0 (* v t)))
(= a (/ f m))
(= v (* a t))
(= f (/ (* m v) t))
(= f (/ (* m (expt v 2)) r))
(= h (- h0 (* 4.94 (expt t 2))))
(= c (sqrt (+ (expt a 2) (expt b 2))))
(= v (* v0 (- 1 (exp (/ (- t) (* r c))))))
- Students in beginning physics courses
may solve homework problems by searching through the
book for an equation that relates the desired variable
and the variables whose values are given.
Define a function
(solveit equations var values) where
equations is a list of equations, var is a variable
whose value is desired, and values is an association list of variables
with known values. Search the list equations to find an
equation that relates exactly these variables; a function set=
is provided. Solve the equation for
the desired variable and evaluate the solved equation to find its value.
(solveit formulas 'm '((f 10.0) (a 2.0))) => 5.0
Use the equations in formulas to solve the following problems:
- A pebble is dropped off the UT tower and hits the ground after
4 seconds. What is the height of the tower in meters?
(Find h0 given h = 0.0, t = 4.0.)
- A car accelerates from zero to 60 mph (88 ft/s) in 8 seconds.
What is its acceleration? (Find a given v = 88.0, t = 8.0.)
- A capacitor is charged through a resistance of 10K ohms using a
6 volt battery. It reaches 3 volts after 5 seconds. What is its
(Find c given v = 3.0, v0 = 6.0, r = 10000.0, t = 5.0.)
- A ladder 10 ft long leans against a wall. The foot of the ladder is
6 ft from the wall. How far up the wall is the top of the ladder?
(Find b given c = 10.0, a = 6.0.)