...array

Row exchange is an essential part of some important mathematical algorithms, such as Gaussian Elimination. We won't study these algorithms in this course, but it is useful to remember that row exchange is something that can be important.

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

...algorithm

Strassen's algorithm is described in section 10.2.4, pages 378-380 of the Weiss book.

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

...is

Of course, it can't be faster than 15#15, since an n-by-n matrix has 16#16 elements, and each has to be visited once just to fill in the answer- but how close to 15#15 can we get?

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

...tries.

It is possible to represent duplicate keys in a trie, but the result is a more complicated data structure, whose design is left as an exercise.

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

...Patricia).

Patricia stands for ``Practical Algorithm To Retrieve Information Coded in Alphanumeric''.

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

...trie.

The Lempel-Ziv algorithm would make a fascinating topic for a final paper.

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

...sizes).

This is less and less of a worry each year; currently nearly every CPU uses 8-bit bytes, two's complement integers, and IEEE floating point.

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

...importance.

For example, multi-key search trees, where each level of the tree uses a different key.

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

...property.

In fact, preorder isn't the first one that I thought of when I first had to solve this problem myself, although I wish it had been, because it would have saved me a lot of work!

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

...sides.

We assume that the die must always come to rest on one of its faces, not balanced on an edge or a corner.

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

...tails.

From a mathematical perspective, it is incorrect to so blithely make a comparison of the cardinality of these two infinite sets. Although most people's intuition about the nature of infinity is far from correct, most people do find probability reasonably intuitive, and I appeal to that intuition here instead of embarking on a lengthy mathematical digression.

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

...population.

In some cases, such as we will explore later in the chapter, this is not even possible, no matter how kindly fate smiles upon our program- our estimates will always be rational numbers, and not all probabilities are rational.

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

...slow.

Many modern compilers implement   %   via division on machines that do not have a mod instruction, and many RISC architectures do not have mod. Therefore, it seems that the faster your machine is, the slower   %   runs relative to everything else.

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

...do.

Using a b that is smaller than the number of characters in the alphabet is possible as well, if for some reason this is desirable, but doing so does require a bit more care.

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

...complex.

It would make a wonderful (and ambitious) final project for someone to nail down the O(M) algorithm for computing the skip array.

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

...others.

Using randomly generated text and pattern strings.

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

...equality.

It would be strange if this was not the case, but language designers have been known to do strange things.

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

...standard

This shift will break many, many existing programs. Converting all of these programs will keep many, many programmers busy for some time.

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

...byte

In some computers, the smallest distinct unit of memory is not a byte. For the sake of simplicity, however, this section assumes that the smallest distinct unit of memory on the computer in question is a byte.

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