Instructor	Niloufer Mackey nil.mackey@wmich.edu	Home
Prerequisite.	Math 1220 or Math 1700 (Calculus) and a computer programming language with a grade of C or better.
Text.	Discrete Mathematics, 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:

• 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 concepts useful?
• 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.
• Probability. 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? Appreciably below? Here is a Short History of Probability.
• 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.

[ home ]    [ Math 145 ]    [ teaching ]   [ selected papers ]   [ selected links ]