 ...102#102.

The notation 103#103 denotes the
floor function ,
which is defined as follows:
For any real number x, 104#104 is the
greatest integer less than or equal to x.
While we are on the subject,
there is a related function,
the ceiling function ,
written 105#105.
For any real number x, 106#106 is the
smallest integer greater than or equal to x.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...121#121.

In fact, we would normally write 122#122,
but we have not yet seen the 1#1 notation which is introduced
in Chapter .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...rule

Guillaume François Antoine de L'Hôpital,
marquis de SainteMesme,
is known for his rule for computing limits which states that
if 360#360
and 361#361, then
362#362
where f'(n) and g'(n) are the
first derivatives with respect to n of
f(n) and g(n), respectively.
The rule is also effective
if 363#363
and 364#364.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...commensurate.

Functions which are commensurate
are functions which can be compared one with the other.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...439#439.

This notion of the looseness (tightness )
of an asymptotic bound is related to
but not exactly the same as that given in Definition .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...numbers.

Fibonacci numbers are named in honor of
Leonardo Pisano (Leonardo of Pisa),
the son of Bonaccio (in Latin, Filius Bonaccii),
who discovered the series in 1202.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...numbers.

These running times were measured on a Sun SPARCstation 5,
Model 85, which has an 85 MHz clock, and 32MB RAM.
The programs were compiled using the SPARCompiler C++ 4.1 compiler,
and run under the Solaris 2.3 operating system.
The times shown are user CPU times, measured in seconds.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...T.

This is not an unrealistic assumption.
In the absence of a userdefined overloading of the assignment operator,
the default behavior for assignment is to copy onebyone
the data members of the object of type T.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...NAME=2789>

The outofrange exception
is defined in the C++ standard library.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...616#616.

Actually, in C++ it is not possible to have a data type T
for which 617#617.
While C expressly forbids an empty struct declaration,
i.e., one which contains no data members (fields),
such declarations are permissible and quite common in C++ programs.
However, the draft standard specifically says that even though
an empty struct or class declaration is legal,
it shall always be the case that 618#618!
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...NAME=3616>

The domainerror exception
is defined in the C++ standard library.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...represents.

The address attribute is sometimes
called its lvalue
and the value attribute
is sometimes called is rvalue .
This terminology arises from considering the semantics of
an assignment statement such as y = x.
The meaning of such as statement is
``take the value of variable x
and store it in memory at the address of variable y.''
So, when a variable appears on the righthandside of an assignment,
we use its rvalue;
and when it appears on the lefthandsize,
we use its lvalue.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...address,

Actually, it is possible for two variables to occupy the same
memory location if a union is used.
While there are legitimate uses for unions (see Chapter ),
it is reasonable to assume here that all objects have unique addresses.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...NAME=8022> .

The word deque is usually pronounced
like ``deck'' and sometimes like ``deek.''
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...class.

I will admit that the name ListAsLinkedList is somewhat confusing.
However, it is a whole word shorter than OrderedListAsLinkedList
and that much easier to type!
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...order

A total order is a relation, say <,
defined on a set of elements, say 842#842,
with the following properties:
 For all pairs of elements 843#843,
such that 844#844, exactly one of either i<j or j<i holds.
(All elements are commensurate ).
 For all triples 845#845,
846#846.
(The relation 397#397 is transitive ).
(See also Definition ).
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...
867#867

This is the Swedish word for the number two.
Since there is no å in the ASCII character set,
for the purposes of the discussion in this chapter we will use
the ASCII code for a in its place.
However, the Swedish national variant of the ISO 646 character set
uses the code corresponding to the ASCII character ``}''.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...
867#867

I have been advised that a book with out sex will never be a best seller.
``Sex'' is the Swedish word for the number six.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...integer.

The function bitsizeof
can be implemented as the C++ preprocessor macro
#define bitsizeof(T) (8*sizeof(T))
which determines the number of bits required to represent the type T
assuming eightbit bytes.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...prime

Two numbers x and y are
relatively prime
if there is no number other than one
that divides both x and y evenly.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...type.

Typically, on 32bit computer 925#925.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...i.
 What else would it be?
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...NAME=15292> .

Isomorphic is a fancy word that means
being of identical or similar form or shape or structure.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...div.

Of course, in C++ we can overload
the builtin operators.
However, having done so we would write an infix expression
rather than the prefix one.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...Landis

Russian mathematicians G. M. Adel'sonVel'skiı and E. M. Landis
published this result in 1962.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...trees.

Obviously since BTrees are Mway trees,
the ``B'' in BTree does not stand for binary.
BTrees were invented by R. Bayer and E. McCright in 1972,
so the ``B'' either stands for balanced
or Bayertake your pick.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...HREF="page385.html#exercisepqueuesbinom">).

Isaac Newton discovered the binomial theorem in 1676
but did not publish a proof.
Leonhard Euler attempted a proof in 1774.
Karl Friedrich Gauss
produced the first correct proof in 1812.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...subsets.

Stirling numbers of the second kind
are given by the formula
1655#1655
where n>0 and 1656#1656.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...p.

Actually, the programmer must be careful when doing this kind of thing.
Because C++ cannot guarantee the order in which globals declared in
separate files are constructed,
in some circumstances it may be possible for operator new
and operator delete to be called
before the storage pool p has been initialized
by its constructor.
The solution to this is to use a technique
such as double construction [33].
Such trickery is beyond the scope of this text.
Caveat emptor.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...Log2Ceil.

We assume that there exists the function
unsigned int Log2Ceil (unsigned int n);
which computes 1782#1782.
It is possible to compute this function in constant time
using simple bit manipulations.
Most computers have instructions that make the implementation trivial.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...space.

The reader may find it instructive to compare
Program with Program and Program .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...space.

The reader may find it instructive to compare
Program with Program and Program .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...class.

The declaration of the class itself has been omitted since
it follows directly from Programs and .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...NAME=33394> .

The table is named in honor of Blaise Pascal
who published a treatise on the subject in 1653.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...number!

Prime numbers of the form 2015#2015 are known as
Mersenne primes .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...2018#2018.

For convenience, we use the notation 2019#2019
to denote 2020#2020.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...time.

In this chapter we assume that 601#601
and that 1296#1296.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...NAME=35375> .

Unfortunately, the fame of bubble sort exceeds by far its practical value.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
 ...zero.

There is also the symmetrical case in which i is always n1.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.