The Book

We next turn our attention to a way to view statements about sets as propositions with Boolean values (true or false). In lisp, true is abbreviated t, and false nil. With some help from a pair of global variables, we can be traditional and just use true and false.

VTO: a proposition is a sentence (or statement) that is either true or false. The sentence can be about anything at all (not just sets), as long as ascertaining its truth or falsity is feasible. The study called propositional logic deals with standalone and compound propositions, which are propositions composed of other propositions, standalone or themselves composite. How to compose or combine propositions to create these compounds is coming after a few exercises in model building. Do start the warmup by thinking up three examples and three non-examples of propositions. Make them pithy.

True propositions are AKA facts. A set of true propositions is called a knowledge base, which is just a database of facts. This set represents what we know about the world (or a subset of the world) or, in other words, the meaning or interpretation we attach to symbols (such as sentences — strings of words). Take a simple two-proposition world:

• It is true that snow is white.
• It is false that grass is white.

Given our propensity for abbreviation, let's assign propositional variables p and q to make it easier to manipulate this world:

• p = "snow is white"
• q = "grass is white"

p and not q represents our interpretation of this world. We could imagine a stranger world — stranger than the real one where we live — where p and q (i.e., where snow is white and so is grass) or even not p and q (where snow is green, say, and grass is white) is the real model.

VTO: a model is (roughly speaking) the meanings (interpretations) of symbols. In general, a model is all over the map, but in propositional logic, models are assignments of truth values to propositions (conveniently identified as variables). As aforementioned, truth values are Boolean values, true or false. Period. No partly true or somewhat false, nor any other kind of wishy-washiness.

Decision-making ability is an important component of any programming language. Lisp is no exception. The conditional logic decidering of one of the basic logical connectives will be revealed in the following exercise that invites you to explore the logical connectives and (∧), or (∨), xor (⊕), and not (¬). Naturally, not is not a connective in the sense of connecting two things together, but it's a logical operator nonetheless. For xor, the 'exclusive' or, use the if form to do a conditional expression.

We can compose or combine propositions to create compound propositions by applying the following rules again and again (consider this a 'grammar' for generating these propositional 'molecules' from propositional 'atoms'):

1. A proposition is a variable, that is, a single element from the set [p q r s t ...];
2. alternatively, a proposition is a proposition preceded by a not;
3. alternatively, a proposition is a proposition followed by a connective followed by a proposition.
4. A connective is a single element from the set [and or xor].

Rules 2 and 3 have a recursive flavor, so said because they refer back to themselves; that is, they define a proposition in terms of itself, and simpler versions of itself.

We actually need more syntactic structure to make sense of certain compounds. For example, building a proposition from scratch by starting with

proposition;

from thence applying rule 1 (choosing p) then rule 3 yields

p connective proposition;

from thence applying rule 4 (choosing and) yields;

p and proposition;

from thence applying rule 3 again yields

p and proposition connective proposition;

from thence applying 1 twice and 2 once yields

p and q connective not r;

from thence one more application of 4 (choosing or) yields the not-further-expandable:

p and q or not r

Which is ambiguous. Does it mean p and s where s is q or not r? Or does it mean s or not r where s is p and q? In other words, which is the right interpretation, 1 or 2?

1. p and (q or not r); associating from the right.
2. (p and q) or not r; associating from the left.

The mathematically astute reader will recognize that the parentheses are the extra syntactic sugar we need to sprinkle on to disambiguate (choose 1 or 2 (but not both)).

The next question is, does it matter? Try it both ways with the truth-value assignment of p to true, q to false, and r to true:

Replacing p, q, and r with true, false, and true, respectively, in

p and (q or not r)

yields

true and (false or not true)

Before simplifying this expression, a quick review of how these connectives work:

The simplest one first: not flips truth values — when notted (or negated — not is AKA negation) true becomes false, false becomes true. To be true, or requires at least one of the two propositions appearing on its left-hand-side (LHS) and its right-hand-side (RHS) to be true. If both of them are false, their disjunction (a fancier name for or) is false. To be true, and requires both propositions (LHS and RHS) to be true. If even one of them is false, their conjunction (a fancier name for and) is false.

Back to the task: the above expression simplifies to

true and (false or false)

from thence to

true and false

from thence to

false.

Replacing propositional variables with their values in

(p and q) or not r

yields

(true and false) or not true

which simplifies to

(true and false) or false

from thence to

false or false

and finally

false.

So they're the same. But wait! What if we try a different assignment of truth values? With all of p, q and r false, here is the evolving evaluation for 1 (p and (q or not r)):

1. false and (false or not false)
2. false and (false or true)
3. false and true
4. false

And here it is for 2 ((p and q) or not r):

1. (false and false) or not false
2. false or not false
3. false or true
4. true

So it's different — it DOES matter which form we choose. Let's tabulate all possible truth-value assignments (AKA models) for each, and see how often they're the same or not:

First, how do we generate all possible assignments? Let's use a decision tree:

       p     q     r
   / false false false
  /\ false false true
 /\/ false true  false
/  \ false true  true
\  / true  false false
 \/\ true  false true
  \/ true  true  false
   \ true  true  true

In this binary tree, each node (wherever it branches up or down) represents a decision to be made. Branching up represents a choice of false, branching down true. Going three levels (branch, twig, leaf) gives us the eight possibilities.

VTO: a tabulation of possible models (essentially picking off the leaves of the tree from top to bottom (making each leaf a row)) is called a truth table. Here's an example:

Numerically it makes sense to have, and indeed most other languages do have, 0 represent false. Lisp is an exception — 0 evaluates to non-nil (which is not nil — not false). Having 1 represent true has advantages, too, although MOL treat anything non-zero as true as well. Still, it's less typing, so we'll use it to save space — but keep in mind, the arithmetization of logic is also instructive because of how it enables certain useful encodings. Here's the same truth table in a more compact form:

Let it be. Let it go. Let it go so. Let it be so. Make it so.

Let p be prime. In lisp, something like p is called a symbol, and you can treat a symbol essentially like a variable, although it is much more than that.

Let something be something is a very mathy way of speaking. So lisp allows somethings to be other somethings by way of the keyword let.

Like God, who said let there be light, and there was light, the programmer commands and is obeyed. The keyword let binds symbols to values, fairly commanding them to stand in for values. Values evaluate to themselves. Symbols evaluate to the values they are bound to. An unbound symbol cannot be evaluated. If you try it, an error results.

Before doing some exercises, let's look at let syntactically and abstractly:

(let <frame> <body>)

The <frame> piece is a model in the form of a list of bindings. Just as we modeled truth-value assignments as, e.g., p is true and q is false, in list-of-bindings form this would be ((p true) (q false)). A binding is a two-element list (<var> <val>). Variables can be left unbound, so for example, (let ((a 1) (b 2) c) ...) is perfectly acceptable. It assumes c will get a value later, in the <body>.

The <body> is a list of forms to be evaluated — forms that use the bindings established in the frame model.

The frame list can be empty, as in:

(let () 1 2 3)
; alternatively
(let nil 1 2 3)

The value of this symbolic expression (lispers shorten this to an s-expression, or sexp for shorter) is 3, the value of the last form before the closing parenthesis.

