CMPS 295 Discrete Structures
Catalog Description
CMPS 295 Discrete Structures (5 units)
Discrete structures and applications in computer science. Proofs, with a focus on induction. Introduction to propositional and predicate logic, functions, relations and sets, algorithm analysis, counting techniques, recursion and solution of recurrence relations, graph theory and trees. CMPS 221 or CMPS 222 with a grade of C- or better; MATH 190 or MATH 191
Prerequisites by topic
Polynomial, exponential and logarithmic functions
Units and Contact Hours
5 quarter units. 4 units lecture (200 minutes), 1 unit lab (150 minutes).
Required for CE and CS.
Required Textbook
Recommended Textbook and Other Supplemental Materials
Discrete Mathematics and Its Applications by Kenneth Rosen, 7th Edition, ISBN 978-0-07-338309-5 (available as a rental in the bookstore). The 6th Edition is also acceptable, ISBN: 978-0-07-288008-3.
Donna Meyers
Student Learning Outcomes
This course covers the following ACM/IEEE Body of Knowledge student learning outcomes:

CC-DS: Discrete Structures
CC-AL: Algorithms and Complexity
CE-DSC Discrete Structures

ABET Outcome Coverage
The course maps to the following program/student outcomes for Computer Science (CAC/ABET) and Computer Engineering (EAC/ABET):

(CAC PIa5, EAC PIa5): Use discrete mathematics techniques and algorithms.
Assessed by question on weekly quiz.

Lecture Topics and Rough Schedule
o propositional logic and logical connectives
o truth tables and logical equivalences
o converse, inverse, contrapositive
o normal forms (conjunctive and disjunctive)
o predicate logic with nested quantifiers
o logical inference rules (modus ponens, modus tollens, fallacies ...)
Proof Strategies
o the structure of formal proofs
o direct proof, proof by counter example
o proof by contradiction, proof by cases
Functions and Sets
o functions (surjections, injections, inverses, composition)
o sequences & summations
o sets (power sets, Venn diagrams and tables, Cartesian product)
o set operations (complement, union, intersection, difference)
o cardinality and countability
Algorithms and Algorithm Analysis
o function growth & big-oh notation
o integer division, modulo
o primes and greatest common divisor
Number Systems & Mathematical Induction
o binary, octal, hexadecimal conversions and operations
o standard, strong and structural induction
o proving recursive algorithms by induction
Basics of Counting
o sum and product rule, rule of falling powers
o inclusion/exclusion and pigeonhole principles
o permutations and combinations
Discrete Probability
o complements and unions of events
o binomial coefficients and Pascal's triangle
Relations & Recurrence Relations
o relations (reflexivity, symmetry, transitivity)
o recursive definitions & recurrence relations

Grading Policy
                                    A   93%
                                    A-  90%
    10 HW/Labs...10%                B+  87%
    10 Quizzes...60%                B   83%
    Final Exam...30%                B-  80%
                                    C+  77%
                                    C   70%
                                    C-  65%
                                    D+  60%
                                    D   50%
                                    D-  40%
                                    F  below 40% 
Estimated ABET Category Content
Math and Basic Sciences: 3 Credit Hours
Prepared By
Donna Meyers on October 17, 2013
Approved by CEE/CS Department on October 17, 2013.
Effective Fall 2013