...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 gif. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...rule
Guillaume François Antoine de L'Hôpital, marquis de Sainte-Mesme, 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 gif. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...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 user-defined overloading of the assignment operator, the default behavior for assignment is to copy one-by-one 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 l-value  and the value attribute is sometimes called is r-value . 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 right-hand-side of an assignment, we use its r-value; and when it appears on the left-hand-size, we use its l-value. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...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 gif), 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:
  1. 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 ).
  2. For all triples 845#845, 846#846. (The relation 397#397 is transitive ).

(See also Definition gif). 

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...

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 eight-bit 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 32-bit 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 built-in operators. However, having done so we would write an infix expression rather than the prefix one. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...Landis
Russian mathematicians G. M. Adel'son-Vel'skiı and E. M. Landis published this result in 1962. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...trees.
Obviously since B-Trees are M-way trees, the ``B'' in B-Tree does not stand for binary. B-Trees were invented by R. Bayer and E. McCright in 1972, so the ``B'' either stands for balanced or Bayer-take your pick. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...HREF="page385.html#exercisepqueuesbinom">gif).
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 gif with Program gif and Program gif. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...space.
The reader may find it instructive to compare Program gif with Program gif and Program gif. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...class.
The declaration of the class itself has been omitted since it follows directly from Programs gif and gif. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
...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 n-1. 
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.