CS 378 Assignment 2: Symbolic Algebra

Due: October 1, 2024.

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 last assignment.

1. 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.
   1. 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 cave; otherwise, it returns a list of first and rest that describes the path to the item. findpath is easily written as a recursive function. Examples:

      (findpath 'a 'b)     = nil
      (findpath 'a 'a)     = ()
      (findpath 'a '(a))   = (first)
      (findpath 'gold '(rocks gold (monster))) = (rest first)
      

   2. 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
      

   3. 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))))
        ==> music
      

2. 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 are provided.
   1. If the left-hand side (lhs) of e is v, return e.

         (solve '(= f (* m a)) 'f)  =>  (= f (* m a))
      

   2. 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))
      

   3. If the rhs is not v and not a cons?, return nil.

   4. If the rhs of e is a cons? (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))
      

   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).

   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))))))
   

3. 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:
   1. 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.)
   2. 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.)
   3. 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 capacitance? (Find c given v = 3.0, v0 = 6.0, r = 10000.0, t = 5.0.)
   4. 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.)