The rule for dealing with lisp expressions is to look for lists, and when found, evaluate them. Casual observation reveals the bulk of lisp code is in fact lists, and lists of lists nested to many levels. Evaluating a list entails evaluating each of its elements, except the first, which is treated differently. For now, think of the first element as an operator that operates on the values of the rest of the elements. So (+ 1 2 3 4) adds together 1 (the value of 1 — numbers self-evaluate), 2, 3 and 4 to produce 10. Note the economy of this prefix notation, as it's called: only one mention of the '+' sign is needed. The more familiar infix notation requires redundant '+' signs, as in 1+2+3+4.

CSP a description of set operations, union, intersection, difference, symmetric difference, subset-of, superset-of, disjoint, mutually or not; De Morgan's laws for logic and sets.

Let's leave 'let' for now, and look at lisp functions via the defun special form.

(defun <parameter-list> [optional documentation string] <body>)

Examples of /def/ining /fun/ctions via defun are forthcoming. First note that this language feature is convenient, but not strictly necessary, because any function definition and call can be replaced with a let form, where the frame bindings are from the caller's environment.

For example, the function list-some-computations-on, defined and invoked (another way to say called) like this:

(defun list-some-computations-on (a b c d)
  "We've seen this one before."
  (list (+ a b) (/ d b) (- d a) (* c d)))

(list-some-computations-on 1 2 3 4)

This definition/call has exactly the same effect as:

(let ((a 1) (b 2) (c 3) (d 4))
  (list (+ a b) (/ d b) (- d a) (* c d)))

Of course, any procedural (or object-oriented) programmer knows why the first way is preferable. Imagine the redundant code that would result from this sequence of calls if expanded as above:

(list-some-computations-on 1 2 3 4)
(list-some-computations-on 5 6 7 8)
; ...
(list-some-computations-on 97 98 99 100)

Functions encapsulate code modules (pieces). Encapsulation enables modularization. The modules we define as functions become part of our vocabulary, and a new module is like a new word we can use instead of saying what is meant by that word (i.e., its definition) all the time.

But stripped down to its core, a function is just an object that takes objects and gives other objects. Speaking completely generally, these are objects in the 'thing' sense of the word, not instances of classes as might be assumed if object-oriented programming were the context. Are there any restrictions on what objects can be the inputs to a function (what it takes) and what objects can be the outputs of a function (what it gives)? Think about and answer this question before looking at the endnote.

VTO: again, a function is simply an object, a machine if you will, that produces outputs for inputs. But simply amazingly, there is a plethora of terms describing various kinds and attributes of functions that have been designed and pressed into mathematical and computer scientific service over the years:

