\magnification=\magstep 1
\parindent=0 pt
\parskip=5 pt

\centerline{Discrete Mathematics,  Math 302}

\centerline{311 Milner, Phone 845-3654, email Doug.Hensley@math.tamu.edu}


The catalog description of this course can give the impression that it's a course in terminology. Terminology there is, and a lot of it. There is the terminology of formal logic: $p, q, \wedge,\vee$, $ \neg, \Rightarrow, \Leftrightarrow $, $ \forall,\exists, \clubsuit,\heartsuit $ (Well, it {\it seems } like the kitchen sink!). There are sets (finite, for the most part), subsets, power sets,  relations, functions (injective, surjective, bijective, etc.), binomial coefficients, graphs, $\sum$. There is the terminology of rates of growth: $\ll, \Omega $, and `Big Oh'. 

Fortunately, the subject matter is not really the terminology. There are a few common threads, or ways of thinking about things, that will show up continually in all these topics. The same was true of calculus, if you think back: Derivatives, integrals, and limits were at the heart of it all. 

Here, the corresponding ideas are counting, reformulation, and induction. Counting includes, naturally, direct enumeration. But most of the time, there will be better ways to count something. For instance, we all know better than to count the squares on a chess board: All you really have to do is to multiply the number of squares in a row by the number in a column and $8\times 8=64$. Reformulation is a matter of setting a new question in an old context, after which the answer can be pretty obvious. For instance, how many ways are there to choose a pair of symbols, where the first symbol must be one of abcdefgh, and the second, 12345678? Well, the squares of a chessboard can be labeled with such symbols...for instance, the white rooks go on a1 and h1 originally. With this {\it reformulation}, the answer is obvious: there are 64 such pairs. 

Induction is the logical process of bootstrap reasoning. You may have seen the old chestnut $\sum_{k=1}^n k=n(n+1)/2$ formula proved by induction. The effective use of induction is a deep and subtle skill, requiring long experience with a wide variety of cases. Often, in order to prove A, you must discover that moreover B is true, and then prove B (of which A is a part.) The reason it can pay to attempt MORE is that this MORE is also part of your inductive premise. That is, with induction, the thing to be proved shows up as part of what you can assume (for the previous $n$) as well as what you are now trying to prove (for $n+1$). Although the text is organized about the terminology rather than the techniques, we shall take up induction at the very start of the course and continue with it right to the end.

There will be a series of several mini-exams, seven in all, of which the best 6 will count for 10\% each of your final grade. There will be weekly homework, due each Thursday. A couple of the problems will be selected for grading. Two sets will be dropped. The homework will then account, in aggregate, for 20\% of your score. Finally, there will be a final. This counts 20\% too, for a grand total of 100. A score of 85\% or better earns an A, 70\% -84\%, a B, and so on. The University has asked that we remind you that all work submitted for credit must be your own. If you wish to incorporate material from sources or fellow students in an assignment, name your source and clearly identify that part (it should be small) of the assignment which is due to any source other than yourself. 
Assigned homework is listed in the following pages.\vfill\eject

\parindent =0 pt
\parskip=5 pt

Jan 15-17: 2.1-2.3
2.1 \# 3, 5, 8h, 9, 10, 11, 14, 17, 18. 4.1 \# 1a.
2.2 \# 1, 11, 15, 19, 21d. 2.3 \# 1c, 3ace, 4, 5, 7, 12.

Jan 20-24: 2.4-2.5, Quiz 1.
2.4 \# 1abh, 2b, 3, 4afn, 10, 11, 20a, 27. 2.5 \# 4, 8a, 9, 16, 20, 21. 4.1 \# 1c, d.

Jan 27-31: 3.1-3.2 . 3.1 \# 1, 2, 4, 8a, 10, 16, 20ad, 23. 3.2 \# 1af, 2de, 3,6, 10a, 11, 18a, 20.

Feb 3-7: 3.2-3.4, Quiz 2. 3.3 and 3.4 \# 4, 5, 7, 10, 13, 15. 4.1 \# 1ef.

Feb 10-14: 1.1-1.2. 1.1 \# 3, 5, 8, 11, 14c, 20, 23, 25, 26, 28, 30, 31, 39. 4.1 \# 2a.

Feb 17-21: 1.3-1.4, Quiz 3. 1.3 \# 3, 4, 8, 15, 18, 19, 24, 25a, 28a, 29, 31, 32, 37, 38. 1.4 \# 3, 9, 15, 17, 21. 4.1 \# 2c.

Feb 24-28: 4.1 \# 3, 5, 8, 12, 13, 16, 18.

Mar 3-7: 5.1-5.2, Quiz 4. 5.1 \# 1, 2, 5, 8, 10. 5.2 \# 1, 3, 7, 8, 12, 15, 24, 25. 4.1 \# 19.

Mar 10-14: Spring Break

Mar 17-21: 5.3-5.4. 5.3 \# 1, 2, 3, 5. 5.4 \# 3, 4, 7, 8, 12, 14. 4.1 \# 21.

Mar 24-28: 5.5-5.6, Quiz 5. 5.5 \# 1, 2, 5, 6, 7, 8, 11, 13, 18, 19
5.6 \# 1, 2a, 7, 11, 14e, 20a,h. 4.1 \# 24.

Mar 31-Apr 4: 5.7 \& 7.1. 5.7 \# 1, 4, 7, 10 and supplemental problems. 7.1 \# 1, 4, 9, 12, 13, 15.

Apr 7-11: 72. \& 7.4, Quiz 6. 7.2 \# 2, 7, 9!, 16, 17, 23, 24. 7.4 \# 1, 6, 7, 10, 13, 18.

Apr 14-18: 10.1-10.2. 10.1 \# 1,2, 3, 5, 7, 8. 10. 2 \# 1aceg, 3, 4, 5, 6a, 8, 9, 16, 19.

Apr 21-25: 10.6 and supplementary material, Quiz 7. 10.6 \# 1, 2, 4, 8 and supplemental problems.

Remaining time: More on the `master theorem' of recurrence growth rates. 



\bye