# Writing a Paper

## Audience

What background does the reader have?

• specialist versus non-specialist

Does the work build on past works that the reader is likely to have read, or is it a novel approach?

Does the work combine two or more distinct fields (inter-disciplinary)?

Extremes:

1. A survey paper that must motivate a work and be self-contained for the non-specialist.
2. A paper proving new theorems on interconnection networks, that builds on hundreds of past papers.

### More on "Audience":

The audience will determine the slant of your paper:

A paper about Toeplitz matrices for engineers would phrase properties and results in terms of the applications in which these matrices arise.

A paper for mathematicians typically considers the matrices in isolation from their applications.

Use the notation and terms that fit your intended audience; otherwise you may confuse the reader and the work may be impenetrable.

Example:

```    "Least squares problem" for linear algebraists versus
"Linear regression problem" for statisticians
```

When writing, ask yourself why a member of the intended audience should want to read your paper.

The question should be easy to answer in a well written paper.

Otherwise, consider altering the design of the paper, or doing more research before continuing the writing.

With a little effort it should be possible to make a paper partially understandable to non-experts:

"The titles, abstracts, and introductions of many mathematical papers say: "Outsiders keep out! This is of interest only to those few already in the know."

## Organization and Structure

1. Identify a strong "theme" for a paper before doing any writing or outlining.
2. Examples of alternate themes for a particular paper: (ranked from weakest to strongest)

1. An Overview of Chitra, a System for Modeling
2. Visualizing Categorical Data, and its Applications to Modeling
3. A New Model of Transient Behaivor

Rank your contributions, to identify the most important. Use the rankings to decide where to put the emphasis. The rankings also help you to write the title and abstract.

3. You should aim to
• minimize the length
• avoid repetition
• be concise
• state the general problem or solution, then lead to the specific result
4. Design the paper both for sequential and random acess. For random access, be sure definitions, equations, algorithms, and results are clearly displayed.

## Title

1. For every person that reads the whole text, 500 read only the title!
2. The title must balance two objectives:
1. catch the attention of the browser
2. provide a terse summary of the content to help someone carefully scanning the table of contents of a journal
3. Give preference for short titles:
4. "A decomposition of compact continua and related results on fixed sets under continuous mappings"

versus:

5. Avoid vague titles: "Parallel Programming Notes"

### Examples of good titles...

Computing the eigenvalues and eigenvectors of symmetric arrowhead matrices

[lively and informative]

How and how not to check Gaussian quadrature formulae

