Differentiation Exercise

Please note, the following was used for the application process to ; while still an interesting academic exercise, it is not valid for 2010 applicants. The OpenMP Exercise and/or ANTLR exercise is being used for the GSOC2010 application process.

/*
 * The following quiz is provided as an example of what we need for reverse
 * automatic differentiation. Work as much of this as you can. We are
 * not out to reinvent the wheel-- if you know of an open-source code that
 * can do the task or be extended to do the task, you may recycle provided
 * you cite the source. If recycling, create a single source file with just
 * the portions needed to do the specified operators.  Simply pointing at 
 * the other code is not considered doing the quiz, however.
 *
 * The goal is to convince yourself (and us) you have the basic skills needed to
 * do the project. When submitting answers, please indicate how many hours you
 * spent on each part. Partial solutions are fine -- we want to see how you think
 * not how fast you can code -- but solutions that run are better if you have the time.
 *
 * Answers may be submitted in C, C++, java, python, or pseudo-C-code. Both style and substance matter.
 * For pseudo-C-code, give full details of the data structures used and memory management.
 * Solutions in C++/python may NOT use operator overloading in any way-- use only the basic object
 * management features in OO languages.
 *
 * Given: 
 * (i) a text file containing, one per line, operators or variables
 * defining a well-formed scalar equation in postfix notation. Details to follow in (I).
 * (ii) a text file containing, one per line, variable names and their values separated by whitespace.
 *
 * Task 1: Write a function to load the file into a data structure that can be used
 * to evaluate the equation for any set of values assigned to the variables.
 * Hint: typically a tree or a postfix array of tokens is used. Some projects use both.
 * The final result from the function should be an object to be passed to 
 * other functions written in the following tasks.
 *
 * Task 2: Write a function (cite sources if borrowing code from other projects)
 * to read a file of type (ii) above and evaluate the relation.
 *
 * Task 3: Find a publication on the web or book in the library explaining
 * the reverse mode of automatic differentiation. Cite the book/pages and implement
 * a function computing the first partial derivatives given the inputs
 * read and data structures created in task1, task2; reverse AD must be used.
 *
 * Task 4: Critique your own solution. Tell us how you would make it more general,
 * Tell us where you think it might be slow and what experiments you would run
 * to test your theory. Tell us where you would need to add code to manage the memory in 
 * C (especially if you coded in a different language). Tell us anything else
 * notable about the code you wrote (or stole with citation) that will help us see just
 * how well you understand the task. If you know your code is incomplete,
 * create test input files that demonstrate the working features of your code
 * and at least one test input file that demonstrates each problem area/incompleteness
 * you know about and the error message output you created to notify the user.
 * If you know your code is not thread safe during evaluate, explain why and
 * what you would do about it given proper code-development time.
 *
 * Extreme extra credit given: For the restricted set of operators
 *         listed in (I) below, implement second partial derivatives. The
 *         set of operators in ascend is much nastier, and in ascend we will
 *         want to specify only certain variables out of the total set are
 *         of interest.
 * 
 * (I) The equation elements are as follows (c notation, floating point functions):
 * "="
 * "+"
 * "*"
 * "/"

 * "pow"
 * "sin"
 * "variable" variable-name
 * "constant" real-value
 * "integer_constant" integer-value
 * Example: a + b = c * d + 3.14 * pow( sin( e / f ) , 2)
 * will result in an input file (postfix notation)
= 
+ 
variable a 
variable b 
+ 
* 
variable c 
variable d 
* 
constant 3.14 
pow 
sin 
/ 
variable e 
variable f 
integer_constant 2
 
* (II) a test input for part (ii) and the example given in (I) would be

a 2.7
b 0.5
c 1.1
d 9.3
e 6
f 1.33

*  another test input for part (ii) would be

a 2.7
b 0.5
c 1.1
d 9.3
e 6
f 0

*/

/* Method signature hints (c notation) */
struct Equation {
// your details here
};

struct Equation * readEquation(const char * filename);
int readVariables(struct Equation *eqn, const char * filename);

/* how many distinct variables does the eqn have? */
int getNumberVariables(struct Equation *eqn);

/* the the name of i-th variable (0..getNumberVariables()-1) */
const char * getVariableName(struct Equation *eqn, int variable_index);

/* evaluation is computing F = left-hand-side - right-hand-side (the residual error if the
variable values given do not satify the equation). */
double *evaluate(struct Equation *eqn);

/* evaluate dF/d(all-variables) partial derivatives).
  and store results in the given array result[resultLen].
 */
int evaluateFirstPartials(struct Equation *eqn, double *result, int resultLen);