Study Guide for the Discrete Mathematics Comprehensive Exam

Coordinator: William Shoaff, .

Topics:

Boolean Algebras
  • Example Algebras: Logic Gates, Propositions, Power Set of a Set
  • Defining Properties of a Boolean Algebra
  • Duality Principle
Counting
  • Permutations
  • Combinations
  • Pigeonhole Principle
  • The Inclusion-Exclusion Rule
  • The Product Rule for Counting
  • The Sum Rule for Counting
Functions
  • Common Functions: Logarithms, Exponentials, Polynomials, Floor and Ceiling, etc.
  • Composition of Functions
  • Inverses of Functions
  • One-to-one Functions
  • Onto Functions
  • Rates of Growth: Big-O Big-Omega, Big-Theta
Graphs
  • Connectivity
  • Directed and Undirected Graphs
  • Euler and Hamilton Paths
  • Graph Coloring
  • Graph Isomorphisms
  • Planar Graphs
  • Weighted Graphs
Logic
  • Propositional Logic
  • Logical Connectives: AND, OR, NOT, IMPLIES, XOR, NAND, etc.,
  • Truth Tables
  • Validity
  • Predicate Logic
  • Quantifiers
Proof Techniques
  • Rules of Inference, e.g., Modus Ponens and Modus Tollens
  • Direct Proofs
  • Proofs by Counterexample
  • Proof by Contradiction
  • Proofs by Mathematical Induction
Recursion
  • Recursive Definitions
  • Recurrence Equations
Relations
  • Antisymmetry
  • Equivalence Relations
  • Orders: Partial, Total, Strict, Hasse Diagrams
  • Reflexivity
  • Representation as Graphs
  • Symmetry
  • Transitivity
Sets
  • Cardinality
  • Cartesian Products
  • Countable and Uncountable Sets
  • The Power Set of a Set
  • Set Operations: Union, Intersection, Complement
  • Venn diagrams
Summations
  • Arithmetic Summations
  • Geometric Summations
  • Summations Involving Common Numbers: Harmonic Numbers, Binomial Coefficients
Trees
  • Binary and n-ary Trees
  • Tree Traversals
  • Spanning Trees
References:
  1. A Course On Mathematics For Computing,
    William Shoaff
    http://cs.fit.edu/~wds/CourseOnComputing/Material_files/Book.pdf
  2. Discrete Mathematics and Its Applications,
    Kenneth H. Rosen, 5th Edition,
    McGraw-Hill, ISBN 0-07-242434-6,
    http://www.mhhe.com/rosen
  3. A Short Course in Discrete Mathematics
    by Edward A. Bender and S. Gill Williamson,
    Dover, ISBN 0-486-43946-1.
  4. Mathematics for Algorithm and Systems Analysis
    by Edward A. Bender and S. Gill Williamson,
    Dover, ISBN 0-486-44250-0.
  5. Schaum's Easy Outlines: Discrete Mathematics,
    Seymour Lipschutz and Marc Lipson,
    McGraw-Hill, ISBN, 0-07-139877-5