UploadBot: Restored page from Google Cache, uploaded by John Pye

2010-05-13T13:50:04Z

Restored page from Google Cache, uploaded by John Pye

New page

'''Please note, the following was used for the application process to [[Category:GSOC2009|GSOC2009]]; 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.

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

</pre>

[[Category:GSOC2010]]

Differentiation Exercise - Revision history

UploadBot: Restored page from Google Cache, uploaded by John Pye