Preface
This book was begun around January 1991, as a response to a need I perceived in the
classroom. Students who have not had calculus but intend to pursue the mathematical sciences are
not ready for a formalistic proof-laden treatment of the subject.
1 Relations
This book starts with one of its most abstract topics, so don't let the abstract nature deter
you. Relations are quite simple but like virtually all simple mathematical concepts they have
their subtle aspects. Relations are defined on collections (or sets) of objects.
2 Graphs
We are concerned with graphs. Every graph contains
objects that are known as nodes or vertices depending on the
mood of the speaker. A graph always contains at least one
node. A graph usually also contains lines that go between
nodes. These lines are known as arcs or edges, again
depending on the mood of the speaker.
3 Integer Functions
The integer function that is the heart of this section is the modulo function. However,
before getting to it, let us look at some very simple functions. The first (and most important) of
these is the floor function. We denote this function by lxm although it can be denoted by floor(x)
It is also widely known as the greatest integer function and is found in some computer languages
as the integer function (sometimes denoted INT(x)).
4 Algorithms
An algorithm is the abstract version of a computer program. In essence a computer
program is the codification of an algorithm, and every algorithm can be coded as a computer
program.
5 Recursive Algorithms
Recursion is a form of definition and of algorithms that is very important in computer
science theory as well as in practice. Recursive algorithms can be inefficient or efficient.1 A
recursive definition or a recursive algorithm is characterized by self-reference.
6 Induction
The principle of induction is a one of the most fundamental laws of mathematics.
Students come across it, as here, as a method of proof. However, it is a basic property of the
natural numbers (i.e. the positive integers) and can be considered as part of the definition of the
natural numbers. Since we do not define the natural numbers here, the principle will be simply
given as an axiom.1
7 Graph Searching
Algorithms for searching graphs go back at least to the nineteenth century when they
were used for mazes. Until the advent of computers they were an extremely obscure topic (as
was graph theory). We are going to look at two algorithms which represent the two main
approaches to searching graphs.
8 Horner's Algorithm
Horner's algorithm is an excellent example of an algorithm. It is a simple and useful
algorithm, but it does not have much to do with discrete mathematics.
9 Shortest Paths
A fundamental problem in graphs is finding the shortest path from vertex A to vertex B.
Fortunately there are several simple (and efficient algorithms for doing this). We will look at
the three best of these: Dijkstra�s algorithm, Floyd�s algorithm, and the Bellman-Ford algorithm.
First we need to discuss different types of shortest path problems and various conventions that
we will use in solving them.
Electronic Transactions on Numerical Analysis - Free eBook Electronic Transactions on Numerical Analysis - Download ebook Electronic Transactions on Numerical Analysis free
|