CE16 Applied Discrete Math

Catalog copy 

CE16. Applied Discrete Mathematics. F, W, S. An introduction to
applications of discrete mathematical systems. Topics include sets,
functions, relations, graphs, trees, switching algebra, first order
predicate calculus, mathematical induction, permutations,
combinations, summation, and recurrences. Examples are drawn from
computer science and computer engineering.  
Prerequisites: MATH 002B or MATH 003 or Mathematics Placement Exam (40
or higher) or either MATH 019A or MATH 011A or ECON 011A or either
ENGR 003A or ENGR 003


Explanation of prerequisites

CMPE 16 is a freshmen-level mathematics course, but it requires
minimal mathematical sophistication.  

Required Skills to pass the course
1. Logic and proofs using propositional equivalences
2. Sets and operations and proofs about sets
3. Functions and Relations
4. Proofs by mathematical induction
5. Combinatorics including permutations and combinations
6. Discrete probability
7. Boolean Algebra

Core topics (must be taught)
1. Logic: propositions, proofs using propositional equivalences.
2. Predicates, quantifiers, sets and set operations: union,
    intersection, difference
3. Functions and relations, sequences and summations.
4. Modular arithmetic, mathematical induction.
5. Mathematical induction, recursive definitions.
7. Counting arguments, pigeonhole principle, permutations and combinations.
8. Discrete probability, generalized permutations and
     combinations, recurrence relations.
9. Introduction to solving recurrence relations, n-ary relations.
10. Boolean algebra.


Optional topics
1. Trees and induction on trees.
2. Generating functions.
3. Inclusion-exclusion principle for counting.
4. More summations involving binomial coefficients and factorials.

Text
Rosen, "Discrete Mathematics and its Applications", McGraw-Hill, 1999.


Prepared by Kevin Karplus, 4/02