CE16 H	Honors Applied Discrete Math

Catalog copy 

CE16H. Discrete Mathematics (honors). W An honors version of CMPE 16,
 this is 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, inclusion-exclusion, summation,
 recurrences, and generating functions.  Examples are drawn from
 computer science and computer engineering.  May not be repeated for
 credit.  Students may not get credit for both CMPE 16 and CMPE 16H.
 Prerequisite: permission of instructor.


Explanation of prerequisites

CMPE 16H is intended as an honors version of CMPE 16 (Applied Discrete
Math).  It will be taught once a year to a relatively small group of
students (30-60).  Students register for CMPE16,
then petition to be accepted into CMPE16H, providing informmation
about their math backgrounds, scores and grades.  Those not accepted
into CMPE16H will remain in CMPE16

All the topics of CMPE 16 need to be covered in 16H, but at a somewhat
faster pace and in more depth.

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. More depth on inductive proofs
2. Trees and induction on trees.
3. Solving recurrence relations.
4. Generating functions.
5. Inclusion-exclusion principle for counting.
6. More summations involving binomial coefficients and factorials.
7. Applications of number theory for cryptography.
8. Representations of numbers in computers
9. Logic minimization
10. Summations using Knuth's k^n-rising, k^n-falling notation.
11. Database applications of relations (overlaps with CMPS 180).
12  Closure of relations.
13. Partial orders.
14. More formal induction over well-founded relations.

Text

Rosen, "Discrete Mathematics and its Applications", McGraw-Hill, 1999.
Because students will not know until after the second day of class
whether they are in 16 or 16H, the two courses will have to use the
same textbook.  There is plenty of material in the book that is not
currently covered in CMPE 16, so there will be no difficulty in
teaching an honors course from the book.


Prepared by Kevin Karplus, 4/02