Mathematics - Writing for Computer Science - page 126

An inverted list for a given term is a sequence of pairs, where the first element
in each pair is a document identifier and the second is the frequency of the
term in the document to which the identifier corresponds.

An inverted list for a term t is a sequence of pairs of the form d , f , where

each d is a document identifier and f is the frequency of t in d .

In the first version, the author has had to struggle to avoid ambiguity.
Many terms have well-defined mathematical meanings and are confusing if used
in another way.

Normal, usual, typical . The word “normal” has several mathematical meanings;
it is often best to use, say, “usual” or “typical” if a non-mathematical meaning is
intended.

Definite, strict, proper, all, some . Avoid “definite”, “strict”, and “proper” in their
non-mathematical meanings, and be careful with “all” and “some”.

Any . Avoid the word “any” in mathematical writing: sometimes it means “all” and
sometimes it means “some”.

Intractable, infeasible . An algorithm or problem is “intractable” only if it is NP-
hard, that is, the asymptotic cost (or computational complexity) is believed to be
worse than polynomial. In the context of asymptotic cost, “infeasible” sometimes
has the same meaning as “intractable”; in the context of an optimization problem, it
might mean that the problem has no (feasible) solution.
In general writing, either “infeasible” and “intractable” is sometimes used tomean
hard to do , which is acceptable if there is no possibility of confusion.

Formula, expression, equation . A “formula”, or an “expression” is not necessarily
an “equation”; the latter involves an equality.

Equivalent, similar . Two things are “equivalent” if they are indistinguishable with
regard to some criteria. If they are not indistinguishable, they are at best “similar”.

Element, partition . An “element” is a member of a set (or list or array) and should
not be used to refer to a subpart of an expression. If a set is “partitioned” into subsets,
the subsets are disjoint and form the original set under union.

Average, mean . “Average” is used loosely to mean typical . Only use it in the formal
sense—of mean , that is, the arithmeticmean—if it is clear to the reader that the formal
sense is intended. Otherwise use “mean” or even “arithmetic mean”.

Subset, proper subset, strict subset . “Subset” should not be used to mean sub-
problem . Orderings (or partial orderings) specified in writing are assumed to be
non-strict. For example, “A is a subset of B” means that A ↆ B ; confusingly, this is

sometimes written A ↂ B . To specify A B use “A is a proper (or strict) subset

of B”.
Similar rules apply to “less than”, “greater than”, and “monotonic”.