["How to" titles immediately arouse the reader's interest]

Gaussian elimination is not optimal

[A short, one sentence paper summary can make a great title]

How near is a stable matrix to an unstable matrix?

[A title that asks a question is direct and enticing]

ALGOL68 with fewer tears

[One can't help be curious enough to read the abstract!]

The art of programming

[Knuth's provocative title has inspired similar titles on other papers]

The ubiquitous B-tree

[An unusual but apt word catches the browser's attention]

### Breaking long titles across lines...

Rules of thumb

• a phrase should not be split between lines:
• ```     Bad:

Numerically Stable Parallel Algorithms for
Interpolation
Better:

Numerically Stable Parallel Algorithms
for Interpolation
```
• the lines should not differ too much in length:
• ```     Bad:

An Iteration Method for the Solution of
the Eigenvalue Problem
of Linear Differential and Integral Operators
Better:

An Iteration Method for the Solution
of the Eigenvalue Problem
of Linear Differential and Integral Operators
```
• a line should not start with a weak work such as a conjunction:
• ```     Bad:

A Method for Cutting
and Pasting Text Segments
Better:

A Method for Cutting and
Pasting Text Segments```

## Author List

1. There is no universal rule of how to order authors in a multiply authored paper. Some conventions are:
• authors are listed in order of decreasing amount of work
• authors are listed alphabetically
• the senior person (such as the director of a lab) is listed last

Sometimes two authors that frequently publish together may swap orders on each paper (e.g., Hennessy and Patterson).

2. Be sure to chose the name that you wish to be recognized by in your career, and use only this name on all works: Ernie Page versus Ernest H. Page This can pose a problem if you change your name after marriage.

## Date

Even if you do not publish the work, if you give a copy to someone else they will want to know when it was written.

Dating helps to avoid confusing drafts. I usually put the date into the header or footer to avoid confusing sheets of paper on my desk.

Put the date on a line by itself, usually after the author's name, on the first page of the document.

## Abstract

1. The abstract summarizes the paper's content.
2. The abstract must be self-contained.
3. The reader must be able to decide whether to read the paper based on the abstract.
4. There are often length limits on abstracts (e.g., 200-300 words) -- obey them.
5. Be sure to highlight the paper's main contributions in the abstract.
6. The abstract is usually one paragraph.
7. Avoid mathematical equations in the abstract, particularly displayed equations. (These may cause problems for abstract services.)
8. Do not cite references by number in the abstract. If a paper must be mentioned, spell it out in full:
9. An algorithm given by Boyd [Linear Algebra Appl., 9 (1974), pp. 95-101] is extended in this paper.

10. Make the abstract easy to understand for those readers whose first language is not English. Abstracts are sometimes translated to other languages.
11. Some journals disallow the word we, preferring the passive voice.
12. The abstract should convey the paper's conclusions.
13. Avoid starting an abstract with common phrases (e.g., "This paper..." or "In this paper...")

### Variations on abstracts:

Some conferences request submission of extended abstracts -- typically 50% the length of a full paper.

Conferences often publish poster abstracts -- typically one or two page summaries.

If you give a talk or serve on a conference panel, you may be asked abstract your presentation for publication in a proceedings.

## Key Words and Subject Classifications

Journals may ask for one or both of the following:

• Keywords
• Computing Reviews subject classifications

### Keywords:

Five to ten author-chosen words that best characterize the paper. Words are used in computer searches, therefore anticipate words a reader might search.

### Subject Classifications:

The Computing Reviews Classification System is a four-level tree that has three numbered levels and an unnumbered level of descriptors. The top level consists of eleven nodes, denoted by letters A (General Literature) to K (Computing Milieux).

Example:

G.1.3 [Numerical Analysis]: Numerical Linear Algebra - sparse and very large systems.

## The Introduction

The first sentence of a paper should

• be the best in the paper
• suggest the problem under consideration
• gently translate the reader into the body of the article

Example:

Formation of models of physical behavior underlies science. Yet our ability to construct behavioral models of parallel and distributed programs is very limited.

These opening sentences had enough impact on one reader that the reader quoted them in the opening paragraph of that they later wrote!

### What Goes Into an Introduction?

motivate why you are examining a problem area

define problem (which may first require some notation)

outline your solution to the problem:

• Summarize the results achieved

summarize contributions in a thesis or dissertation

summarize the organization of the rest of the paper, at the end.

### Length of Introduction

Keep the introduction short: About 10% of the paper.

Try deleting the first one or more sentences of your introduction, and see if it still makes sense:

To understand the central challenge in distributed and parallel processing, one only needs to read the popular press. Recent Sunday editions of The Washington Post contain articles querying business and academic leaders on whether parallel processing will fulfill its touted benefits. A common theme emerges in each: although we can manufacture parallel computers, can we program them?

versus:

Electronics technology has reached the point today where we can manufacture parallel computers -- but can we program them?

## Computational Experiments

Rarely do Computer Science "experiments" follow the classic science model: hypothesis, experiment design, results, conclusions.

More often, computer scientists report results of program measurements, referring to these as experiments.

Often papers report data collected from execution of programs to

• test a hypothesis
• compare competing methods
• verify theoretical predictions
• characterize empirically the error in a method
• characterize the rate of convergence of an algorithm
• characterize the dynamic behavior of a program or system
• characterize empirically the performance (e.g., speedup) of a parallel algorithm
• tune parameters in a code or a system
• demonstrate "proof of concept" (e.g., virtual memory can be implemented on a message passing system with reasonable performance)

Be sure to state clearly:

• the hypothesis tested or the experiment objective
• the experimental method with sufficient detail so that a reader can replicate the experiment:
• all required parameters
• all necessary algorithms
• the type of random numbers (e.g., Normal (0,1)) and the type of random number generator used (e.g., LCG)
• the machine model, processor speed, memory size, OS version...

When showing convergence or accuracy of a method, tabulate errors rather than the values themselves.

Report normalized errors.

Repeat the experiment at least three times, and report at least the sample variance of three observations, or even better the confidence interval. Why repeat the experiment?

• Factors such as cache-warmup can cause variation on a single-user machine.
• Background traffic in a network or a multi-user system necessitates tens or hundreds of observations

## Tables

1. If a reader should compare similar quantities in a table, arrange those quantities in columns.
2. Do not state numerical results to more significant figures than are known for the data.
3. Carefully choose between a table and a graph. Use a graph:
• when you wish to show a trend
• when there are more than 20 numbers
4. Avoid tables with too much detail -- consider using an Appendix if you must show many details.
5. Use a table design that is as simple as possible to improve readability. For example, omit unnecessary rules (lines).
6. Summarize the table in words when you first refer to it in the paper.

## Citations

### Style of citations

Styles:

See Abrams [1].
See Abrams [ABR94a].
See Abrams 1. (Symbol "1" should be a superscript.)
See Abrams (1994a).

1. The organization for which you work or the journal in which your work is published will set the style for citations.
2. Avoid using a citation as a noun, especially at the beginning of a sentence:
3. Awkward: [1] proves the theorem.

Better: Jones [1] proves the theorem.

4. When citing a specific item in a book, use a chapter number or page numbers.
5. Example: ...several variations exist [2, Chap. 7].

6. Order citations that appear together in ascending order (citation number or explicit date).
7. Examples:
Several variations exist [1,3,9].
Variations have been developed by Smith (1974) [9],
Barnes (1982) [3] , and Jackson (1989) [1].

Incorrect: Several variations exist [3,9,1].

8. Include the author's name unless the citation is more than just a passing one. This is more informative and "has an enlivening effect because of the human interest it introduces".

### When to Cite

• you are referring to someone else's ideas or results
• you do not want to define a term (e.g., virtual reality ), but want to use the definition of an expert in the field.
• you want to support an argument that you are making (e.g., why formal methods are important to software engineering)

But be careful not to overuse citations. Do not cite the same paper twice in one paragraph!

Be sure to clearly identify what part of a paper is your own creative idea and what is existing literature. I suggest using words such as

• We propose...
• Our use of geometry to solve the problem is, to our knowledge, novel.

### Location of citations

Locate the citation in a place that does not intrude on a sentence.

```     Awkward: The method was found [17] to be unstable.
Better:  The method was found to be unstable [17].
```

Be sure that the sentence reads properly when the citation is deleted.

```     Incorrect:  This question has been addressed by [5].
Correct:  This question has been addressed by Ott [5].
```

### Reference lists

Carefully choose what to include and exclude from your reference list!

• Some readers read the reference list after the title, and ignore the paper if the references are unfamiliar.
• Editors often choose reviewers from the reference list.
• You may wish to include a key paper in the reference list.
• Sometimes you must balance making the list comprehensive and consuming too many pages when there is a page limitation for a paper.
• Keep the reference list timely -- even while the paper undergoes years of referee delay

## Conclusions

The conclusions can:

• draw broad inferences from the data or methods given earlier
• speculate on or posit facts or explanations that might hold true but are unsupported
• list open problems
• list directions for future research
• mention work in progress
• significance

It is dangerous to refer to works in progress -- they may never materialize! It is safer to put intermediate results into a technical report, and then cite the technical report.

The conclusions section should not:

• repeat sentences that appeared earlier in the paper
• summarize the paper, unless accompanied by new insights

## Acknowledgements

You should acknowledge

• financial support for your work
• "This research was supported by the National Science Foundation under grant DCR-1234567."

[Some funding agencies tell you the exact words to use!]

"This work was supported by an SERC Fellowship."

• individuals that read the manuscript in draft form

[Note: X may be the anonymous referees.]

• individuals with whom you discussed the ideas
• "I thank X for discussions during the development of this work."

• facilities or software systems essential to your work
• "X provided the database traces used in this paper."

"The experiments were performed using the computer facilities of the Argonne National Laboratory."

"The illustrations were drawn using Jane Ott's pic software.

## Appendix

An appendix can be used to provide essential information that would distract the reader if it were placed in the paper body.

Examples:

• detailed algorithms
• proofs that do not enlighten the reader, but are needed to convince the reader that a theorem is true
• detailed results of a computational experiment
• a computer program listing (in a technical report, thesis, or dissertation)
• a formal specification of something (i.e., a protocol)
• a table of values (e.g., the values of the Chi-squared distribution in a statistics text)

## Reference List

If I were paid based on the number of errors that I found in a manuscript, I would always start with the reference list!

Correct example:

J. H. Wilkinson, Error analysis of floating-point computation, Numer. Math., Vol. 39, No. 5, Nov. 1983, pp. 639-648.

I highly recommend use of an automated tool to maintain a bibliography for everything you write, and to automatically generate a reference list using a consistent style.

Every journal has its own style of references. Usually the copy editor will change your style to fit that of the journal.

Hence

• You do not need to carefully follow the journal's style (unless the editor explicity instructs you to do so)
• You must, however, put all essential information in your reference list, including:
• page numbers (for serials)
• issue number (for serials)
• volume number (for serials)
• publisher (for books)
• year of publication (for a book, the latest year)
• edition, for a book with more than one edition
• month of publication (for technical reports or conferences)
• Higham suggests that an address can be ommitted with well-known publishers

### Specific suggestions on reference lists

1. Do not cite a work A that is referenced in paper B until you personally find A in the library!
• Sometimes B contains an error in the reference list.
• Higham describes a paper by Vieira and Messing, cited as Viera only by one author. Afterwards subsequent authors ignored rule (1). As a result, the paper was placed too low in a list of most-cited papers.

• Sometimes the author of B did not carefully read A, and misinterprets A. You do not want to look as ignorant as the authors of B!
2. Always give all initials of an author -- not just the first or first and middle. It is not unusual for multiple researchers to have the similar initials!
3. H. A. Guvenir (that's me)
A. Guvenir (another person who works in something else)

4. Be consistent -- always use the first name or always abbreviate the first name.
5. You can inadvertently insult someone by failing to use their first name when you use the first name for other authors in a reference list.

6. Copy bibliographic information from the first page of a journal paper, not the title page of the journal.
7. Before citing a technical report, ask the author if it has appeared in a conference or journal. Also
• the title may have changed
• the content may have changed
8. In book titles, add a colon to separate a title from a subtitle, even if the colon does not appear in the book.
9. K. M. Chandy and J. Misra, Parallel Program Design: a Foundation, Addison-Wesley, 1988.

10. Use italics for the name of a separately published work (e.g., book, conference proceedings name, video tape, technical report). Use quotations (or lower case letters) for works published within another work (e.g., papers).
11. You may want to give the International Standard Book Number (ISBN) for more obscure sources:
12. 0-89871-314-5
0 = Publisher from English speaking country
89871 = Publisher (SIAM)
314 = book's individual number (Book 314 from SIAM)
5 = checksum

There is also an International Standard Serial Number (ISSN) for serial publications.

13. Be sure that all references are actually cited in the paper! Some copy editors will ask you to do this on the paper proofs.

## Specifics and Deprecated Practices

### Dangling Theorems

1. Avoid this construct, which tries to avoid repeating the word "theorem":
2. The result is proved in the following Theorem 3.13. If f is ...

3. Do not use a section title as the antecedent of a pronoun:
4. 5.1. Accuracy of the Computed Solution.

It depends on the machine precision....

### Naming Mathematical and Other Objects

1. Number only those equations that are referrence elsewhere in the text or which are likely to be cited by other authors.
2. Refer to an equation as follows: "Now we solve (3.9)."
3. LaTeX will automatically number equations, theorems, lemmas, definitions, ...

4. Give all algorithms a name.
5. Consider giving the problem that you are solving a name, especially so that subsequent authors can refer to it:
6. Example: The synonym problem in memory addressing is solved by ...

### Footnotes

• Use footnotes sparingly. Consider using parentheses instead.
• Some journals do not allow footnotes.
• The correct use is to "add a note or comment that would deflect from the main message of the sentence." [H, p. 91]
• Be careful not to put critical information or definitions into footnotes that a reader may overlook.

### Captialization

References to proper nouns should be capitalized:

See Theorem 1.5, the proof of Lemma 3.5, and the discussion in Section 6.

See the last theorem, the last lemma, and the next section.

### "This Paper Proves..."

Awkward:

This paper proves....

Section 3 shows....

Better:

We prove ....

We show ....

Theorem 2 states....