1.4.1 Sets

The concept of a set in the mathematical sense has wide application in computer science. The notations and techniques of set theory are commonly used when describing and implementing algorithms because the abstractions associated with sets often help to clarify and simplify algorithm design.

A set is a collection of distinguishable members or elements. The members are typically drawn from some larger population known as the base type. Each member of a set is either a primitive element of the base type or is a set itself. There is no concept of duplication in a set. Each value from the base type is either in the set or not in the set. For example, a set named $\mathbf{P}$ might consist of the three integers 7, 11, and 42. In this case, $\mathbf{P}$’s members are 7, 11, and 42, and the base type is integer.

The following table shows the symbols commonly used to express sets and their relationships.

Here are some examples of this notation in use. First define two sets, $\mathbf{P}$ and $\mathbf{Q}$.

$$\mathbf{P} = \{2, 3, 5\}, \qquad \mathbf{Q} = \{5, 10\}.$$

$|\mathbf{P}| = 3$ (because $\mathbf{P}$ has three members) and $|\mathbf{Q}| = 2$ (because $\mathbf{Q}$ has two members). Both of these sets are finite in length. Other sets can be infinite, for example, the set of integers.

The union of $\mathbf{P}$ and $\mathbf{Q}$, written $\mathbf{P} \cup \mathbf{Q}$, is the set of elements in either $\mathbf{P}$ or $\mathbf{Q}$, which is {2, 3, 5, 10}. The intersection of $\mathbf{P}$ and $\mathbf{Q}$, written $\mathbf{P} \cap \mathbf{Q}$, is the set of elements that appear in both $\mathbf{P}$ and $\mathbf{Q}$, which is {5}. The set difference of $\mathbf{P}$ and $\mathbf{Q}$, written $\mathbf{P} - \mathbf{Q}$, is the set of elements that occur in $\mathbf{P}$ but not in $\mathbf{Q}$, which is {2, 3}. Note that $\mathbf{P} \cup \mathbf{Q} = \mathbf{Q} \cup \mathbf{P}$ and that $\mathbf{P} \cap \mathbf{Q} = \mathbf{Q} \cap \mathbf{P}$, but in general $\mathbf{P} - \mathbf{Q} \neq \mathbf{Q} - \mathbf{P}$. In this example, $\mathbf{Q} - \mathbf{P} = \{10\}$. Finally, the set {5, 3, 2} is indistinguishable from set $\mathbf{P}$, because sets have no concept of order. Likewise, set {2, 3, 2, 5} is also indistinguishable from $\mathbf{P}$, because sets have no concept of duplicate elements.

The set product or Cartesian product of two sets $\mathbf{P} \times \mathbf{Q}$ is a set of ordered pairs. For our example sets, the set product would be:

$$\{(2, 5),\ (2, 10),\ (3, 5),\ (3, 10),\ (5, 5),\ (5, 10)\}.$$

The powerset of a set $\mathbf{P}$ (denoted $2^\mathbf{P}$ or $\mathcal{P}(\mathbf{P})$) is the set of all possible subsets of $\mathbf{P}$. For our example set $\mathbf{P}$, the powerset would be:

$$\{ \emptyset,\ \{2\},\ \{3\},\ \{5\},\ \{2, 3\},\ \{2, 5\},\ \{3, 5\},\ \{2, 3, 5\} \}.$$

A collection of elements without a specific order, similar to a set, but allowing multiple occurrences of each element, is called a bag. A bag is also known as a multiset and an element that appears more than once is called a duplicate.

A sequence is an ordered collection of elements of the same type that may include duplicates. A sequence can for example be implemented as a list, an array, or a vector. We can access elements in a sequence using zero-based indexing, where the index 0 refers to the first element, 1 to the second, and so on. We will use square brackets $[]$ to enclose the elements of a sequence. For example, $[3, 4, 5, 4]$ is a sequence. Note that sequence $[3, 5, 4, 4]$ is distinct from sequence $[3, 4, 5, 4]$, and both are distinct from sequence $[3, 4, 5]$.

1.4.2 Relations

A binary relation $R$ over set $\mathbf{S}$ is a set of ordered pairs from $\mathbf{S}$, i.e., $R\subseteq\mathbf{S}\times\mathbf{S}$. As an example of a relation, if $\mathbf{S}$ is $\{a, b, c\}$, then

