[18335fall08] some info on the final project paper

[Steven G. Johnson]

Hi gang,

As I said in class, the final project is due on the last day of class  
(Wed., Dec. 10), which officially is the last date that I am allowed  
to have assignments due.  I wanted to give you a few more tips on what  
I'm expecting your end result to look like.

In terms of results, I'm not expecting anything publication-worthy ---  
small scale tests of known algorithms on known problems is fine.  But  
it should still be clear and convincing.  e.g. if you are trying to  
demonstrate some trend, you should have enough data points and a well- 
thought-out numerical experiment for that purpose, clearly presented.

It's fine to use "canned" software like NLopt, LAPACK, etcetera,  
implementing the existing algorithms.  However, if your paper is about  
some algorithm X, or it is about a variety of algorithms for some  
purpose and you find X to be the best, then I do expect you to write  
at least a proof-of-concept implementation (e.g. in Matlab) of  
algorithm X in order to show that you understand the algorithm well  
enough to implement it yourself.   Your implementation does not have  
to be competitive in terms of performance or robustness with  
production-quality off-the-shelf software, however.

In terms of the paper, I expect it to be structured like a research  
paper, aimed at the level of your peers in the class.  It should include

1) introduction - motivate your project, explaining the basic problem  
your method address and where this problem arises.  give some  
background and history, both of the problem in general and the  
specific method(s) you are looking at, citing the relevant papers in  
the literature.  give an overview of what you did in the project and  
of the remainder of the paper

2) methods - describe the algorithms that you are looking at, and the  
implementation that you used.  (Possibly including pseudocode,  
although not pages of pseudocode, but no actual programming code  
should go here.)  If you compared several off-the-shelf algorithms,  
you don't need to explain all of them in great detail; it is okay to  
focus on one or two and given a brief overview of the others you  
compared.

You should have some explanation of *why* the method works, not just  
how. Depending on how theoretical your focus is, this may include  
proofs, or it may just consist of simple heuristic explanations.   
Diagrams are helpful and encouraged!

3) results - convincingly presented graphs and discussion of any  
numerical experiments you did.  In general, I expect you to look at  
both performance and accuracy (floating-point and/or other  
approximations) of your algorithm.  Ideally, you should also compare  
to at least one competing approach for the same problem.  Obviously,  
the precise nature of the problem you look at will determine precisely  
what numerical experiments you perform.  For example, if you have an  
approximate method, you might look at the performance as a function of  
the required accuracy in the solution.

Note also that the best way to measure performance might not be timing  
measurements (e.g. if you compare C code for one algorithm to Matlab  
code for another algorithm, timing comparisons might be very  
misleading because they are mainly comparing C vs. Matlab and not  
algorithm 1 vs. algorithm 2).  For example, if you are looking at  
different optimization algorithms, counting the number of times the  
objective function is evaluated to obtain the solution to within a  
given accuracy might be more appropriate.   Or if you are comparing  
ODE integrators for y' = F(y), you might compare the number of times  
F(y) is evaluated for a given level of accuracy.

4) discussion of results - explain features you observed.  For  
example, if you looked at roundoff errors, a theoretical analysis of  
roundoff and conditioning in your algorithm might be appropriate.

5) conclusion - a summary of your findings.  ("This algorithm sucks  
for this problem" is an okay finding, as long as you have convincingly  
demonstrated that the problem is intrinsic to the algorithm and not  
merely a flaw or bug in your implementation of it.)

As mentioned on the course web page, I expect the formatting of the  
paper to resemble a paper in the SIAM Journal on Numerical Analysis.   
(You can find templates on http://www.siam.org/journals/auth- 
info.php ... also, you can just look at some random papers in that  
journal to see what they look like.)  I don't care about every tiny  
detail, as long as it is basically similar.  Do *not* use preprint  
format (preprints are normally double spaced); use the single-spaced  
format like the published journal papers.

The paper should be 5-10 pages long, including figures.  This does not  
include source code; you should attach a printout of any code you  
wrote as an appendix.  (Do *not* print out source code you downloaded  
from elsewhere, unless you substantially modified it.  I don't want  
printouts of all of LAPACK, for example!)

--SGJ