# Differentiation Exercise

From ASCEND

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