$$\{ (a, c), (b, c), (c, b) \}$$

is a relation, and

$$\{ (a, a), (a, c), (b, b), (b, c), (c, c) \}$$

is a different relation. If tuple $(x, y)$ is in relation $R$, we may use the infix notation $xRy$. We often use relations, such as the less than operator ($<$), on the natural numbers, which includes ordered pairs such as $(1, 3)$ and $(2, 23)$, but not $(3, 2)$ or $(2, 2)$. Rather than writing the relationship in terms of ordered pairs, we typically use an infix notation for such relations, writing $1<3$.

The most important properties of relations are as follows:

• $R$ is reflexive if $aRa$.
• $R$ is irreflexive if $aRa$ is never true.
• $R$ is symmetric if whenever $aRb$, then $bRa$.
• $R$ is antisymmetric if whenever $aRb$ and $bRa$, then $a = b$.
• $R$ is transitive if whenever $aRb$ and $bRc$, then $aRc$.

(Here $R$ is a binary relation over a set $\mathbf{S}$, and the condition holds for all $a, b, c \in \mathbf{S}$.)

As examples, for the natural numbers, $<$ is irreflexive (because $aRa$ is never true), antisymmetric (because there is no case where $aRb$ and $bRa$), and transitive. Relation $\leq$ is reflexive, antisymmetric, and transitive. Relation $=$ is reflexive, symmetric (and antisymmetric!), and transitive. For people, the relation “is a sibling of” is symmetric and transitive. If we define a person to be a sibling of themself, then it is reflexive; if we define a person not to be a sibling of themself, then it is irreflexive.

1.4.3 Miscellaneous notations

We now define several mathematical terms and concepts, providing a reference for future use.

Units of measure:

We will use the following notation for units of measure. “B” will be used as an abbreviation for bytes, “b” for bits, “KB” for kilobytes ($2^{10} = 1024$ bytes), “MB” for megabytes ($2^{20}$ bytes) “GB” for gigabytes ($2^{30}$ bytes) and “ms” for milliseconds (a millisecond is 1/1000 of a second). Spaces are not placed between the number and the unit abbreviation when a power of two is intended. Thus a disk drive of size 25 gigabytes (where a gigabyte is intended as $2^{30}$ bytes) will be written as “25GB”. Spaces are used when a decimal value is intended. An amount of 2000 bits would therefore be written “2 Kb” while “2Kb” represents 2048 bits. 2000 milliseconds is written as 2000 ms. Note that in this book large amounts of storage are nearly always measured in powers of two and times in powers of ten.

Permutations:

A permutation of a sequence $\mathbf{S}$ is simply the members of $\mathbf{S}$ arranged in some order. For example, a permutation of the integers 1 through $n$ would be those values arranged in some order. If the sequence contains $n$ distinct members, then there are $n!$ different permutations for the sequence. This is because there are $n$ choices for the first member in the permutation; for each choice of first member there are $n-1$ choices for the second member, and so on. Sometimes one would like to obtain a random permutation for a sequence, that is, one of the $n!$ possible permutations is selected in such a way that each permutation has equal probability of being selected.

Logic Notation:

We will occasionally make use of the notation of symbolic logic.

• $A \Rightarrow B$ means “if $A$ then $B$” – i.e., that $A$ implies $B$.
• $A \Leftrightarrow B$ means “$A$ if and only if $B$” – i.e., that $A$ and $B$ are equivalent.
• $A \vee B$ means “$A$ or $B$” – the disjunction of $A$ and $B$.
• $A \wedge B$ means “$A$ and $B$” – the conjunction of $A$ and $B$.
• $\neg A$ means “not $A$” – the negation of $A$.

Floor and ceiling:

The floor of $x$ (written $\lfloor x \rfloor$) takes real value $x$ and returns the greatest integer $\leq x$. For example, $\lfloor 3.4 \rfloor = 3$, as does $\lfloor 3.0 \rfloor$, while $\lfloor -3.4 \rfloor = -4$ and $\lfloor -3.0 \rfloor = -3$. The ceiling of $x$ (written $\lceil x \rceil$) takes real value $x$ and returns the least integer $\geq x$. For example, $\lceil 3.4 \rceil = 4$, as does $\lceil 4.0 \rceil$, while $\lceil -3.4 \rceil = \lceil -3.0 \rceil = -3$.

