April 2007

## CSE 321: Discrete Structures

### Purpose:

Provide students with the definitions and basic tools for reasoning
about discrete mathematical objects useful for computer science and
engineering.

### Precondition Concepts:

- simple algorithms, data structures, and asymptotic analyses
- recursion
- definitions of elementary mathematical objects:

functions and relations on the reals and integers

### Precondition Abilities:

- facility with high school mathematics
- ability to understand simple programs

### Postcondition Concepts:

- propositional logic (and set theory)
- connectives
- truth assignments
- truth tables
- satisfiability and tautology
- equivalences, e.g. De Morgan's laws
- sets

- predicate logic
- quantifiers
- quantifier order
- interaction of quantifiers and connectives

- arithmetic
- divisibility
- primality and compositeness
- mod relation
- optional:
- unique factorization
- greatest common divisors and Euclidean algorithm
- modular arithmetic
- Chinese remainder theorem
- RSA

- methods of proof
- logical equivalences
- logical inference
- formal reasoning:
- indirect proof
- proof by contradiction
- proof methods involving quantifiers

- mathematical induction
- organization of an inductive proof
- course of values (strong) induction
- recursive definitions
- induction over recursive definitions
- optional:
- correctness of a simple program with loops

- counting
- sum and product rules
- power set
- permutations and combinations
- optional:
- pigeonhole principle
- countable/uncountable sets

- discrete probability
- sample spaces
- events
- probability distributions
- uniform distribution
- optional:
- conditional probability
- independence
- expected value
- linearity of expectation
- average case analysis of a simple program

- binary relations
- representations and connections with directed graphs
- properties: reflexivity, symmetry and antisymmetry, transitivity
- equivalence relations
- optional:
- partial orders
- closures of binary relations
- algorithms for closures

- undirected and directed graphs
- representations
- connectedness
- topics chosen from:
- isomorphism
- Euler tours
- Hamiltonian tours
- planarity
- coloring
- spanning trees

### Postcondition Abilities

- express simple mathematical concepts formally
- write simple proofs, including proofs by induction

### Postcondition Skills

- translate from English to predicate logic and vice versa