Mar 29, 2024  
2017-2018 Undergraduate Academic Catalog 
    
2017-2018 Undergraduate Academic Catalog [ARCHIVED CATALOG]

Add to Portfolio (opens a new window)

MA 3320 - Discrete Mathematics II

3 lecture hours 0 lab hours 3 credits
Course Description
This course continues the introduction of discrete mathematics begun in MA 2310 . Emphasis is placed on concepts applied within the field of computer science. Topics include logic and proofs, number theory, counting, computational complexity, computability, and discrete probability. (prereq: MA 2310 , MA 262 )
Course Learning Outcomes
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

Prerequisites by Topic
  • Predicate logic
  • Recurrence relations
  • Fundamental structures
  • Continuous probability

Course Topics
  • 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

Coordinator
Chunping Xie



Add to Portfolio (opens a new window)