Modulus function:

The modulus (or mod) function returns the remainder of an integer division. Sometimes written $n \;\mathrm{mod}\; m$ in mathematical expressions, the syntax in many programming languages is $n$. From the definition of remainder, $n \;\mathrm{mod}\; m$ is the integer $r$ such that $n = qm + r$ for $q$ an integer, and $|r| < |m|$. Therefore, the result of $n \;\mathrm{mod}\; m$ must be between 0 and $m-1$ when $n$ and $m$ are positive integers. For example, $5\mathop{mod}3 = 2$, $25\mathop{mod}3 = 1$, $5\mathop{mod}7 = 5$, and $5\mathop{mod}5 = 0$.

There is more than one way to assign values to $q$ and $r$, depending on how integer division is interpreted. The most common mathematical definition computes the mod function as $n \;\mathrm{mod}\; m = n - m\lfloor n/m\rfloor$. In this case, $-3 \;\mathrm{mod}\; 5 = 2$. However, Java and C++ compilers typically use the underlying processor’s machine instruction for computing integer arithmetic. On many computers this is done by truncating the resulting fraction, meaning $n \;\mathrm{mod}\; m = n - m (\mathrm{trunc}(n/m))$. Under this definition, $-3 \;\mathrm{mod}\; 5 = -3$. Another language might do something different.

Unfortunately, for many applications this is not what the user wants or expects. For example, many hash systems will perform some computation on a record’s key value and then take the result modulo the hash table size. The expectation here would be that the result is a legal index into the hash table, not a negative number. Implementers of hash functions must either ensure that the result of the computation is always positive, or else add the hash table size to the result of the modulo function when that result is negative.

1.4.4 Logarithms

The logarithm of base $b$ for value $y$ is the power to which $b$ is raised to get $y$. Normally, this is written as $\log_b y = x$. Thus, if $\log_b y = x$ then $b^x = y$, and $b^{log_b y} = y$.

Logarithms are used frequently by programmers. Here are two typical uses.

Nearly all logarithms we use have a base of two. This is because data structures and algorithms most often divide things in half, or store codes with binary bits. Whenever you see the notation $\log n$, either $\log_2 n$ is meant or else the term is being used asymptotically and so the actual base does not matter. For logarithms using any base other than two, we will show the base explicitly.

Logarithms have the following properties, for any positive values of $m$, $n$, and $r$, and any positive integers $a$ and $b$.

1. $\log (nm) = \log n + \log m$.
2. $\log (n/m) = \log n - \log m$.
3. $\log (n^r) = r \log n$.
4. $\log_a n = \log_b n / \log_b a$.
5. $b^{\log_b n} = n$.

The first two properties state that the logarithm of two numbers multiplied (or divided) can be found by adding (or subtracting) the logarithms of the two numbers. Property (3) is simply an extension of property (1). Property (4) tells us that, for variable $n$ and any two integer constants $a$ and $b$, $\log_a n$ and $\log_b n$ differ by the constant factor $\log_b a$, regardless of the value of $n$. Most runtime analyses we use are of a type that ignores constant factors in costs. Property (4) says that such analyses need not be concerned with the base of the logarithm, because this can change the total cost only by a constant factor.

When discussing logarithms, exponents often lead to confusion. Property (3) tells us that $\log n^2 = 2 \log n$. How do we indicate the square of the logarithm (as opposed to the logarithm of $n^2$)? This could be written as $(\log n)^2$, but it is traditional to use $\log^2 n$. On the other hand, we might want to take the logarithm of the logarithm of $n$. This is written $\log \log n$.

1.4.5 Summations

Most programs contain loop constructs. When analysing running time costs for programs with loops, we need to add up the costs for each time the loop is executed. This is an example of a summation. Summations are simply the sum of costs for some function applied to a range of parameter values. Summations are typically written with the following “Sigma” notation:

$$\sum_{i=1}^{n} f(i)$$

