Transcript title

Discrete Mathematics II

Credits

4

Grading mode

Standard letter grades

Total contact hours

40

Lecture hours

40

Prerequisites

MTH 231.

Course Description

A second course in discrete mathematics. Builds on the topics of MTH231 including topics in combinatorics, mathematical proofs, probability, graph theory and number theory. Applications include cryptography and analysis of algorithms.

Course learning outcomes

1. Model and solve counting problems by applying properties of functions and techniques of combinatorics including problems involving indistinguishable items, repetition, and the principle of inclusion/exclusion.
2. Apply mathematical proof techniques in settings of number theory, graph theory, analysis of algorithms, and probability.
3. Calculate and interpret probabilities by applying principles of discrete probability, techniques of combinatorics and set theory.
4. Analyze graphs and apply techniques for identifying Euler and Hamiltonian paths, shortest paths, chromatic numbers, and isomorphic graphs.
5. Classify the growth of functions and the run-time of algorithms using Big O notation.
6. Apply principles of number theory including divisibility, modular arithmetic, modular congruences, and their applications to cryptography.

Content outline

1. Foundational Topics in Discrete Mathematics
   1. Proofs (direct, contraposition, contradiction, induction)
   2. Sets
   3. Basic Combinatorics
2. Advanced Combinatorics
   1. Permutations with non-distinct objects
   2. Repetition allowed combinations
   3. Inclusion/Exclusion
   4. Applications
3. Discrete Probability
   1. Basics of Discrete Probability
   2. Methods for Calculating Probability (probability theory)
   3. Conditional Probability and Bayes Theorem
   4. Expected Value
4. Algorithms
5. Number Theory
   1. Divisibility 
   2. Modular arithmetic
   3. Primes and GCD’s
   4. Representations of Integers and related Algorithms
   5. Modular Congruences
   6. Applications in Cryptography
6. Graph Theory
   1. Basics of Graph Theory
   2. Graph Isomorphisms
   3. Euler Paths
   4. Hamiltonian Paths
   5. Shortest Paths
   6. Planar Graphs
   7. Graph Coloring

Required materials

A textbook is required.

General education/Related instruction lists

• Science not Lab