• domain is the term for the set of all possible inputs for a function. (So functions depend on sets for their complete and rigorous definitions.)
• codomain is the set of all possible outputs for a function.
• range is the set of all actual outputs for a function (may be different — smaller — than the codomain).
• onto describes a function whose range is the same as its codomain (that is, an onto function produces (for the right inputs) all possible outputs).
• surjective is a synonym for onto.
• surjection is a noun naming a surjective function.
• one-to-one describes a function each of whose outputs is generated by only one input.
• injective is a synonym for one-to-one.
• injection is a noun naming an injective function.
• bijective describes a function that is both one-to-one and onto.
• bijection is a noun naming a bijective function.
• recursive describes a function that calls itself. Yes, you read that right.
• arguments are the inputs to a function (argument "vector" (argv)).
• arity is short for the number of input arguments a function has (argument "count" (argc)).
• k-ary function — a function with k inputs.
• unary – binary – ternary — functions with 1, 2 or 3 arguments, respectively.
• infix notation describes a binary function that is marked as a symbol between its two arguments (rather than before).
• prefix notation describes a k-ary function that is marked as a symbol (such as a word (like list)) before its arguments, frequently having parentheses surrounding the arguments, but sometimes (like in lisp) having parentheses surrounding symbol AND arguments.
• postfix notation describes a function that is marked as a symbol after its arguments. Way less common.
• image describes the output of a function applied to some input (called the pre-image of the output). (The image of 2 under the 'square' function is 4. The square function's pre-image of 4 is 2.)

Since the square function (a unary, or arity 1 function) is a handy one to have around, we defun it next:

(defun square (number)
  "Squaring is multiplying a number by itself,
   AKA raising the number to the power of 2."
  (* number number))

There are many one-liners just itching to be defuned (documentation string (doc-string for short) deliberately omitted):

(defun times-2 (n)
  (* 2 n))

(defun times-3 (n)
  (* 3 n))

This one deserves a doc-string, if only to remind us what the 'x' abbreviates:

(defun xor (p q)
  "Exclusive or."
  (if p (not q) q))

(defun not-with-0-1 (p)
  (- 1 p))

As written, all of these one-liner functions are problematic; take, for example, not-with-0-1. Its domain is exactly the set [0 1], and exactly that set is its codomain (and range) too. Or that's what they should be. Restricting callers of this function to only pass 0 or 1 is a non-trivial task, but the function itself can help by testing its argument and balking if given something besides 0 or 1. Balking can mean many things — throwing an exception being the most extreme.

We've been viewing a function a certain way, mostly with a programming bias, but keep in mind that functions can be viewed in many other ways as well. The fact that functions have multiple representations is a consequence of how useful each representation has proven to be in its own sphere and element. A function is representable by each of the following:

• assignment
• association
• mapping (or map)
• machine
• process
• rule
• formula
• table
• graph

and, of course,

• code

CSP examples and exercises.

The bottom line: mathematical functions are useful abstractions of the process of transformation. Computer scientific functions follow suit.

Let's now define a sequence and distinguish it from a set. The difference is that a sequence is an ordered collection. So a list or a vector is just a sequence, and truth be told, a sequence is really just a special kind of function.

VTO: a finite sequence of elements of a set S is a function from the set {1, 2, 3, ..., n} to S — the number n is the length of the string. Alternatively, the domain of the sequence function can be {0, 1, 2, ..., n - 1} (or with n concretized as 10, [0 1 2 3 4 5 6 7 8 9] in lisp vector style). The sequence length is still n (ten) in this case.

Generically, a_n denotes the image of the (nonnegative) integer n, AKA the n^th term of the sequence. An infinite sequence of elements of S is a function from {1, 2, 3, …} to S. Shorthand notation for the entire sequence is {a_n}. Again, the domain can be either Z⁺ or N.

For example, {a_n}, where each term a_n is just three times n (i.e., a(n) = 3n, or in lisp, (defun a (n) (times-3 n))), is a sequence whose list of terms (generically a₁, a₂, a₃, a₄, …) would be 3, 6, 9, 12, … (all the multiples of three — infinite in number).

Another term for a finite sequence is a string, that venerable and versatile data structure available in almost all programming languages. Strings are always finite — if it's an infinite sequence, it is most emphatically not a string.

With lisp symbols there must automatically be support for strings. Every symbol has a unique string naming it, and everywhere the same symbol is used, the same string name (retrieved via the function symbol-name) comes attached.

Functions that return false (nil) or true (t — actually anything that evaluates to non nil) are ubiquitous. So much so that they have a special name — predicate.

VTO: a predicate is a function whose codomain is the set [true false], and is AKA a property. The domain of a predicate can be any conceivable set. We could also call these functions deciders (short for decision-makers) that ascertain whether or not a given object has a specified property.

"Applying the plus function to sequences yields summations." Let's unpack that sentence. To apply a function to a sequence we need that function's symbol, the sequence as a list, and the function apply. Here's where we start to see the power of the functional programming paradigm.

CSP applying '+ (yes, no closing quote is correct) to sequences to get summations.

Continuing to mind our p's and q's, it's time to talk predicates and quantifiers.

In our neverending quest for succinctness, we desire a shorter way to say, for example, all the colors of the rainbow are beautiful. Shorter, that is, than just listing all true propositions, with B for Beautiful as predicate:

• B(red)
• B(orange)
• B(yellow)
• B(green)
• B(blue)
• B(indigo)
• B(violet)

We know all the colors in the domain, so why not just say, for all the colors in the rainbow, each is beautiful. Or even more succinctly, every rainbow color is beautiful. These quantifiers "all" and "every" apply to the whole of our universe of discourse.

VTO: a universe of discourse (AKA domain of discourse) is the set of all things we've set forth to talk about, i.e., all things under consideration. It must be specified (unless the real universe is the universe of discourse) to make sense of propositions involving predicates. The universal quantifier ∀ says something is true for all members of this universal set, no exceptions.

Saying something like

• ∀ x B(x)

rather than

• B(red) ∧ B(orange) ∧ B(yellow) ∧ B(green) ∧ B(blue) ∧ B(indigo) ∧ B(violet)

(because, of course, each and every one is true) is much shorter, which is especially important when the domain is large (or infinite).

• ∀ x Even(x)

is true when x comes from [2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 42], but false when the domain is [2 4 6 8 10 12 14 16 18 20 22 24 26 28 30 32 34 36 38 40 41], instead. And indeed

• ∀ x Even(x)

is infinitely shorter than a conjunction of unquantified propositions Even(2) ∧ Even(4) ∧ …, one for each member of the set of even integers.

Another easy example:

Let P = "is a ball".

So P(x) means x is a ball. Is P(x) true?

We can't say. A predicate (or more precisely, a propositional function (or formula) consisting of a predicate and some variable(s)) is not a proposition.

∃ x P(x)

Meaning: There exists an x such that x is a ball.

∃ is the Existential quantifier.

Is this true?

It depends.

What is the Universe of Discourse?

Let it be the set [markers erasers whiteboards] (in a classroom, for example).

¬ ∃ x P(x) means "There does not exist an x such that x is a ball".

(True, in this Universe.)

∃ x ¬ P(x) means "There exists an x such that x is not a ball".

This is the same as saying "Something is not a ball."

But it's not the same as saying "Everything is not a ball."

∀ x ¬ P(x)

Meaning: For every x, it is not the case that x is a ball.

Remember, ∀ is the Universal quantifier.

¬ ∀ x P(x) means "Not everything is a ball".

Let R(y) = "y is red".

∀ y R(y) means "Everything is red".

¬ ∀ y R(y) means "Not everything is red".

∃ y ¬ R(y) means "There is some non-red thing."

∃ y R(y) means "There is something that is red" or "There exists some red thing".

Let's examine a "Sillygism":

Very wrong! Better as a "Syllogism":

That's right. In general:

• G(x) = x is good.
• O(x) = x is object-oriented.

A Well-Known Syllogism:

A Slightly Less Well-Known Syllogism:

• S(x) = x is a student of Discrete Mathematics.
• T(x) = x has taken Data Structures.

∀ x (S(x) → T(x))

Or more succinctly:

∀ x T(x)

(if the Domain of Discourse is decided on in advance to be "students in this class").

The Gospel as Domain of Discourse is an abundantly fruitful mindscape.

In his teachings, Paul the apostle uses conditionals (and their variations) and syllogistic reasoning a lot. For example: I Corinthians 15:29

Else what shall they do which are baptized for the dead, if the dead rise not at all? why are they then baptized for the dead?

All things that are done by people are done for a reason (i.e., they have a point). Baptisms for the dead are done by people. Therefore, baptisms for the dead have a point. If the dead rise not (i.e., there is no resurrection) then there would be no point to do baptisms for them. Thus, if baptisms for the dead have a point, then there is a resurrection of the dead. Therefore, the resurrection of the dead is real.

As a rule of thumb, universal quantifiers are followed by implications. For example, the symbolic form of "Every prime > 2 is odd" is

∀ x ((Prime(x) ∧ GreaterThanTwo(x)) → Odd(x))

or

∀ x > 2 (Prime(x) → Odd(x))

but not

∀ x > 2 (Prime(x) ∧ Odd(x)).

As a rule of thumb, existential quantifiers are followed by conjunctions. For example, the symbolic form of "There exists an even number that is prime" is

∃ x (Even(x) ∧ Prime(x)),

but not

∃ x (Even(x) → Prime(x)).

Remember to change the quantifier when negating a quantified proposition.

Take another example, the negation of the statement that "some cats like liver". It is not the statement that "some cats do not like liver"; it is that "no cats like liver," or that "all cats dislike liver." So with "cats" as the Universe of Discourse and letting L = "likes liver";

∃ x L(x) says "some cats like liver."

¬ ∃ x L(x) ≡ ∀ x ¬ L(x)

"All cats dislike liver", or "No cats like liver".

¬ ∀ x L(x)

"It is not the case that all cats like liver", or "Not all cats like liver".

¬ ∀ x ¬ L(x)

"Not all cats dislike liver", or "Some cats like liver".

There are two important concepts to keep in mind when dealing with predicates and quantifiers. To turn a first-order logic formula into a proposition, variables must be bound either by

• assigning them a value, or
• quantifying them.

What means Freedom Versus Bondage?

In formulas, variables can be free or bound. Bondage means being under the control of a particular quantifier. If φ is some Boolean formula and x is a variable in φ, then in both ∀ x (φ) and ∃ x (φ) the variable x is bound — free describes a variable in φ that is not so quantified.

As in propositional logic (AKA the propositional (or predicate) calculus), some predicate formulas are true, others false. It really depends on how its predicates and functions are interpreted. But if a formula has any free variables, in general its truth is indeterminable under any interpretation.

For example, let the symbol 'L' be interpreted as less-than. Whether the formula

∀ x L(x, y)

is true or not is indeterminable. But inserting an ∃ y right after the ∀ x makes it true. Yes, we just nested one quantifier inside another. And importantly, when nesting different-flavored quantifiers, the order in which they appear matters (but not if they are the same flavor).

Using a predicate, e.g., if (Q x y) is "x + y = x - y"

∀ x ∀ y (Q x y) is false;

∀ x ∃ y (Q x y) is true;

∃ x ∀ y (Q x y) is false; and

∃ x ∃ y (Q x y) is true.

How have mathematicians generalized functions? They defined relations. With one big difference, relations are essentially functions. The difference is, there is no "fan-out" constraint on relations as there is on functions. What that means is that an element of the domain of a relation can map to any number of (zero, one or more) elements in its codomain.

VTO: A binary relation R from a set A to a set B is a subset: R ⊆ A × B. A binary relation R on a set A (a self relation) is a subset of A × A, or a relation from A to A (from the set to itself).

VTO: A × B, the Cartesian product (or just product) of set A with set B is the set of all ordered pairs (a b) where a ∈ A and b ∈ B. This generalizes to n sets in the obvious way.

For an A × B example:

• A = [a b c]
• B = [1 2 3]
• R = [(a 1) (a 2) (b 2) (b 3) (c 3)]

For a self relation example:

• A = [a b c]
• R = [(a a) (a b) (a c)]

VTO: extravaganza of special properties of binary relations — given:

• A Universe U
• A binary relation R on a subset of U
• A shorthand notation xRy for "x is related to y" — shorter than saying "the pair (x y) is in the relation R" (in symbols, (x y) ∈ R), and shorter too than "x is related to y (under the relation R)". Since "(under the relation R)" is the assumed context, choose succinctness.

R is reflexive iff ∀ x [x ∈ U → xRx].

If U = ∅ then the implication is vacuously true — so the void relation on a void Universe is reflexive. Reflect on that. If U is not void, then to be a reflexive relation, all elements in the subset of U must be present.

R is symmetric iff ∀ x ∀ y [xRy → yRx].

R is antisymmetric iff ∀ x ∀ y [xRy ∧ yRx → x = y].

From this definition, using logic, you should be able to show that if xRy and x ≠ y then it is false that yRx.

R is transitive iff ∀ x ∀ y ∀ z [xRy ∧ yRz → xRz].

CSP naturally, binary relations readily generalize to n-ary relations.

CSP a very brief treatment of equivalence relations.

To end this foray into all things relational, it is illuminating to investigate how mathematicians think and make sense of the world. However, this investigation will be limited for now to one mathematician in particular — Roger Penrose.

So this is how one world-class mathematician (who is also a mathematical physicist) thinks. In this excerpt from his book The Large, the Small and the Human Mind, with abundant intellectual humility, Penrose writes:

What is consciousness?

Well, I don't know how to define it.

I think this is not the moment to attempt to define consciousness, since we do not know what it is. I believe that it is a physically accessible concept; yet, to define it would probably be to define the wrong thing. I am, however, going to describe it, to some degree. It seems to me that there are at least two different aspects to consciousness. On the one hand, there are passive manifestations of consciousness, which involve awareness. I use this category to include things like perceptions of colour, of harmonies, the use of memory, and so on. On the other hand, there are its active manifestations, which involve concepts like free will and the carrying out of actions under our free will. The use of such terms reflects different aspects of our consciousness.

I shall concentrate here mainly on something else which involves consciousness in an essential way. It is different from both passive and active aspects of consciousness, and perhaps is something somewhere in between. I refer to the use of the term understanding, or perhaps insight, which is often a better word. I am not going to define these terms either — I don't know what they mean. There are two other words I do not understand — awareness and intelligence. Well, why am I talking about things when I do not know what they really mean? It is probably because I am a mathematician and mathematicians do not mind so much about that sort of thing.

They do not need precise definitions of the things they are talking about, provided they can say something about the connections between them.

The first key point here is that it seems to me that intelligence is something which requires understanding. To use the term intelligence in a context in which we deny that any understanding is present seems to me to be unreasonable. Likewise, understanding without any awareness is also a bit of nonsense. Understanding requires some sort of awareness. That is the second key point. So, that means that intelligence requires awareness. Although I am not defining any of these terms, it seems to me to be reasonable to insist upon these relations between them.

Counting involves applying logic and some general principles to find the number of ways some choice can be made, some task can be done, or some event can happen. Counting ways of combining abstract or concrete objects from given sets they belong to is the goal.

VTO:

The Addition Principle (AKA the Sum Rule): faced with a task to select just one member from each set in a collection of two or more sets, the number of ways to make the selection is the sum of the sizes of the sets, provided the sets have no members in common.

Example: The number of ways to choose one vowel or one consonant from the alphabet is 5 + 21 = 26. It should not be surprising that this is the same as the number of ways to choose one letter from the whole alphabet. The Addition Principle involves an either-or choice, where the choices are mutually exclusive.

VTO:

The Multiplication Principle (AKA the Product Rule): faced with a task to select one member from one set, and one member from another set, and (continue with arbitrarily many sets) …, the number of ways to do so is the product of the sizes of the sets. Here again it is usually stipulated that the sets are disjoint — meaning they have no members in common.

Example: The number of ways to choose one vowel and one consonant from the alphabet is \(5 \cdot 21 = 105\). The Multiplication Principle involves a both-and choice.

In sum, adding is like or-ing, and multiplying is like and-ing, to liken '+' to ∨ and '*' to ∧.

Mixing these two principles in certain ways leads to basic counting techniques applicable to many many counting tasks. The hard part of the solution to any counting problem is choosing the appropriate model and technique. After that, applying the appropriate technique (formula) is easy.

VTO:

A permutation is an arrangement, where order matters (just like with nested quantifiers).

A combination is a subset, where order matters not, like with sets in general.

So whether order matters or not is one dimension of a counting problem, with another dimension being whether or not repetition of elements is allowed. Generally speaking these considerations are germane to either permutations or combinations, but there are subtle variations of permunations and combitations to take into account as well.

To wit, given a set of n objects, say you want to select r of them. After choosing one object from the set —

• you can either put it back — called selection with replacement (or allowing repetition)
• or not — called selection without replacement (or disallowing repetition)

Choosing the appropriate technique requires answering the two questions:

1. Does the order of the selected objects matter or not?
2. Is the selection with or without replacement (repetition)?

In general, how many different possible sequences (arrangements) of objects there are depends on the size (length) of the sequence. Selection without replacement of r objects from a set of n objects naturally constrains r to be at most n. If more than one object is selected (\(r \ge 2\)), two different orderings or arrangements of the objects constitute different permutations. Thus it is:

1. Choose the first object n ways, and
2. Choose the second object \((n - 1)\) ways (when selection is without replacement, there is one fewer object to choose from) and
3. Choose the third object \((n - 2)\) ways (again without replacement,) …

Finally choose the \(r^{th}\) object \((n - r + 1)\) ways.

By the Multiplication Principle, the number of r-permutations of n things, or said another way, the number of permutations of n things taken r at a time is

\(P(n, r) = n(n - 1)(n - 2) \cdots (n - r + 1) = n!/(n - r)!\)

If selection is without replacement but order does not matter, this is the same as selecting subsets of size r from a set of size n. Again, \(0 \le r \le n\). The secret is to divide out the number of arrangements or permutations of the r objects from the set of permutations of n objects taken r at a time. Since each r-combination can be arranged \(r!\) ways, we have \(r!\) permutations for each r-combination. So the number of r-combinations of n things, or, the number of combinations of n things taken r at a time is

\(C(n, r) = P(n, r)/P(r, r) = \frac{n!}{(n - r)! r!}\)

Example: How many ways can we choose a three-letter subset of the nine letters ABCDELMNO?

We have selection without replacement, and because we want a subset (not a sequence) the order does not matter — CDE = CED = DCE = DEC = ECD = EDC — they're all the same. So n = 9 and r = 3:

\(C(9, 3) = \frac{9!}{(9 - 3)! 3!} = \frac{9!}{6!3!} = \frac{362880}{720 \cdot 6} = 84\)

Basic Probability Theory

Taking a frequentist position is the usual way to begin exploring the vast space of BPT.

VTO:

A Probability Space is a finite set of points, each of which represents one possible outcome of an experiment. This is the discrete definition, as opposed to the continuous one with infinite points.

• Each point x is associated with a real number between 0 and 1 called the probability of x.
• The sum of all the points' probabilities \(= 1\).
• Given n points, if all are equally likely (a typical assumption) then \(1/n\) is the probability of each point.

Example: What are the possible outcomes of throwing a single fair die?

[1 2 3 4 5 6] is the probability space of outcomes as a lisp vector.

VTO:

An Event is a subset of the points in a probability space.

• P(E) (or Pr(E), or sometimes even p(E)) denotes the probability of the event E.
• If the points are equally likely, then P(E) is the sum of the points in E divided by the sum of the points in the entire probability space.

In the (fair) die throwing example, each number 1-6 is equally likely, so 1/6 is the probability of each number.

Example: What are the possible outcomes of flipping two fair coins?

• Probability Space: 4 outcomes (1/4 probability of each outcome).
• Event: seeing a head (H) and a tail (T) — the middle two of the four possibilities:
  • HH
  • HT
  • TH
  • TT

There are two points in the event, so 2/4 or 1/2 is the event's probability.

Ramp Up to Four

When flipping four coins is the experiment, the probability space quadruples:

• Probability Space: 16 outcomes, each having 1/16 probability.

Double Previous Event

• Event: seeing two heads and two tails.

  • HHHH
  • HHHT
  • HHTH
  • HHTT
  • HTHH
  • HTHT
  • HTTH
  • HTTT
  • THHH
  • THHT
  • THTH
  • THTT
  • TTHH
  • TTHT
  • TTTH
  • TTTT

  With 6 points in it (can you pick them out?) 6/16 or 3/8 is the probability of this event.

Til's aside, we fire our opening salvo into "mathmagic land" by way of distinguishing Elementary Number Theory from Advanced (or Analytic) Number Theory (ANT)). ANT uses the techniques of calculus to analyze whole numbers, whereas ENT uses only arithmetic and algebra. What more primordial concept to begin with than those multiplicative building blocks, the atoms of numbers, primes. Let's examine several ways to say the same thing:

VTO: a prime is a number (integer) greater than 1 that is divisible only by 1 and itself.

• A prime is a positive integer > 1 with exactly 2 divisors (those being 1 and itself).
• A positive integer > 1 that is not prime is called composite.
• In first-order logic, prime(n) ↔ ∀ x ∀ y [(x > 1 ∧ y > 1) → xy ≠ n].
• A composite is a positive integer with 3 or more divisors (because 3 is the first number greater than 2, and a number cannot have fewer than two divisors).
• 1 is neither prime nor composite — call it unit.
• 2 is the only even prime: ∃ ! n [even(n) ∧ prime(n)]. The "∃ !" construct is short for "there exists a unique" or "there exists one and only one".

What's so important about primes?

The Fundamental Theorem of Arithmetic, that's what. The FTA says that every positive integer can be written as the product of prime numbers in essentially one way. (So, 2 × 2 × 2 × 3 × 5 × 7 = 840 = 7 × 5 × 3 × 2 × 2 × 2 is two ways in one — the order of the factors doesn't matter.)

