| |
Jan 15, 2025
|
|
|
|
|
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 (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)
Coordinator
Karl David
Add to Portfolio (opens a new window)
|
|
Skip to Main Content
