|
Mar 29, 2024
|
|
|
|
MA 3320 - Discrete Mathematics II3 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)
|
|