Discrete mathematics is an exciting and rapidly growing area of mathematics which has important applications in computer science and in many high technology areas. For example, "secure" internet communication, efficient storage of data (e.g. jpeg) and robust communication networks are developed using techniques from discrete mathematics.
This course serves two main populations, students from mathematics and students from computer science. The course also has two distinct goals: one is to teach the basics of set theory, logic, combinatorics and graph theory. The other is to convey concepts essential to mathematics: absolute clarity and precision in definitions and statements of fact, and rigorous methods for establishing that a statement is true.
|§1.1-4||Logic and logical arguments.||4 classes|
|§2.1-3||Predicates and quantifiers.||3 classes|
|§3.1-7||Proofs: direct, by counterexample, by indirect argument.||6 classes|
|Some number theory.|
|§5.1-3||Sets: subsets, union, intersection.||4 classes|
|Venn diagrams. Algebra of set operations.|
|Cartesian product, power set.|
|§10.1-3,5||Relations. Reflexive, symmetric and transitive relations.||6 classes|
|Equivalence relations. Partially ordered sets|
|§7.1,3,4,5||Functions: one-to-one and onto functions.||4 classes|
|Invertible functions. The pigeonhole principle.|
|Composition of functions.|
|§4.1-4||Sequences, mathematical induction||6 classes|
|§8.1-3||Recursively defined sequences:||4 classes|
|Finding explicit formulas,|
|establishing the formulas by induction.|
|§6.1-7||Combinatorics: Counting and the multiplication rule.||6 classes|
|Permutations and combinations.|
We will have weekly assignments, three midterms and a final exam. For the weekly assignments (see above), there will be a small number of problems (10 or so) which you should write up carefully. They will be graded and returned to you promptly (to the best of my ability).
I recommend that you do or at least attempt most of the exercises in the book. That is the best way to learn!
Point value for the work will be as follows (plus or minus 50 points)
The first exam is tentatively Wed. Oct. 2.
The second exam is TBA.
The final is Wednesday, December 18, 10:30-12:30.