CS 378 Assignment 1: Recursion, Lists, and Trees

Due: September 10, 2020 via Canvas.

Files: cs378.clj

  1. Start Clojure. You can use the command clojure on the lab machines, and it is a good idea to download it for your laptop from clojure.org under Get Started. Try a few things:

  2. Write a function (sum lst) that adds up the numbers in lst. Write (a) sum in recursive style, (b) sumtr in tail-recursive style, and (c) sumr using reduce.

  3. Write a function (sumsq lst) that adds up the squares of numbers in lst. Write (a) sumsq in recursive style, (b) sumsqtr in tail-recursive style, and (c) sumsqmr using map and reduce.

  4. Write a function (stdev lst) that finds the standard deviation of the numbers in lst. The standard deviation is the square root of the variance. The variance is equal to the mean square (mean square = (sum xi2) / n) minus the square of the mean (= mean2). Calculate the standard deviation for the list of numbers lstnum: 

    (def lstnum '(76 85 71 83 84 89 96 84 98 97 75 85 92 64 89 87 90 65 100))

  5. Write tail-recursive functions, (union lsta lstb) that finds union of two sets represented as lists, and (set-difference lsta lstb). These are only slightly different from the intersection function in the lecture notes.

  6. Binomial coefficients are the numeric factors of the products in a power of a binomial such as (x + y)n. For example, (x + y)2 = x2 + 2 x y + y2 has the coefficients 1 2 1. Binomial coefficients can be calculated using Pascal's triangle: 
                1                   n = 0
         1     1
      1     2     1
   1     3     3     1
1     4     6     4     1       n = 4

    Each new level of the triangle has 1's on the ends; the interior numbers are the sums of the two numbers above them. Write a program (binomial n) to produce a list of binomial coefficients for the power n using the Pascal's triangle technique. For example, (binomial 2) = (1 2 1). You may write auxiliary functions as needed. binomial should be a set of recursive programs that manipulate lists, for example, make a new row (1 3 3 1) from an existing row (1 2 1).

  7. Write a function (maxbt tree) that finds the maximum value in a binary tree containing numbers and other things. For this function, we will consider both the first and rest of a cons as subtrees. We will assume that every element of the tree is a cons?, a number?, or something else. We will assume that every number is greater than -999999.
    Example: (maxbt '((1 pie 7) (-3 2 eggs) (((foo (((8))) ))) )) = 8

  8. An algebraic expression can be written as a linked list tree: an expression is either a number, a symbol or a list (op lhs rhs) where op is an operator and lhs (left-hand side) and rhs (right-hand side) are expressions. The functions op, lhs and rhs are provided. Write a function (vars expr) that returns a set of the variables in an expression. Note that the op and numbers are not variables. The result is a set (list) of variables in any order; the union function above can be used.
    Example: (vars '(= f (* m a))) = (f m a)

  9. Write a function (occurs item tree) that tests whether the item occurs anywhere in the expression tree. We will assume that the item can be tested with = and is not a cons?.
    Example: (occurs 'm '(= f (* m a))) = true

  10. Write a function (myeval tree) that evaluates (finds the value of) an expression tree where the leaves are numbers. The value of a number is the number itself. If the expression is a cons?, first find the value of its arguments (lhs and rhs), then perform the operation denoted by the op. The possible operations are + - * / expt . (expt x n) raises x to the power n; a similar Clojure function is Math/pow. Note that - could have either one operand (minus) or two operands (difference); all other operations are assumed to be binary. myeval is a small version of eval, which is the Lisp interpreter; use myeval rather than eval in your function.
    Example: (myeval '(+ 3 (* 5 7))) = 38

  11. Write a function (myevalb tree bindings) that evaluates an expression tree where the leaves are numbers or are variables whose values are given in the bindings. bindings is an association list, ((var value) ...), that gives values for variables. This version of myevalb is an easy extension of the previous one. The function assoc is provided.
    Example: (myevalb '(+ 3 (* 5 b)) '((b 7))) = 38

  12. There is a close relationship between programming languages and trees. A compiler performs parsing, which converts a character string in a programming language to a tree. Unparsing, converting a tree to a program, is also useful. Write a function (tojava tree) that translates an expression tree to a string that is a line of Java code. The line of Java code should be terminated by a semicolon character. We will assume that the expression can contain the operators = + - * / as well as single-argument functions such as sin.

    Operators have precedence, which determines the order in which operations are performed when an expression is not parenthesized. We will assume that = has precedence 1, + - have precedence 5, and * / have precedence 6. A subexpression needs to be parenthesized if its precedence is less than or equal to the precedence of its surroundings; otherwise, it should not be parenthesized. Make an auxiliary function that includes precedence as an argument. The starting precedence can be 0, so that any operator will be higher in precedence.
    Example: (tojava '(= x (* (+ a b) c))) = "x=(a+b)*c;"

    We will assume that a unary minus should always be parenthesized, and that it has a precedence of 6.

    For functions that are not in the operator list, such as sin, make the name be Math. followed by the function name, and make a function call form. For example, (sin x) would become "Math.sin(x)" .

    The function (str ...) makes a string out of its arguments.