Sometimes uniqueness is guaranteed by phrasing it as "every integer greater than 1 can be written uniquely as a prime or as the product of two or more primes where the prime factors are written in order of nondecreasing size". But what about 1? The first statement didn't exclude it, why did the second?

Determining if a given integer is prime is a key component to modern cryptology — and crucial to the success of the enterprise of cryptology is the difficulty of factoring large integers into their prime factors.

More prime lore can be perused and pursued by the interested reader, but here's a playful smattering:

1. What's the smallest three-digit number that remains prime no matter how its digits are shuffled?
2. Why are the primes 2, 5, 71, 369119, and 415074643 so special?
3. Cicadas of the genus Magicada appear once every 7, 13, or 17 years; whether it's a coincidence or not that these are prime numbers is unknown.
4. Sherk's conjecture. The n^th prime, if n is even, can be represented by the addition and subtraction of 1 with all the smaller primes. For example, 13 = 1 + 2 - 3 - 5 + 7 + 11.
5. You look up one on your own so sexy can be 6 (because the Latin for six is sex).
6. Sexy primes are such that n and n + 6 are both prime. The first few such pairs are 5-11, 11-17, and 13-19.

There are many more prime puzzles for our pondering pleasure provided also courtesy David Wells. A random sample will suffice for now.

