Discrete Math: What's it all about?
Math 1220 or Math 1700 (Calculus) and a computer programming
language with a grade of C or better.
Dossey, Otto, Spence, Vanden Eynden,
5th ed., Addison Wesley, 2006.
Please bring this text with you to every class.
Why the prerequisites?
Calculus is required not because we use it extensively,
but because you need to possess some mathematical maturity,
have the ability to conduct mathematical arguments, and possess the
mathematical stamina that calculus builds. The programming requirement is
there because then you can better understand the
value of, and appreciate the difficulty of not just proving a result, but
proving it in an elegant and constructible way that can be translated into a
step-by-step procedure, in short, an efficient algorithm that can be programmed
into a computer.
Here are some of the questions we will be addressing in this course:
Hope this piques your interest, and makes you into an active, regular
participant in the course!
- Where does the word algorithm come from?
You'll be suprised by
some of the answers I get to this question. And most students who don't
know the answer are surprised to learn its origin.
- Sets, functions, and relations.
What is a one-to-one function?
What is an onto function? What is an equivalence relation? Why are these
- An introduction to mathematical logic.
ow can we
determine if two statements are logically equivalent? How do we negate a
statement of the sort, ``Everybody loves somebody''. Would it be ``Nobody
loves everybody''. Nope. ``Everybody loves nobody''. Nope.
``Somebody loves everybody''. Nope, nope. Then what
could it be? When is a statement of the sort ``P implies Q'' false?
We also study methods of proof -- proof by contradiction,
direct proof, proof by induction. We'll look at purported ``proofs'' and try
to find out if they are legitimate or not.
- Learning how to count.
This may sound
strange at first. But here are some examples of the things we try
to count. If we were to distribute 10 identical sticks of gum among 3
children, how many different distributions would there be? Or, if we were to
choose a committee of 4 from a group of 6 men and 5 women, how many
different committees can we form? If the committee had to have at least 2
women on it, how many different committees would we be able to make?
Here's a different but important kind of counting problem.
Suppose we're given a program that
takes as input an unsorted list, and then sorts it in some desired order.
How do we count how many swaps this algorithm performs in order to sort a
list of some fixed but arbitrary size? If can figure this out, then we can
compare two sorting algorithms, and figure out which one will be better.
If we were to distribute 10 sticks of gum randomly
among 3 children, most of us would agree that it is highly
unlikely that one kid will get all 10 sticks of gum.
We might even agree that the event that each child gets at least 3 sticks of gum is more likely.
But how much more likely is it?
What is the probability that each child gets at least 3
sticks of gum? Is it close to half?
Here is a Short History of
- Recurrence relations.
How to set them up. How to solve first
order and second order homogeneous recurrence relations with constant
coefficients. Here is an example of a situation that calls for setting up
and solving a first order recurrence relation: You've just turned 25, and are starting
out on your first full-time job. You decide to open an Individual
Retirement Account (IRA). You put $125 each month into this account,
which earns an annual interest rate 7%. You do this till you reach age 65.
Will you have a quarter of a million dollars in this account by then? How
much will the account be worth?
Now suppose you had started investing $125 each month when you were 35
instead, and continued until age 65.
How much would the account be worth when you retire at 65?
What is the moral of the story?
(By the way, the advantage of an IRA
account is that you pay no taxes on the earnings till you retire
and start withdrawals.)
- Network Flows.
This is a cool subject, with obvious
applications. Think of a connected graph with the vertices representing
locations, and directed edges representing directions of flow of some
commodity. Each edge has a capacity, which represents the maximum amount
of the commodity that can flow across the edge. There is exactly one
vertex in the graph that is a "source", that is, no edges flow into it.
And there is exactly one vertex that is a "sink", that is, no edges flow
out of it. The problem is to find the maximum flow -- that is the maximum
amount of the commodity that can be sent through the network, from the
source to the sink, without violating the capacities of the edges, and with
no loss or accumulation of the commodity at any intermediate vertex (this
means the total amount of flow into an intermediate vertex must equal the
total amount of flow out of the vertex). The algorithm which we will
study to solve this problem is a fairly
"modern" piece of mathematics, dating to the work in the early 1960's
of two American mathematicians, Ford and Fulkerson.
Last modified: Fri Dec 1 18:21:43 EST 2006
[ home ]
[ Math 145 ]
[ teaching ]
[ selected papers ]
[ selected links ]