CS130N Assignment 2: Symbolic Differentiation

• Use the following rules of differential calculus to implement a symbolic differentiation package:
  $$\begin{array}{lll} D(x) & = & 1 \\ D(a) & = & 0, \mbox{ if $a$\ ... .../(v^2) \\ D(u^v) & = & D(u)*(v*(u^{(v-1)})) + ((\ln{u}*D(v))*(u^v) \end{array}$$

• Implement multivariate polynomial expressions either as generalized lists or as binary trees. The input can be given in any of the following forms
  1. a string in fully parenthesized infix form
  2. a string in postfix form
  We will use the symbol $\sim$ for unary negation and the symbol ln for the unary function $\ln$. For example, the expression
  $$3 \ln{(x+1)} - (-a)/x^2$$
  may be given as the following strings:

  fully parenthesized infix:

   ((3*ln(x+1))-(~a/(x^2.0)))
  

  postfix:

   3.0 x 1 + ln * a ~ x 2 ^ / -
  

  Note that
  1. opearators to be supported are:

                 + - * / ^ ~ ln (usual meanings)
     

  2. numbers may be written as either 3 or 3.0
  3. there will be no blanks in the infix input string. The tokens in the postfix input string will be separated by exactly one blank.
  4. variables names may contain arbitrary number of characters and numerals but must start with an alphabet.
• You have to provide methods for returning output strings in fully parenthesized infix and postfix forms according to the above convention. Note that if you blindly apply the rules for differentiation, you may get
  $$0*ln(x+1) + 3((1+0)/(x+1)) - (0/x^2 - (-a*(1*(2*x^{2-1}) + \\ (\ln{(x)} * 0)*x^2))/(x^2))$$
  which is correct but somewhat unsatisfactory. You will get extra credit if you can program the rules for $x + 0 = x$, $x * 0 = 0$, $x^0 = 1$, $x^1 = x$, $0/x = 0$, $x + x = 2x$, $5 - 3 = 2$ and so on. The more simplified the output is the more credit you will get.

  In particular, you will get bonus if you can provide methods for checking equality of expressions. This will require you to reduce your expressions to a suitable normal form.

• Implement a Java class called deriv which implements the interface symexp.java.
• Make the Java class deriv a part of package myutils (put the file deriv.java in a sub-directory called myutils and include the statement package myutils; at the top of the file.) deriv.java is the only file you will submit by clicking here.
• You may use the Java class StringTokenizer and Java type char to parse the input string. Look at Text.java for their use.
• The last date for submission is March 1, 2001. There will be a deduction of 1 mark for every day's delay after the last date. This assignment will have to be done individually. I will appreciate if you do not make any requests regarding extension of the the last date or doing the assignment jointly with a partner.
• Do not panic, but if you successfully complete the assignment you would have programmed a recursive descent parser among a few other things!

Cheers.