Fall 2011

Schedule Number: 21851

Meeting: MWF 1:00 - 1:50

NE 60

San Diego State University

TuTh afternoons I may also be in my office and available.

Other times: by appointment.

(2nd Ed. or 3rd Ed. may also be used, but you are responsible for attention to any differences.)

My lecture notes, available on Blackboard.

SCHEDULE | |

PROBLEMS TO STUDY AND WRITTEN ASSIGNMENTS | |

REVIEW SHEETS: First Exam, Second Exam, Third Exam and some notes, Fourth Exam, Fifth Exam, Final Exam. |

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 the rigorous use of terminology and proof which is essential to mathematics: that is, clarity and precision in definitions and statements of fact, and logical methods for establishing that a statement is true. The fundamental mathematics taught in this course is useful in computer science and electrical engineering. The analytical skills developed are critical to understanding computer languages, to the development of good programming skills, and, more generally, to appreciating scientific method. The experience with abstract concepts, proof writing and the use of formal definitions should help students in all disciplines to articulate their ideas more clearly.

SECTIONS | TOPICS | TIME |

§2.1-4 | Logic and logical arguments. | 4 classes |

§3.1-3 | Predicates and quantifiers. | 4 classes |

§4.1-7 | Proof: direct proof, division into
cases,proof by contraposition, proof by contradiction and disproof by counterexample. |
6 classes |

Some number theory:
Statements of the division theorem, unique factorization.
Proof of the irrationality of sqrt(2), proof of the infinitude of primes. |
||

§5.1-4, 6, 7 | Sequences, mathematical induction | 4 classes |

Recursively defined sequences: | 4 classes | |

Finding explicit formulas, | ||

establishing the formulas by induction. | ||

§6.1-3 | Sets: subsets, union, intersection. | 4 classes |

Venn diagrams. Algebra of set operations. | ||

Cartesian product, power set. | ||

§7.1-3 | Functions: one-to-one and onto functions. | 4 classes |

Invertible functions. | ||

Composition of functions. | ||

§8.1-3,5 | Relations. Reflexive, symmetric and transitive relations. | 6 classes |

Equivalence relations. Partially ordered sets | ||

§9.1-5, 7 | Counting: the addition
rule and the
multiplication rule. The pigeonhole principle. |
6 classes |

Permutations and combinations. |

Grading for this course is based on two levels of expectations.

Level 1 involves mastering computational problems, ability to recall
and use terminology and to give short responses to questions.
The maximum grade of B+ is based on the following.

- Webwork homework assignments worth 100 points.
- 7 exams worth 100 points each, lowest score is removed.
- Final exam worth 300 points.

Level 2 involves writing proofs, and doing problems that require some organization and explanation. If you attain a grade of 800 or above on Level 1 you may be considered for a higher grade, based on additional work.

- Written homework assignments.
- Additional exam problems.

Most students find this a tough class. You will greatly magnify your chances of succeeding if you work regularly and attentively! Start the assignments early and do most of the exercises in each section we cover. If you get stuck, please ask me in class. Your questions often lead to a valuable class discussion. You are also quite welcome during my office hours, but come prepared.