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