This notation indicates that we are summing the value of $f(i)$ over some range of (integer) values. The parameter to the expression and its initial value are indicated below the $\sum$ symbol. Here, the notation $i=1$ indicates that the parameter is $i$ and that it begins with the value 1. At the top of the $\sum$ symbol is the expression $n$. This indicates the maximum value for the parameter $i$. Thus, this notation means to sum the values of $f(i)$ as $i$ ranges across the integers from 1 through $n$. This can also be written $f(1) + f(2) + \cdots + f(n-1) + f(n)$. Within a sentence, Sigma notation is typeset as $\sum_{i=1}^{n} f(i)$.

Given a summation, you often wish to replace it with an algebraic expression with the same value as the summation. This is known as a closed-form solution, and the process of replacing the summation with its closed-form solution is known as solving the summation. For example, the summation $\sum_{i=1}^{n} 1$ is simply the expression “1” summed $n$ times (remember that $i$ ranges from 1 to $n$). Because the sum of $n$ ones is $n$, the closed-form solution is $n$.

Here is a list of useful summations, along with their closed-form solutions.

$$\begin{align*} \sum_{i = 1}^{n} i &= \frac{n (n+1)}{2} \\ \sum_{i = 1}^{n} i^2 &= \frac{2 n^3 + 3 n^2 + n}{6} = \frac{n(2n + 1)(n + 1)}{6} \\ \sum_{i = 1}^{\log n} n &= n \log n \\ \sum_{i = 0}^\infty a^i &= \frac{1}{1-a} ~~~ \mbox{if} \ 0 < a < 1 \\ \sum_{i = 0}^{n} a^i &= \frac{a^{n+1} - 1}{a - 1} ~~~ \mbox{if} \ a \neq 1 \end{align*}$$

As special cases to the last summation, we have the following two:

$$\begin{align*} \sum_{i = 1}^{n} \frac{1}{2^i} &= 1 - \frac{1}{2^n} \\ \sum_{i = 0}^{n} 2^i &= 2^{n+1} - 1 \end{align*}$$

As a corollary to the previous summation:

$$\begin{align*} \sum_{i = 0}^{\log n} 2^i &= 2^{\log n + 1} - 1 = 2n - 1 \end{align*}$$

Finally:

$$\begin{align*} \sum_{i = 1}^{n} \frac{i}{2^i} &= 2 - \frac{n+2}{2^n} \end{align*}$$

1.4.6 Mathematical proof techniques

Solving any problem has two distinct parts: the investigation and the argument. Students are too used to seeing only the argument in their textbooks and lectures. But to be successful in school (and in life after school), one needs to be good at both, and to understand the differences between these two phases of the process. To solve the problem, you must investigate successfully. That means engaging the problem, and working through until you find a solution. Then, to give the answer to your client (whether that “client” be your instructor when writing answers on a homework assignment or exam, or a written report to your boss), you need to be able to make the argument in a way that gets the solution across clearly and succinctly. The argument phase involves good technical writing skills and the ability to make a clear, logical argument.

Being conversant with standard proof techniques can help you in this process. Knowing how to write a good proof helps in many ways. First, it clarifies your thought process, which in turn clarifies your explanations. Second, if you use one of the standard proof structures such as proof by contradiction or an induction proof, then both you and your reader are working from a shared understanding of that structure. That makes for less complexity to your reader to understand your proof, because the reader need not decode the structure of your argument from scratch.

This section briefly introduces three commonly used proof techniques:

1. deduction, or direct proof,

2. proof by contradiction, and

3. proof by mathematical induction.

In general, a direct proof is just a “logical explanation”. A direct proof is sometimes referred to as an argument by deduction. This is simply an argument in terms of logic.

A related proof technique is proving the contrapositive. We can prove that $P \Rightarrow Q$ by proving $(\mathrm{not}\ Q) \Rightarrow (\mathrm{not}\ P)$. This technique works because the truth table for the two logical statements are the same.

Note carefully what took place in this example. First we cast $\mathbf{S}(n)$ in terms of a smaller occurrence of the problem: $\mathbf{S}(n) = \mathbf{S}(n-1) + n$. This is important because once $\mathbf{S}(n-1)$ comes into the picture, we can use the induction hypothesis to replace $\mathbf{S}(n-1)$ with $(n-1)(n)/2$. From here, it is simple algebra to prove that $\mathbf{S}(n-1) + n$ equals the right-hand side of the original theorem.

1.4.7 Estimation

