MA 3320 - Discrete Mathematics II

• 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
• Continuous probability

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