MA 3320 - Discrete Math II

• Upon successful completion of this course, the student will be able to:
  • Illustrate by examples proof by contradiction
  • Synthesize induction hypotheses and simple induction proofs
  • Apply the Chinese Remainder Theorem
  • Illustrate by examples the properties of primes
  • Calculate the number of possible outcomes of elementary combinatorial processes such as permutations and combinations
  • Identify a given set as countable or uncountable
  • Derive closed-form and asymptotic expressions from series and recurrences for growth rates of processes
  • Be familiar with standard complexity classes
  • Apply Bayes’ rule and demonstrate an understanding of its implications
  • Apply conditional probability to identify independent events

• Predicate logic
• Recurrence relations
• Fundamental structures

• Course introduction
• Proofs: direct proofs
• Proofs: proof by contradiction
• Number theory: factorability
• Number theory: properties of primes 
• Number theory: greatest common divisors and least common multiples
• Number theory: Euclid’s algorithm
• Number theory: Modular arithmetic
• Number theory: the Chinese Remainder Theorem
• Computational complexity: asymptotic analysis
• Computational complexity: standard complexity classes
• Counting: Permutations and combinations
• Counting: binomial coefficients
• Countability: Countability and uncountability
• Countability: Diagonalization proof to show uncountability of the reals
• Discrete probability: Finite probability spaces
• Discrete probability: Conditional probability and independence
• Discrete probability: Bayes’ rule
• Discrete probability: Random events
• Discrete probability: Random integer variables
• Discrete probability: Mathematical expectation