Discrete Mathematics

Math 245
Spring 2012
Schedule Number: 21757
Meeting: TuTh, 9:30-10:45.
GMCS 214
San Diego State University

Final Exam: Thurs. May 10, 08:00-10:00.

Professor: Mike O'Sullivan
Email: m.osullivan@math.sdsu.edu
Office: GMCS #579, ext. 594-6697
Office Hours: TuTh: 11:00-1:00,
          Other times: by appointment.
           I'm often in my office and available on TuWeTh.


My lecture notes, available on Blackboard.
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.)

Detailed Information

REVIEW SHEETS:    First Exam,    Second Exam,    Third Exam,    Final Exam,   

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 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, number theory and combinatorics. 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, 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, and the order in which we will cover them. 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.

§1.1-4 Logic and logical arguments. 4 hours
§2.1-3 Predicates and quantifiers. 4 hours
§3.1-7 Proof: direct proof, division into cases,proof by contraposition,
proof by contradiction and disproof by counterexample.
6 hours
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-3 Sets: subsets, union, intersection. 4 hours
Venn diagrams. Algebra of set operations.
Cartesian product, power set.
§10.1-3,5 Relations. Reflexive, symmetric and transitive relations. 6 hours
Equivalence relations. Partially ordered sets
§7.1,3,4,5 Functions: one-to-one and onto functions. 4 hours
Invertible functions. The pigeonhole principle.
Composition of functions.
§4.1-4 Sequences, mathematical induction 4 hours
§8.1-3 Recursively defined sequences: 4 hours
Finding explicit formulas,
establishing the formulas by induction.
§6.1-7 Combinatorics: Counting and the multiplication rule. 6 hours
Permutations and combinations.


We will have weekly assignments, three midterms and a final exam. Some of the assignments will be done on Webwork . Other assignments will be handwritten. Written assignments should be done carefully and legibly. They will be graded and returned to you promptly (to the best of my ability).

Most students find this a tough class. You will greatly magnify your chances of succeeding if you work regularly and attentively! (1) Read the lecture notes before class. (2) Start the assignments early. (3) Do most of the recommended exercises. (4) Be active in class; work problems when I give them, ask questions when you are confused. Your questions often lead to a valuable class discussion. You are also quite welcome during my office hours, but come prepared.

Point value for the work will be as follows.
Webwork 100
Written assignments 150
Tests 450
Final 300
Total 1000
85% and above is an A, 72-85% is a B, 60-72% is a C and 50-60% is a D.