Is there a prime between n and 2n for every integer n > 1? Yes, provably so.

Is there a prime between n² and (n + 1)² for every n > 0? No one knows.

Many primes are of the form n² + 1 (e.g., 2, 5, 17, 37, 101, …). Are there a finite or infinite number of primes of this form? No one knows.

Is there an even number greater than 2 that is not the sum of two primes? No one knows. (That there is not is Goldbach's Conjecture.)

Is there a polynomial with integer coefficients (e.g., n² - n + 41) that takes on only prime values at the integers? The next exercise explores this question.

One very special kind of prime is the so-called Mersenne prime, which is one of the form 2^p - 1 where p is prime. Here are a few examples:

• 2² - 1 = 3
• 2³ - 1 = 7
• 2⁵ - 1 = 31
• 2⁷ - 1 = 127
• 2¹¹ - 1 = 2047 = 23 × 89 — ∴ not prime.
• …
• 2³¹ - 1 = 2147483647 (prime or not? How do you tell, easily?)
• …

The Great Internet Mersenne Prime Search (GIMPS) can be googled to examine the 48^th known Mersenne prime, a number with over 17 million digits (do not even THINK about looking at them all).

How many primes are there up to a given number n? The Prime Number Theorem reveals in a sense how the primes are distributed among the composites. But how does one define a function that measures the distribution of prime numbers?

VTO: Define the function π(n) as the number of primes not exceeding (less than or equal to) the number n. Check it out:

This seems to show that \(\pi(n) \approx \frac{n}{\log n}\).

More formally, \(\lim_{n \rightarrow \infty} \frac{\pi(n)}{(n\ / \log n)} = 1\).

The discovery of [this theorem] can be traced as far back as Gauss, at age fifteen (around 1792), but the rigorous mathematical proof dates from 1896 and the independent work of C. de la Vallée Poussin and Jacques Hadamard. Here is order extracted from confusion, providing a moral lesson on how individual eccentricities can exist side by side with law and order.

— from The Mathematical Experience by Philip J. Davis and Reuben Hersh.

So \(n\ / \log n\) is a fairly simple approximation for \(\pi(n)\), but it is not especially close. Much closer is an approximation that uses the renowned Riemann zeta function:

\(\zeta(z) = 1 + \frac{1}{2^z} + \frac{1}{3^z} + \frac{1}{4^z} + \cdots\)

\(R(n) = 1 + \sum_{k = 1}^{\infty} \frac{1}{k\zeta(k + 1)} \frac{(\log n)^k}{k!}\)

Let's see how much better R(n) approximates π(n):

There is an astounding proof that there exist arbitrarily long sequences of highly composite consecutive integers! (That means having as many prime factors as we want.) In other more precise words:

Let r and n be positive integers. Then there exist r consecutive numbers, each divisible by at least n distinct primes.

Actually, we would need a little more knowledge before looking at the proof of this amazing (if you think about it) theorem. But as persistent investigation will reveal, what this proof demonstrates (like others) is that these multiplicative building blocks called the prime numbers have a gamut of surprises.

Concepts known to ancient Greek mathematicians and no doubt before then too, Greatest Common Divisors (GCD) and Least Common Multiples (LCM) have an interesting interplay.

VTO: In lisp style, the Greatest Common Divisor (gcd a b) is the largest integer that divides both a and b, and its counterpart, the Least Common Multiple (lcm a b), is the smallest positive integer that is divisible by both a and b. Integers whose gcd is 1 are called coprime (or relatively prime), while pairwise coprime (or pairwise relatively prime) describes a set of integers every pair of which is coprime.

Six more topics and then we'll be ready to practice all this number theory:

1. Alternate Base Representation
2. The Division Theorem
3. Modular Arithmetic
4. Modular Multiplicative Inverse
5. Modular Exponentiation
6. Euclidean GCD, plain versus extended

Infinite Representational Fluency. Sounds crazy, no? But representations of integers are endless, because the choice of base to use is infinite.

Alternate Base Number Representation

n = (a_k a_k-1 … a₁ a₀)_b

And so forth, ad infinitum.

Algorithm for Alternate Base Representations

Repeat the three steps until zero appears on the left side of the equation

n = … + a₆ b⁶ + a₅ b⁵ + a₄ b⁴ + a₃ b³ + a₂ b² + a₁ b¹ + a₀ b⁰.

1. The right-most a_i is the remainder of the division by b.
2. Subtract this remainder from n.
3. Divide both sides of the equation by b.

Each iteration yields one a_i coefficient. Simple algebra guarantees the correctness of this algorithm.

For example, take n =97 and b = 3.

CSP The Division Theorem

CSP Modular Arithmetic

CSP Modular Multiplicative Inverse (MMI)

Modular Exponentiation: as powerful as simple as algorithms go.

Say we want to compute, for example, 893²⁷⁵³%4721. (Why we would want to do that is a mystery, but let it go for now.)

Doing this the straightforward way — raising 893 to the power 2753 and then reducing that huge number modulo 4721 — is difficult and slow to do by hand. An easy, fast way to do it (by hand and even faster by computer) first expands the exponent in base 2:

2753 = 101011000001₂ = 1 + 2⁶ + 2⁷ + 2⁹ + 2¹¹ = 1 + 64 + 128 + 512 + 2048

In this table of powers of 2 powers of 893, all instances of ≡ should technically be ≡₄₇₂₁, as all intermediate values are reduced modulo 4721:

We can then exploit this table of powers of 893 to quickly compute 893²⁷⁵³%4721:

Euclidean GCD Algorithm

one for the book!

Euclid's famous algorithm to find the GCD of two numbers (positive integers) goes like this. Divide the larger number by the smaller, replace the larger by the smaller and the smaller by the remainder of this division, and repeat this process until the remainder is 0. At that point, the smaller number is the greatest common divisor.

CSP the Extended Euclidean GCD algorithm.

The mystery puzzle (exercise) should throw some light on the table just seen.

We have been investigating a modular arithmetic scenario known to the first century Chinese and probably before that too. But the name has stuck to them: the Chinese Remainder Theorem. In a nutshell:

Given the remainders from dividing an integer n by an arbitrary set of divisors, the remainder when n is divided by the least common multiple of those divisors is uniquely determinable.

If the divisors are pairwise coprime, their LCM is their product, which is slightly easier to compute, which is why the CRT is usually presented in this more restrictive form (less arbitrary). A proof by construction is typical — show how to find the unique solution — and prove the construction correct.

Here's an example of this method using the system Til had Abu and Ila solve:

So x = 4 × 143 × -2 + 2 × 91 × 4 + 9 × 77 × -1
= 4 × -286 + 2 × 364 + 9 × -77
= -1144 + 728 + -693
= -1109

Now add 1001 twice to get 893. Why 1001? Why twice?

Because we want TUMMI, so it must be a number between 0 and 1001 (actually 1000).

This construction works because of the following facts:

If you've studied any linear algebra, and have solved a system of simultaneous equations using a method like Gaussian Elimination, the 0-1 matrix embedded above should ring a bell.

There are two main applications of the CRT — computer arithmetic with large numbers, and the RSA Cryptosystem. Both are topics worth exploring.

Applications

We now turn our attention to two tree applications whose beauty and utility give them superstar status:

1. fast searching
2. data compression

In searching for an item in a list of orderable items, there is a slow (less efficient) way and a fast (more efficient) way. The less efficient way is linear search — or sequential search — in which the searched-for item (called a key) is compared with each item in the list (or array/vector — indeed any sequence type) in a linear left-to-right front-to-back order. The items in the list can be in any order, but orderable items are ones that can be sorted. First putting them in sort order (typically, ascending — from "smallest" to "largest") leads to the more efficient way, called binary search. The non-tree binary search algorithm normally uses an indexable array of data. We'll skip taking a closer look at that and just focus on the tree version.

Key comparisons are usually three-way, but it takes a nested if to discern:

1. key1 < key2
2. key1 = key2
3. key1 > key2

as in the following example, which illustrates orderable numbers as keys:

(let ((items (list 1 2 3 4))
      (key 3))
  (loop for item in items
        collect (if (< key item) "<" (if (= key item) "=" ">")))) ; evaluates to: (">" ">" "=" "<")

The same code in more functional style:

(let ((items (list 1 2 3 4))
      (key 3))
  (mapcar (lambda (item)
            (if (< key item) "<" (if (= key item) "=" ">"))) items)) ; also evaluates to: (">" ">" "=" "<")

In binary search, after each step the search time is cut in half, so a list of size 16 is reduced to a list of size 1 in 4 steps (counting arrows in \(16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1\)). A size-one list is easy to search, just check whether or not its single element compares as equal to the search key.

A binary search tree (BST) is a binary tree with a key at each node such that all keys in the node's left descendants (i.e., subtree) are less than the node's key, and all keys in the node's right descendants (i.e., subtree) are greater than the node's key. And of course, all keys at the node itself (all one of them) are equal to that one key. Note that this application of trees requires 'beefier' nodes than cons cells can easily provide.

Other characteristics of BSTs, where n is the number of nodes (keys), and h is the height of the tree, include:

• Search time is a logarithmic function of n (assuming a balanced tree — see below).
• Insertion of a key is equally fast: search for the key, insert it at the leaf where the search terminates.
• For all operations (search, insert, delete) the worst case number of key comparisons = h + 1.
• \(\lfloor \mbox{lg}\ n\rfloor \le h \le n - 1\)
• With average (random) data: \(h < 1.44\ \mbox{lg}\ n\)
• With a poorly built (unbalanced) tree, in the worst case binary search degenerates to a sequential search.
• Inorder traversal produces a sorted list (the basis for the treesort algorithm).

Building a BST

To build a binary search tree for a set of words, use alphabetical order for ordering the keys/words, as in:

[trees are cool and the binary search kind wonderfully so]

Step 1, insert 'trees as the root of the BST
                                              trees

Step 2, insert 'are as the left child of 'trees since 'are < 'trees

                                              trees
                                              /
                                            are

Step 3, insert 'cool as the right child of 'are since 'cool < 'trees and 'cool > 'are

                                              trees
                                              /
                                            are
                                               \
                                              cool

Step 4, insert 'and as the left child of 'are since 'and < 'trees and 'and < 'are

                                              trees
                                              /
                                            are
                                            /  \
                                          and cool

Step 5, insert 'the as the right child of 'cool since 'the < 'trees and 'the > 'are and 'the > 'cool

                                              trees
                                              /
                                            are
                                            /  \
                                          and cool
                                                 \
                                                 the

Step 6, insert 'binary as the left child of 'cool since 'binary < 'trees and 'binary > 'are and 'binary < 'cool

                                              trees
                                              /
                                            are
                                            /  \
                                          and cool
                                              /  \
                                          binary the

Step 7, insert 'search as the left child of 'the since 'search < 'trees and 'search > 'cool and 'search < 'the

                                              trees
                                              /
                                            are
                                            /  \
                                          and cool
                                              /  \
                                          binary the
                                                 /
                                               search

Step 8, insert 'kind as the left child of 'search since that's where it goes

                                              trees
                                              /
                                            are
                                            /  \
                                          and cool
                                              /  \
                                          binary the
                                                 /
                                               search
                                               /
                                            kind

Step 9, insert 'wonderfully where it goes (finally a right child for root!)

                                              trees
                                              /   \
                                            are  wonderfully
                                            /  \
                                          and cool
                                              /  \
                                          binary the
                                                 /
                                               search
                                               /
                                            kind

Step 10, insert 'so where it goes, and the tree is complete.

                                              trees
                                              /   \
                                            are  wonderfully
                                            /  \
                                          and cool
                                              /  \
                                          binary the
                                                 /
                                               search
                                               /  \
                                            kind  so

Post-construction Binary Search Tree Insertion

To insert a new word, very, into this BST, we must compare it to 'trees, then 'wonderfully. At this point the search terminates, because 'wonderfully has no children. Note we needed two comparisons to find 'very's insertion site, as the left child of 'wonderfully. If a key is already in the BST, insertion of that key has no effect. It still costs some comparisons, however. Inserting (futilely) 'cool costs 3 comparisons (the level of 'cool plus one), and 'kind costs 6 comparisons.

