Discrete Mathematics

Math 245
Fall 2012
Schedule Number: 21805
Meeting: TuTh 11:00 - 12:15
San Diego State University

Last Class: Thursday, Dec. 6.
Final Exam: Thursday, Dec. 13, 10:30-12:30.

Professor: Mike O'Sullivan
Email: m.osullivan@math.sdsu.edu
Office: GMCS #579, ext. 594-6697
Office Hours: Tu, Th 1:00-2:30.
        Most of the afternoon on TuTh I will be in my office and available.
        Other times: by appointment.

Teaching Assistant: Carina Mueller
Office: GMCS #528, ext. 594-6697
Office Hours: M, W, 1:00-4:00, 5:00-6:30


S. Epp, Discrete Mathematics with Applications, 4th Ed.
(2nd Ed. or 3rd Ed. may also be used, but you are responsible for attention to any differences.)

My lecture notes, available on Blackboard.

Detailed Information

REVIEW SHEETS:    First Exam,    Second Exam,    Third Exam,    Final Exam.   
SOLUTIONS:    First Quiz   

Course Description

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 three main degree programs: mathematics computer science, and computer engineering. The course also has two distinct goals. One is to develop skills in several areas of discrete mathematics: set theory, logic, number theory and combinatorics. The other is to convey the rigorous use of terminology and proof which is essential to mathematics: clarity and precision in definitions and statements of fact, and logical methods for establishing that a statement is true. The 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.


Here is a rough idea of the amount of time I expect to spend on each topic, but the order in which we will cover the material may be a bit different. I am also open to suggestions if the class would like to spend more time on certain topics or cover items not listed here. A day by day schedule (see above) will be maintained to keep you informed of upcoming and past lectures.

§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.


We will have weekly assignments using Webwork , midterms and quizes and a final exam.

Point value for the work will be as follows.
Assignments 150
Tests 550
Final 300
Total 1000

The point values for each item are subject to change by plus or minus 50 points.

The ranges for grades are as follows: 85% and above for A- and A; 72-85% for B- to B+, 60-72% for C- to C+ and 50-60% for D- to D+.

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.