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

*January 29, 2019*

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.