Expected Search Cost

Binary search trees have expected search costs, which simply put is the average cost of finding a key. Minimizing this cost for a static (unchanging) tree and a set of keys whose access frequencies are known in advance (think English words as might be used by a spell-checker) is the Optimal BST scenario. GPAO.

Keys' search costs can be weighted based on how likely they are to be looked up. Estimates of these likelihoods are usually good enough if they can't be computed exactly, and the more accurate the estimates, the speedier the average lookup. So an optimal BST would have a common word like is near the root and a rarely used word like syzygy near the leaves. Here are the search costs (number of key comparisons) for the tree above:

UnBalanced

Average cost: 3.6 comparisons

Balanced

Average cost: 2.9 comparisons

A Huffman tree is like an optimal BST, but with a twist. It has a different goal, that of encoding information efficiently, meaning it minimizes the average number of bits per symbol (information atom). A Huffman tree does this by storing more frequently-seen symbols closer to the root and less-frequently-seen symbols further from the root. Bits (1s and 0s) are used to label the links on the path from root to leaf, giving a unique bit string encoding for each symbol.

Unlike a BST, a Huffman tree does not care about key order, and it doesn't use internal (non-leaf) nodes to store the data (neither keys nor bits). The only data items are the symbols, stored at the leaves. The symbols' encodings are stored in the structure of the tree. For example, consider the symbols A through F with the given frequencies:

