Index Index
Adjacency Matrix, Definition
Adjacency Matrix Method, Subsection
Algorithmic Complexity, Section Subsection
Algorithms, Section
Alphabet, Definition
Analog-to-digital Conversion, Example
Antisymmetric Relation, Definition
Atom of a Boolean Algebra, Definition
Backus-Naur Form, Subsection
Basic Law Of Addition:, Theorem
Basic Operations, Subsection
Basic Set Operations, Section
Bayes’ Rule, Section
Bayes’ Theorem, Subsection Definition
Bayes’ Theorem (Generalized), Definition
Bernoulli Trial, Definition
Biconditional Proposition, Definition
Bienaymé’s Formula, Theorem
Big O Notation, Subsection
Big O of Common Functions, Subsection
Big O of Function Combinations, Subsection
Big Omega, Subsection
Big Theta, Subsection
Bijection, Definition
Binary Conversion Algorithm, Algorithm
Binary Representation, Section
Binary Search Algorithm (Iterative), Algorithm
Binary Search Algorithm (Recursive), Algorithm
Binary Tree, Definition
Binary Trees, Section
Binomial Coefficient, Definition
Recursive Definition, Definition
Binomial Coefficient Formula, Theorem
Binomial Distribution, Subsection Definition
Binomial Theorem, The, Theorem
Bipartite Graph., Definition
Bipartitie
a Limerick, Poem
Boolean Algebra, Definition
Boolean Algebras, Section
Boolean Arithmetic, Definition
Boolean Expression, Definition
Boolean Expressions, Section
Bounded Lattice, Definition
Breadth-First Search, Subsection
Breadth-first Search, Algorithm
Bridge, Definition
Bubble Sort, Subsection
Bubble Sort Algorithm, Algorithm
Cardinality., Definition
Cartesian Product, Definition
Center of a Graph, Item
Characteristic Equation, Definition
Characteristic function, Exercise
Characteristic Roots, Definition
Chromatic Number, Definition
Church-Turing Thesis, Paragraph
Circuit Minimization, Section
Closed Form Expression., Definition
Closest Neighbor Algorithm, Algorithm
cofactor, Definition
Combination with Repetition Formula, Theorem
Combinations, Subsection
Combinations with Repetition, Subsection
comparing expected values, Subsubsection
Complement of a Lattice Element, Definition
as an operation, Definition
Complement of a set, Definition
Complement of an Event, Definition
Complemented Lattice, Definition
Complete Undirected Graph., Definition
Composition of Functions, Definition
Composition of Relations, Definition
Computability, Section Subsection
computational unsolvability, Paragraph
Conditional Probability, Subsection
conditional probability, Definition
Conditional Statement, Definition
Congruence Modulo m, Definition
Conjunction, Logical, Definition
Connected Component, Definition
Connectivity in Graphs, Section
Constructive Proof, Definition
Context-free Grammar, Subsection
Contradiction, Definition
Contrapositive, Definition
Converse, Definition
Countable Set, Definition
Counting Binary Trees, Subsection
covering relation, Definition
Cramer’s rule, Subsection Definition
Cycle, Definition
Degree, Definition
Degree Sequence of a Graph, Definition
Derangement, Subsection
Deterministic Finite-State Automata, Subsection Definition
Deviation of a Random Variable, Definition
DFA, Subsection
Digraph, Paragraph
Direct proof, Example
Directed Graph, Definition
Directed graph, Paragraph
Disjoint Events, Definition
Disjoint Sets, Definition
Disjunction, Logical, Definition
Disjunctive Normal Form, Definition
Distributive Lattice, Definition
Divides, Definition
Divisors of an Integer, Definition
Doyle, Chris, Poem
Duality for Boolean Algebras, Definition
Echelon Form, Definition
Elementary Operations, Definition
Embedding of a graph, Paragraph
Empty set, Paragraph
Equivalence, Definition
Equivalence Class, Item
Equivalence Relation, Definition
Equivalence Relations, Subsection
equivalent grammars, Definition
Euclid’s Algorithm, Subsection Subsubsection
Eulerian Paths, Circuits, Graphs, Definition
Euler’s Formula, Theorem
Euler’s Theorem, Theorem
Koenigsberg Case, Theorem
Existential Quantifier, Definition
expectation of a binomial distribution, Theorem
expectation of a geometric distribution, Theorem
Expected Successes in a Bernoulli Trial, Theorem
expected value, Definition Theorem
Expected Value and Variance, Section
Expected Values, Subsection
Expression Tree, Subsection
Factorial, Definition
Factorial Algorithm, Algorithm
Factorial Algorithm (Recursive), Algorithm
Fibonacci Algorithm (Recursive), Algorithm
Fibonacci Sequence, Example
Finite-State Automata, Section
finite-state automaton, Paragraph
Finite-State Machines, Section
Five-Color Theorem, Theorem
Flow Augmenting Path, Definition
Forest., Definition
Formal Languages, Section
Four-Color Theorem, Theorem
Function, Definition
Bijective, Definition
Composition, Definition
Equality, Definition
Injective, Definition
One-to-one, Definition
Onto, Definition
Surjective, Definition
Functions
Of two Variables, Subsection
Functions Between Two Sets
Set of, Definition
Gauss Elimination, Subsection Paragraph
Gauss Jordan Method, Paragraph
Gauss-Jordan Procedure, Definition
Generalized Set Operations, Definition
Generating Function, Definition
Generating Functions, Section
Closed form expressions for, Subsection
Operations on,, Subsection Definition
Generative Grammars, Paragraph
Geometric Distribution, Subsection Definition
George Boole
a Limerick, Poem
grammar, ambiguous, Paragraph
Grammars, Section
Graph
Data Structures, Section
Multigraph, Definition
Simple Directed, Definition
Undirected, Definition
Graph Coloring, Definition
Graph Optimization, Section
Graphic Sequence, Definition
Greatest Element, Definition
Greatest Lower Bound, Definition
Greedy Change Making Algorithm, Algorithm
Growth of Functions, Section
Halting Problem, Paragraph
Hamiltonian Paths, Circuits, and Graphs, Definition
Hasse Diagram, Paragraph
Homogeneous Recurrence Relation., Definition
Howlett,Chris, Poem
Identity Function, Definition
Identity Matrix, Definition
Image of an Element., Definition
Implication, Definition
Improper subset, Paragraph
Inclusion-Exclusion, Laws of, Theorem
Independence, Section
Independent Events, Definition
Independent events, Subsection
Independent Random Variables, Definition
Indirect proof, Paragraph
Induced Subgraph, Definition
Induction and Recursion, Subsection
Injection, Definition
Insertion Sort Algorithm, Algorithm
Intersection, Definition
Introduction to Recursion, Section
Inverse
Matrix, Definition
Inverse Function
of a function on a set, Definition
Inverse Matrix, Definition
Isomorphic Graphs, Definition
Join, Definition
Kruskal’s Algorithm, Algorithm
Language Generated by a Regular Expression, Definition
Languages, Section
Lattice, Definition
Lattice Paths, Exercise
Lattices, Section
Laws of Matrix Algebra, Section
Leaf of a binary tree, Item
Leaf, of a binary tree, Item
Least Element, Definition
Least Upper Bound, Definition
Level of a vertex, Paragraph
Limerick
countably infinite, Poem
Enumerative Combinatorics, Poem
Limits of Computation, Subsection
Linear Search Algorithm, Algorithm
linearity of expectation, Subsection Theorem
linearity of expectation (generalized), Theorem
Logarithm
General Base, Definition
Logarithm, base 2, Definition
Logarithms, Subsubsection
Properties, Theorem
Logic Circuit Minimization, Section
Logic Circuits, Section
Logic Gates, Section
Lower Bound, Definition
Matrices, Section
Matrix Addition, Definition Definition
Matrix Arithmetic, Section
matrix cofactor, Definition
Matrix Determinant, Section
Matrix Equality, Definition
matrix minor, Definition
Matrix Multiplication, Definition
Matrix Oddities, Section
Maximal flow, Paragraph
Maximum Element Algorithm, Algorithm
Meet, Definition
Merge Algorithm, Algorithm
Merge Sort, Subsection
Merge Sort Algorithm, Algorithm
Mesh Graph, Exercise
Minimal Spanning Tree, Definition
Minimum Diameter Spanning Tree, Definition
Minset, Definition
Minset Normal Form, Definition
Minterm, Definition
Minterm Normal Form, Definition
Modulo Operation, Subsubsection
Multigraph, Definition
Multiple Pop and Push:, Definition
Multiplicity, Definition
Multiset, Definition
N-cube, Definition
NAND, Definition
NDFSA, Subsection
Negation, Logical, Definition
Network, Definition
Networks, Subsection
NFA, Subsection
Non-Constructive Proof, Definition
non-terminal symbol, Paragraph
Nondeterministic Finite-State Automata, Definition
Noneterministic Finite-State Automata, Subsection
Nonhomogeneous of Finite Order Linear Relations
Solution, Subsection
Order of a Recurrence Relation, Definition
Ordering Diagram, Paragraph
Ordering Indistinguishable Objects, Subsection
Pairwise and Mutually Independent Events, Definition
Pairwise and Mutually Independent Random Variables, Definition
Partial Ordering, Definition Definition
Partially ordered set, Definition
Partition, Definition
Path Graph, Definition
pattern matching, Paragraph
Permutation, Definition Definition
Permutation Counting Formula, Theorem
Permutations Of Multiplisets, Theorem
Permutations with Repetition, Subsection
Pigeonhole Principle, Theorem
Pivot Column, Definition
Pivot Position, Definition
Planar Graph, Definition
Plane Graph, Definition
Polynomial Big O Theorem, Theorem
Polynomial Expression
Non-recursive)., Definition
Recursive definition, Definition
Polynomials, Subsection
Polynomials and their evaluation, Subsection
Poset, Definition
Posets Revisited, Section
Power Set, Definition
Power Set Cardinality Theorem, Theorem
Powers of Functions, Definition
Prim’s Algorithm, Algorithm
Probability, Section
probability function, Definition
probability of an event, Definition
probability space, Definition
Production Rule, Paragraph
Proper subset, Paragraph
Properties of Functions, Section
Proposition, Definition
Pumping Lemma, Theorem
Random Variable, Definition
Random Variables, Subsection
Range of a Function., Definition
Recurrence Relation, Definition
Recurrence Relations
Solving, Subsection
Recurrence relations obtained from “solutions”, Subsection
Recursive Algorithms, Section
recursive language, Paragraph
Recursive Maximum Element Algorithm, Algorithm
Recursive Searching, Subsection
Recursive Sorting, Subsection
recursively enumerable language, Paragraph
References, References
Reflexive Relation, Definition
Regular Expression, Definition
Regular Expressions, Subsection
regular grammar, Definition
Regular Language, Definition Subsection Subsection
Relation, Definition
Relation Notation, Paragraph
Relation on a Set, Definition
Rewriting Rule, Paragraph
Robinson, Andrew, Poem
Rooted Tree, Definition
Rooted Trees, Section
Row Operations, Definition
Row Reduced Echelon Form, Definition
Rule Of Products, The, Subsection
SageMath Note
Binary Conversion Algorithm, Subsection
bridge hands, Subsection
Cartesian Products and Power Sets, Subsection
Functions, Subsection
Graphs, Subsection
Kruskal’s Algorithm, Subsection
Power Series, Subsection
Search in a Graph, Subsection
Sets, Subsection
sample space, Definition
Scalar Matrix Multiplication, Definition
Scalar Multiplication, Definition
search and replace, Paragraph
Selection Sort, Algorithm
Sequence, Definition
Sequences, Section
Operations on,, Definition
Recursively Defined, Subsection
Set of Functions Between Two Sets, Definition
Set-Builder Notation, Paragraph
Sheffer Stroke, Definition
Solution Set, Example
Spanning Subgraph, Definition
Spanning Tree, Definition
Spanning Trees, Section
Standard Deviation of a Random Variable, Definition
String, Definition
Subgraph, Definition
Sum of Products, Definition
Summation Notation and Generalizations, Section
Surjection, Definition
Switching Theory, Section
Symbol, Definition
Symmetric Difference, Definition
Symmetric Relation, Definition
System of Linear Equations, Definition
Systems of Equations, Section
Tautology, Definition
terminal symbol, Paragraph
Three Utilities Puzzle, Paragraph
Tournament Graph, Definition
Transitive Closure, Definition
Transitive Relation, Definition
Traveling Salesman Problem, The, Subsection
Traversals of Binary Trees, Subsection
Traversals of Graphs, Section
Tree, Definition
triangular matrix, Definition
Truth Set, Definition
Tuples with Repetition, Subsection
Turing Machine, Section Definition
Turing-acceptable, Definition
Turing-computable, Definition
Turing-decidable, Definition
Undirected Graph, Definition
Uniform Distribution, Definition
Union, Definition
Universal Quantifier, Definition
Universe, Definition
Upper Bound, Definition
Value of a Flow, Definition
Variance, Subsection Definition
Variance as Expectation of the Deviation, Theorem
variance of a binomial distribution, Theorem
Variance of a geometric distribution, Theorem
Variance of Successes in a Bernoulli Trial, Theorem
Variance Using Squared Expectations, Theorem
Vector, Definition
Weighted Graph, Definition
What Is a Tree?, Section
X = x, Definition
Zero Matrix, Definition
