everything.study
MATH 3825

Discrete Structures and Applications

0.5 credit · Undergraduate

Enumeration: elementary methods, inclusion and exclusion, recurrence relations, generating functions and applications. Graph theory and algorithms: connectivity, planarity, Hamilton paths and Euler trails. Error-correcting codes.

2022

Topics

  • 6.2; 6.4; Introduction, Pigeonhole and
  • 10.3 -10.6 Euler’s function
  • 11.1-11.4 binomial numbers; unordered selections
  • 11.5-11.7; sieve principal; designs and t-designs
  • 12.3- 12. 4; Multinomial numbers
  • 25.1 - 25.3 power series and properties
  • 25.4 - 25.6 Generating functions; homogenous and
  • Nov. 4 26.1-26.2 partitions and diagrams; conjugate
  • 15.1-15.6 Graphs; isomorphism; valency
  • Course notes; Planar graphs; Euler’s theorem
  • 24.1 -24.2 words, codes and errors; Linear codes
  • Dec. 1 24.3 - 24.4 construction and error correction
  • 27.1-6 Symmetry and counting; course review

Readings

  • “Discrete Mathematics” by Norman L. Biggs (Oxford Science Publications, 2nd edition).

Prerequisites & course information

Precludes additional credit for MATH 3805 (no longer offered), and MATH 3855 and COMP 3805 . Prerequisite(s): MATH 2108 or MATH 3101 . Lectures three hours a week, tutorial one hour a week.

Sources