A natural number is any element of the set 0 1 2 3 4 … An integer is any element of the set … −4 −3 −2 −1 0 1 2 3 4 …
The word positive is often somewhat ambiguous: does it mean > 0 or ≥ 0? Something similar goes for the word negative.
In this site, a number x is considered positive if x ≥ 0 and strictly positive if x > 0. (We may occasionally use the redundant expression positive or null for emphasis.)
Similarly, a number x is negative if x ≤ 0 and strictly negative if x < 0.
A sequence is characterized by the order of its elements: there is a first element, a second element, etc., a last element. (Example: the sequence of digits of a phone number.) To specify the elements of a sequence, write them, in order, wrapped in parentheses: (a, b, c, …). If this does not cause confusion, you may omit the parentheses and commas and write simply a b c …
A set has no order.
There is no first element
and no last element.
(Example: the set of numbers in a lottery result.)
As a consequence, a set has no repeated
elements.
To specify the elements of a set,
write them, in any order,
wrapped in curly braces: {a, b, c, …}.
We shall use the notation a . . b to designate the set of integers {a, a+1, a+2, … , b}. Depending on the context, this notation can also designate the sequence (a, a+1, a+2, … , b).
Sequences are represented by arrays or by linked lists. Sets may are represented by strictly increasing arrays or strictly increasing linked lists.
A sequence
(v0,
v1,
… ,
vn−1)
is increasing
(or is in increasing order)
if
v0 ≤
v1 ≤
… ≤
vn−1 .
The sequence is strictly increasing if
we have <
in place of
≤
.
The concepts of decreasing and
strictly decreasing are defined
similarly.
Analogous definitions apply to arrays and to linked lists.
Caution:
Some books say
nondecreasing
where we say increasing
.
They also say
increasing
where we say strictly increasing
.
A permutation of a finite sequence is any sequence that has the same elements in a possibly different order. For example, 2 1 4 2 3 is a permutation of 1 2 2 3 4 . A sequence with n elements has exactly n! different permutations.
The lexicographic order between sequences of integers is defined roughly as follows: a sequence s is lexicographically smaller than a sequence t if the first element of s that differs from the corresponding element of t is smaller than that element of t.
A precise definition can be stated as follows. Given two different sequences s = (s1, s2, … , sm) and t = (t1, t2, … , tn) of integers, we say that s is lexicographically smaller than t if
Under the same conditions we say that t is lexicographically greater than s.
(See one of the exercises in chapter Enumeration algorithms.)
The lexicographic order is transitive (i.e., if s is lexicographically smaller than t and t is lexicographically smaller than u then s is lexicographically smaller than u). Moreover, the lexicographic order is total (i.e., for any two different sequences s and t, either s is lexicographically smaller than t, or s is lexicographically greater than t).
Now consider a sequence of sequences, also known as a list of sequences. We say that the list is in lexicographic order if each sequence in the list is lexicographically smaller than (or equal to) each of the subsequent sequences in the list. The following example shows a list of sequences (one sequence per line) in lexicographic order:
Lexicographic order for strings. A string is a sequence of bytes. Since each byte represents a positive integer in binary notation, the lexicographic order between strings follows from the lexicographic order between sequences of integers. (See the section Lexicographic order in chapter String manipulation.)
A list of strings is in lexicographic order if each string in the list is lexicographically smaller than (or equal to) each of the subsequent strings. In the case of ASCII strings, the lexicographic order is analogous to the order in which words appear in a dictionary (except that it puts all the uppercase letters before all the lowercase). Here is an example of a list of strings in lexicographic order:
A B A C U S A B O U T A B O V E A B S O L U T E A S H A U T H O R A U T H O R I T Y B A L D B A R B E A R
A subsequence is what is left after some terms of a sequence are deleted. More precisely, a subsequence of a sequence (a1, a2, … , an) is any sequence (b1, b2, … , bk) such that
b1 = ai1, b2 = ai2, … , bk = aik
for some sequence i1 < i2 < … < ik of indices. For example, (2, 3, 5, 8) is a subsequence of (1, 2, 3, 4, 5, 6, 7, 8) but not a subsequence of (1, 2, 3, 8, 4, 5, 6, 7). (See the Subsequence exercise in the Arrays chapter.)
Just as sequences are represented by arrays, subsequences are represented by subarrays. A subarray of an array a[1 .. n] is any array b[1 .. k] such that b[1] = a[i1], b[2] = a[i2], … , b[k] = a[ik] for some sequence i1 < i2 < … < ik of indices.
A segment
of a sequence is a continuos
subsequence.
In other words, a segment
is what is left after some of the initial terms
and some of the final terms
of the sequence are deleted.
(In some contexts, a segment is referred to as a run.)
More precisely,
a segment
of a sequence
(a1,
a2,
… ,
an)
is any sequence of the form
(ai,
ai+1,
ai+2,
… ,
ak)
where 1 ≤ i and k ≤ n.
For example,
(2, 3, 4, 5)
is a segment of
(1, 2, 3, 4, 5, 6, 7, 8).
Similarly, a segment of an array a[1 .. n] is any array of the form a[i .. k] where 1 ≤ i and k ≤ n. If i > k, the expression a[i .. k] represents the empty segment.
A prefix of a sequence is a segment that contains the first term of the sequence. A suffix of a sequence is a segment that contains the last term of the sequence.
A partition of a set X is any collection P of nonempty subsets of X endowed with the following property: every element of X belongs to one and only one of the elements of P. Each element of P is a block of the partition.
Example:
{{1,3},{2,4,7},{5},{6,8}}
is a partition of
{1,2,3,4,5,6,7,8}.
The set {6,8} is one of the blocks of the partition.
(Please do not say
the set {6,8} is a partition of {1,2,3,4,5,6,7,8}.
)
The floor of a real number x is the result of rounding x down. In other words, the floor of x is the only integer i such that
i ≤ x < i + 1 .
For example, the floor of 3.99 is 3. The floor of x is denoted by
⌊ x ⌋ .
In C, the floor of a real number is given by the function floor from the math library.
The ceiling of a real number x is the result of rounding x up. In other words, the ceiling of x is the only integer j such that
j − 1 < x ≤ j .
For example, the ceiling of 3.01 is 4. The ceiling of x is denoted by
⌈ x ⌉ .
Our logarithms are always taken in base 2. Hence, log n is a shorthand for log2 n , that is, the real number x such that 2x = n. (By the way: the correct notation is log2 n, not log 2 n, not log 2n, and not log2 n .)
Therefore, log n is essentially equal to the number of bits in the binary representation of n, i.e., approximately 3.3 times the number of digits in the decimal representation of n.
(Our notation is in conflict with the notation of the math library of C, where the function log produces the natural logarithm, that is, the logarithm in base e = 2.71828…)