The encoding process begins with an initial forest of trees (seedlings, actually). These are conveniently stored in a priority-queue — a data structure where high-priority items are always maintained at the front of the queue. The nodes in this collection are ordered by lowest-to-highest frequencies, as in the table above, shown paired below.

([A 0.08] [B 0.10] [C 0.12] [D 0.15] [E 0.20] [F 0.35])

The algorithm for building a Huffman tree creates an initial queue Q of 1-node trees from pairs of n symbols and n weights, which can be passed as pairs or as parallel arrays. The weights are the frequencies — how often the symbols (e.g., characters) occur in some information (e.g., a body of text). These weights/frequencies define the priorities of the symbols, reverse ordered, so the lower the weight, the higher the priority. Once the tree is built, the weights can be forgotten, all that matters is where the symbols are found in the tree.

Algorithm Huffman Tree (inputs and initialization of Q as above)
while Q has more than one element do
    TL ← the minimum-weight tree in Q
    Delete the minimum-weight tree in Q
    TR ← the minimum-weight tree in Q
    Delete the minimum-weight tree in Q
    Create a new tree T with TL and TR as its left and right subtrees,
    and weight equal to the sum of TL's weight and TR's weight.
    Insert T into Q.
return T

Here's how the algorithm proceeds with the given example, using the phrase consolidate u and v into a parent node (with weight w) inserted after x as an abbreviation for the steps in the body of the loop:

Q: [A 0.08] [B 0.10] [C 0.12] [D 0.15] [E 0.20] [F 0.35]

Iteration 1, consolidate [A 0.08] and [B 0.10] into a parent node (with weight 0.18) inserted after D:

Q:             [C 0.12] [D 0.15] [+ 0.18] [E 0.20] [F 0.35]
                                 /      \
                            [A 0.08] [B 0.10]

Iteration 2, consolidate [C 0.12] and [D 0.15] into a parent node (with weight 0.27) inserted after E:

Q:                               [+ 0.18] [E 0.20] [+ 0.27] [F 0.35]
                                 /      \          /      \
                            [A 0.08] [B 0.10] [C 0.12] [D 0.15]

Iteration 3, consolidate [+ 0.18] and [E 0.20] into a parent node (with weight 0.38) inserted after F:

Q:                                                 [+ 0.27] [F 0.35] [+ 0.38]
                                                   /      \          /      \
                                              [C 0.12] [D 0.15] [+ 0.18] [E 0.20]
                                                                /      \
                                                           [A 0.08] [B 0.10]

Iteration 4, consolidate [+ 0.27] and [F 0.35] into a parent node (with weight 0.62) inserted after [+ 0.38]:

Q:                                                                   [+ 0.38]          [+ 0.62]
                                                                     /      \          /      \
                                                                [+ 0.18] [E 0.20] [+ 0.27] [F 0.35]
                                                                /      \          /      \
                                                           [A 0.08] [B 0.10] [C 0.12] [D 0.15]

Iteration 5, consolidate [+ 0.38] and [+ 0.62] into a parent node (with weight 1.00) inserted back into Q:

Q:                                                                            [+ 1.00]
                                                                              /      \
                                                                             /        \
                                                                            /          \
                                                                     [+ 0.38]          [+ 0.62]
                                                                     /      \          /      \
                                                                [+ 0.18] [E 0.20] [+ 0.27] [F 0.35]
                                                                /      \          /      \
                                                           [A 0.08] [B 0.10] [C 0.12] [D 0.15]

Q no longer has more than one element, so exit the while loop and return the tree T ([+ 1.00]).

What the embedded encoding is will become clear, but here's a preview:

By virtue of its construction as a tree, this encoding is prefix-free, meaning no symbol's bit string is a prefix (initial substring) of any other symbol's bit string. The compression is not great, but serves to illustrate the point of all this work. A quick measure of this encoding's success is, what is the average number of bits used to encode a character?

