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

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