Offered Summer 2019: Math 503/503G Applied Discrete Mathematics

SUMMER 2019
MATH 503/503G: APPLIED DISCRETE MATHEMATICS (3 credit hours)
This course is entirely online and will run from 6/3/19 through 7/26/19.
Prerequisites: MT200 (introduction to writing mathematical proofs) or equivalent and MT357 (proof-based introduction
to linear algebra) or equivalent. Previous coursework in discrete mathematics would be helpful but is not required.
Note: When taken as MT503, this course will count as a list B elective in the mathematics major.
COURSE DESCRIPTION:
An introduction to topics that frequently arise in applications of discrete mathematics in bioinformatics, computer science, and
digital communications technology. The course will be divided into four modules described below: Enumeration, Recurrence
Relations, Graph Theory, and Coding Theory. Each module will start with a short video introduction, a description of the
learning objectives, reading assignments, and link to a blog where online discussions will take place. The reading assignments
will come from lecture notes that I post and from the text. Online discussion will center around questions posed in the lecture
notes. Each module will conclude with a set of problems that you work on individually and submit to me for grading. Your
participation in the group discussion will count for 50% of your grade and the individual homework assignments will count
for 50% of your grade.
Text: Combinatorics: Topics, Techniques, Algorithms, Peter J. Cameron, Cambridge Univ. Press. Additional course notes
will be made available via Blackboard.
Enumeration
• Permutations, combinations, inclusion/exclusion, Pigeonhole Principle, binomial identities, multinomial coefficients,
and generalized binomial coefficients.
• Derangements, partitions, Catalan and Bell numbers, Stirling numbers of the first and second kind.
• Counting selections, ordered or unordered, with or without replacement, from multi-sets.
Recurrence Relations
• Linear and nonlinear recurrence relations.
• Solution of homogeneous, linear recurrence relations with constant coefficients using eigenvalues and eigenvectors of
linear transformations.
• Solution of recurrence relations using ordinary and exponential generating functions.
Graph Theory
• Directed and undirected graphs, basic definitions/results.
• Eulerian and Hamiltonian cycles, trees, graph coloring.
• The mathematics of Google’s page ranking algorithm.
Coding Theory
• Linear and nonlinear block codes, basic definitions/results.
• Bounds on the size of a code.
• Erasure codes. (Used in internet and cell-phone communications.)
For more information, see Prof. Michael Adams, VH2148, mjadams@truman.edu.