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).
Type
Required for CE and CS.
Required Textbook
None.
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.
Coordinator
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
Logic
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 ...)
 week01-02
Proof Strategies
o the structure of formal proofs
o direct proof, proof by counter example
o proof by contradiction, proof by cases
 week03
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
week04
Algorithms and Algorithm Analysis
o function growth & big-oh notation
o integer division, modulo
o primes and greatest common divisor
week05
Number Systems & Mathematical Induction
o binary, octal, hexadecimal conversions and operations
o standard, strong and structural induction
o proving recursive algorithms by induction
week06
Basics of Counting
o sum and product rule, rule of falling powers
o inclusion/exclusion and pigeonhole principles
o permutations and combinations
week07-08
Discrete Probability
o complements and unions of events
o binomial coefficients and Pascal's triangle
week09
Relations & Recurrence Relations
o relations (reflexivity, symmetry, transitivity)
o recursive definitions & recurrence relations
week10

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
Approval
Approved by CEE/CS Department on October 17, 2013.
Effective Fall 2013