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

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