\(3 \cdot 0.08 + 3 \cdot 0.10 + 3 \cdot 0.12 + 3 \cdot 0.15 + 2 \cdot 0.20 + 2 \cdot 0.35 = 2.45\)

Huffman Encoding

1. Traverse the binary tree and generate a bit string for each node of the tree as follows:
   • Start with the empty bit string for the root;
   • append 0 to the node's string when visiting the node's left subtree begins;
   • append 1 to the node's string when visiting the node's right subtree begins.
2. At a leaf, print out the current bit string as the leaf's encoding.

A Huffman tree with n leaves has a total of 2n - 1 nodes, each of which must be visited to generate the leaf nodes' strings. But since each node has a constant height, the efficiency of this algorithm is very good — linear in the number of nodes.

Given this code:

the text CAFEBABE is encoded as 100000110100100000101, a total of 21 bits. (This beats the fixed-length encoding scheme [A=000 B=001 C=010 D=011 E=100 F=101] that requires 3 bits per character and a total of 24 bits 010000101100001000001100 for the 8-character string.)

Huffman Decoding

A bit string (e.g., 0010001011100010101) is decoded by considering each bit from left to right, and starting at the root, traversing left if the bit is 0 and traversing right if the bit is 1, stopping when a leaf is reached. Output the symbol at the leaf, and continue with the next bit.

Simple Graphs

• Correspond to symmetric binary relations.
• Have V, a set of Vertices or Nodes (corresponding to the universe of some relation R).
• Have E, a set of Edges or Arcs or Links (unordered pairs of usually distinct, possibly the same elements \(u, v \in V\) such that uRv).
• Are compactly described as a pair G = (V, E) (with R implied).

Here's an example of a simple graph having V, the set of states in the Intermountain West:

• V = [ID MT WY UT CO NV AZ NM]
• E = \(\{[u\ v] \mid u\ \mbox{adjoins}\ v\} =\) =([ID MT] [ID WY] [ID NV] [ID UT] [MT WY] [WY UT] [WY CO] [UT CO] [UT NV] [UT AZ] [CO NM] [AZ NM] [NV AZ])=

Multigraphs

• Are like simple graphs, but there may be more than one edge connecting two given nodes.
• Have V, a set of Vertices.
• Have E, a set of Edges (as primitive objects).
• Have f, a function \(f : E \rightarrow \{(u,v) \mid u,v \in V \land u \ne v\}\)
• Are compactly described as a triple: G = (V, E, f)

For example, vertices are cities, edges are segments of major highways.

Pseudographs

• Are like multigraphs, but edges connecting a node to itself are allowed.
• The function \(f : E \rightarrow \{(u,v) \mid u,v \in V\}\)
• Edge \(e \in E\) is a loop if \(f(e) = (u, u) = \{u\}\)

Directed Graphs

• Correspond to arbitrary binary relations R, which need not be symmetric.
• Have V, E, and a binary relation R on V.

For example, V = people, \(R = \{(x, y) \mid x\ \mbox{loves}\ y\}\)

Directed Multigraphs

• Like directed graphs, but there may be more than one edge from one node to another.
• Have V, E, and \(f : E \rightarrow V \times V\).

TGB: Terminology Gone Ballistic.

Adjacent, Connects, Endpoints, Initial, Terminal, Degree, In-degree, Out-degree, Complete Graphs, Cycles, Wheels, n-Cubes, Bipartite Graphs, Subgraph, Union, …

Adjacency

Let G be an undirected graph with edge set E. Let \(e \in E\) be (or map to) the pair [u v].

We say:

• u and v are adjacent
• u and v are neighbors
• u and v are connected
• Edge e is incident with nodes u and v
• Edge e connects u and v
• Nodes u and v are the endpoints of edge e

Degree

Let G be an undirected graph, \(v \in V\) a vertex.

• The degree of v, denoted deg(v), is the number of incident edges to it, except that any self-loops are counted twice
• A vertex with degree 0 is called isolated
• A vertex with degree 1 is called pendant

Degree Sequence

A sequence of the degrees of all nodes in a graph, listed in nonincreasing order (highest to lowest), is the graph's degree sequence.

For example, the degree sequence of the knobs-and-lines graph is: [5 5 4 4 4 4 4 3 3 2]

Handshaking Theorem

Let G be an undirected (simple, multi-, or pseudo-) graph with vertex set V and edge set E. Then the sum of the degrees of the vertices in V is twice the size of E:

\[\sum_{v \in V} deg(v) = 2|E|.\]

Directed Adjacency

Let G be a directed (possibly multi-) graph and let e be an edge of G that is (or maps to) [u v].

• u is adjacent to v
• v is adjacent from u
• e comes from u
• e goes to v
• e connects u to v
• e goes from u to v
• u is the initial vertex of e
• v is the terminal vertex of e

Directed Degree

Let G be a directed graph, v a vertex of G.

• The in-degree of v, \(deg^-(v)\), is the number of edges going to v
• The out-degree of v, \(deg^+(v)\), is the number of edges coming from v
• The degree of v is just the sum of v's in-degree and out-degree, \(deg(v) = deg^-(v) + deg^+(v)\)

Directed Handshaking Theorem

Let G be a directed (possibly multi-) graph with vertex set V and edge set E. Then

\[\sum_{v \in V} deg^-(v) = \sum_{v \in V} deg^+(v) = \frac{1}{2} \sum_{v \in V} deg(v) = |E|.\]

Note that the degree of a node is unchanged by whether its edges are directed or undirected.

Special Graph Structures

Special types of undirected graphs:

• Complete graphs K_n
• Cycles C_n
• Wheels W_n
• n-Cubes Q_n
• Bipartite Graphs
• Complete bipartite graphs \(K_{m, n}\)

Complete Graphs

For any \(n \in N\), a complete graph on n nodes (K_n) is a simple graph with n nodes in which every node is adjacent to every other node.

• \(\forall u, v \in V : u \ne v \rightarrow (u, v) \in E\).

Note that K_n has n-choose-2 for its number of edges:

\[\sum_{i = 0}^{n - 1}i = \frac{n(n - 1)}{2}.\]

Cycles

For any \(n \ge 3\), a cycle on n nodes (C_n) is a simple graph where

• \(V = \{v_1, v_2, \ldots, v_n\}\) and
• \(E = \{(v_1, v_2), (v_2, v_3), \ldots, (v_{n - 1}, v_n), (v_n, v_1)\}\).

Wheels

For any \(n \ge 3\), a wheel (W_n) is a simple graph obtained by taking the cycle C_n and adding one extra node \(v_{hub}\) and n extra edges.

• \(\{(v_{hub}, v_1) (v_{hub}, v_2), \ldots, (v_{hub}, v_n)\}\).

n-cubes

For any \(n \in N\), the n-cube (or hypercube) Q_n is a simple graph consisting of two copies of \(Q_{n - 1}\) connected together at corresponding nodes.

Subgraph

A subgraph of a graph G = (V, E) is any graph H = (W, F) where \(W \subseteq V\) and \(F \subseteq E\).

Graph Union

The union \(G_1 \cup G_2\) of two simple graphs \(G_1 = (V_1, E_1)\) and \(G_2 = (V_2, E_2)\) is the simple graph \((V_1 \cup V_2, E_1 \cup E_2)\).

CSP definitions, examples, VTOs.

CSP a discussion of the Chomsky Hierarchy.