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