CMPS 2120 Discrete Structures
Catalog Description
CMPS 2120 Discrete Structures (4 units)
Discrete structures and applications in computer science. Provides an introduction to proof techniques, propositional and predicate logic, functions, relations, sets, big-oh notation, counting techniques, summations, recursive definitions, recurrence relations, discrete probability and simple circuit logic. CMPS 2010 or CMPS 2020 with a grade of C- or better; MATH 1040 or MATH 1050
Prerequisites by topic
Polynomial, exponential and logarithmic functions
Units and Contact Hours
4 semester units. 3 units lecture and 1 unit lab.
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 final exam.

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)
week 01
o predicate logic with single and nested quantifiers
o predicate logic operations
 week 02
o use of inference rules to analyze arguments
o syllogisms and fallacies
week 03
o the structure of formal proofs
o direct proof, proof by counter example
o proof by contradiction, proof by cases
 week 04
o functions (surjections, injections, inverses, composition)
o sequences & summations
week 05
o sets (power sets, Venn diagrams and tables, Cartesian product)
o set operations (complement, union, intersection, difference)
o cardinality and countability
week 06
o algorithms and algorithm analysis
o function growth & big-oh notation
week 07
o integer division, modulo
o primes and greatest common divisor
week 08
o positional number systems
o binary, octal, hexadecimal conversions and operations
week 09
o standard strong and structural induction
o proving recursive algorithms by induction
week 10
o basic combinatorics
o sum and product rule, rule of falling powers
o inclusion/exclusion and pigeonhole principles
o permutations and combinations
o binomial coefficients and Pascal's triangle
week 11
o introduction to discrete probability
o complements and unions of events
 week 12
o properaties of relations (reflexivity, symmetry, transitivity)
o relation composition
week 13
o recursive definitions
o solving recurrence relations
week 14
o Boolean circuits
o logic gates and logic diagrams
 week 15

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