620-353 Discrete Mathematics

Any two 200-level subjects from the Department of Mathematics and Statistics. Computer Science 433-253 may be substituted for one of these subjects.

Discrete mathematics is concerned with the study of objects which are finite in number and typically computable. At a computational level one seeks efficient algorithms and formulas for the listing and counting of the objects. Theory provides a way to these algorithms and formulas, and further provides links between seemingly disparate areas of discrete mathematics.

The main topics to be covered are enumeration and listings; permutations; designs, codes and finite geometry; patterns and Ramsey theory; and physical combinatorics. Designs are relevant to statistics, codes to communication engineering, patterns and Ramsey theory to computer science, and physical combinatorics to mathematical physics.

A common theme throughout the course will be the constructive aspect of the subject, whereby algorithms and formulas are formulated for the enumeration and listing of discrete objects. Through studying this course students will gain an appreciation of the practical use of theoretical analysis, and will also gain experience in the implementation of algorithms.

Up to 48 pages of written assignments due during semester (20%); a 3-hour written examination in the examination period (80%).