The concept of estimation might be unfamiliar to many readers. Estimation is not a mathematical technique, but rather a general engineering skill. This is sometimes known as “back of the napkin” or “back of the envelope” calculation. Both nicknames suggest that only a rough estimate is produced. It is very useful to computer scientists doing design work, because any proposed solution whose estimated resource requirements fall well outside the problem’s resource constraints can be discarded immediately, allowing time for greater analysis of more promising solutions.

Estimation techniques are a standard part of engineering curricula but are often neglected in computer science. Estimation is no substitute for rigorous, detailed analysis of a problem, but it can help to decide when a rigorous analysis is warranted: If the initial estimate indicates that the solution is unworkable, then further analysis is probably unnecessary.

Estimation can be formalised by the following three-step process:

1. Determine the major parameters that affect the problem.
2. Derive an equation that relates the parameters to the problem.
3. Select values for the parameters, and apply the equation to yield an estimated solution.

When doing estimations, a good way to reassure yourself that the estimate is reasonable is to do it in two different ways. In general, if you want to know what comes out of a system, you can either try to estimate that directly, or you can estimate what goes into the system (assuming that what goes in must later come out). If both approaches (independently) give similar answers, then this should build confidence in the estimate.

When calculating, be sure that your units match. For example, do not add feet and pounds. Verify that the result is in the correct units. Always keep in mind that the output of a calculation is only as good as its input. The more uncertain your valuation for the input parameters in Step 3, the more uncertain the output value. However, back of the envelope calculations are often meant only to get an answer within an order of magnitude, or perhaps within a factor of two. Before doing an estimate, you should decide on acceptable error bounds, such as within 25%, within a factor of two, and so forth. Once you are confident that an estimate falls within your error bounds, leave it alone! Do not try to get a more precise estimate than necessary for your purpose.

1.4.8 Random numbers

The success of randomised algorithms depends on having access to a good random number generator. While modern compilers are likely to include a random number generator that is good enough for most purposes, it is helpful to understand how they work, and to even be able to construct your own in case you don’t trust the one provided. This is easy to do.

First, let us consider what a random sequence is. From the following list, which appears to be a sequence of “random” numbers?

• 1, 1, 1, 1, 1, 1, 1, 1, 1, …
• 1, 2, 3, 4, 5, 6, 7, 8, 9, …
• 2, 7, 1, 8, 2, 8, 1, 8, 2, …

In fact, all three happen to be the beginning of a some sequence in which one could continue the pattern to generate more values (in case you do not recognise it, the third one is the initial digits of the irrational constant $e$). Viewed as a series of digits, ideally every possible sequence has equal probability of being generated (even the three sequences above). In fact, definitions of randomness generally have features such as:

• One cannot predict the next item better than by guessing.
• The series cannot be described more briefly than simply listing it out. This is the equidistribution property.

There is no such thing as a random number sequence, only “random enough” sequences. A sequence is pseudo random if no future term can be predicted in polynomial time, given all past terms.

Most computer systems use a deterministic algorithm to select pseudorandom numbers. The most commonly used approach historically is known as the Linear Congruential Method (LCM). The LCM method is quite simple. We begin by picking a seed that we will call $r_1$. Then, we can compute successive terms as follows, where $b$ and $t$ are some constant positive integers.

$$\begin{align*} r_i &= (b\cdot r_{i-1}) \;\mathrm{mod}\; t \end{align*}$$

By definition of the $\mathrm{mod}$ function, all generated numbers must be in the range 0 to $t-1$. Now, consider what happens when $r_i = r_j$ for values $i$ and $j$. Of course then $r_{i+1} = r_{j+1}$ which means that we have a repeating cycle.

Since the values coming out of the random number generator are between 0 and $t-1$, the longest cycle that we can hope for has length $t$. In fact, since $r_0 = 0$, it cannot even be quite this long. It turns out that to get a good result, it is crucial to pick good values for both $b$ and $t$. To see why, consider the following example.

If you would like to write a simple LCM random number generator of your own, an effective one can be made with the following formula:

$$\begin{align*} r_i &= (16807 \cdot r_{i-1}) \mod 2^{31} - 1 \end{align*}$$

Another approach is based on using a computer chip that generates random numbers resulting from “thermal noise” in the system. Time will tell if this approach replaces deterministic approaches.