MATH272 Discrete Mathematics
Second Semester |
Discrete Mathematics looks at problems that are associated with discrete rather than continuous situations. So the nature of the problems is quite distinct from those that are considered in a calculus paper because the important underlying set is the integers rather than the sets of real or complex numbers.
The curriculum includes a selection from the following topics: combinatorics, counting techniques, logic, graph theory, set theory, relations, number theory. There will be an emphasis on both proof techniques and practical algorithms.
Paper details
This paper provides an introduction to combinatorics, logic, graph theory, set theory, and number theory. It gives an opportunity to explore algorithms and proof, in a new environment, and is ideal for students majoring in Mathematics and Computer Science.
The combinatorics section covers counting basic but not simple sets. Starting from counting the number of ways that we can choose a subgroup of people from a given group we work up to counting sets with restrictions. For instance, in a factory only a certain number of people may be skilled to undertake a certain task. To count how many ways we can assign tasks to workers is non-trivial. We develop techniques to handle these problems.
Our introduction to logic covers truth tables, rules of inference and an algebraic approach to logic that generalizes to other situations. For instance the same rules that govern logic also govern electrical switching circuits.
The graphs we consider are simply vertices some (or all) of which are joined by edges. These can be used to model many things including airline routes. We look at several important ideas in graph theory, including algorithms. The content will include topics from: trees, Euler tours, Hamiltonian cycles, matchings and planar graphs. Proofs are given where appropriate.
The set theory topics include power sets, relations and functions.
The paper may also cover some elementary number theory and algebra relevant to the emerging science of cryptography, including Euclid’s algorithm, congruences and modular exponentiation, and some topics related to primes, including primality tests.
Potential students
This paper should be of interest to three main groups.
- The first covers anyone who has ever had an interest in puzzles of a mathematical nature. This is because the topics of the paper frequently come very close to the concepts often used in such puzzles.
- The second group is computer science students. Discrete mathematics ideas are useful in computer science especially where algorithms and computability are concerned.
- Finally, the paper should be of interest to mathematical majors and honours students. It provides a good foundation for other papers, both as background and in exposure to proof techniques.
Prerequisites
MATH170 or HoD approval
Main topics
- Basic counting, inclusion-exclusion
- Logical equivalence, rules of inference
- Introduction to Graph Theory
- Set theory
Required text
Discrete and Combinatorial Mathematics 5th edition by Ralph P. Grimaldi
Useful references
A First Look At Graph Theory, J Clark and D A Holton, World Scientific (1996)
Lecturer
Professor Robert Aldred (room 211A)
Lectures
Monday, Wednesday, and Thursday at 4 pm.
Not all the Thursday lecture times will be used.
Tutorials
One per week: Tuesday at 2 pm
Internal Assessment
The internal assessment is made up from:
50%: 9 weekly assignments
20%: three short Quizzes
30%: test
The Quizzes take place in normal contact time. You can check your marks by clicking on the Resources link at the top of this page.
Final mark
Sample problem

This problem can be tackled using an Euler graph.
Sample problem

Pilots:
Pam: English, Mandarin and Russian
Pat: French, German and Mandarin
Paul: German, Japanese, Polish and Hindi
Penny: Dutch and Spanish
Prunella: French, Mandarin and Slovak
Navigators:
Nancy: Dutch, German and Slovak
Nate: Mandarin, Polish and Russian
Neil: English, French and Spanish
Neville: Mandarin
Ninette: Mandarin and Hindi
Problems such as this can be solved using inclusion-exclusion principles and Rook polynomials.
Alan Turing...

Sample problem
What is the inverse of 5 (mod 26)? That is, what integer k (between 0 and 25) is such that
The encoding was done using the transformation
Select a value for k from the list below to see the effect of decoding. Only the correct value will produce an intelligible message.
3 11 15 17 21 23
The Enigma machine

The Enigma cypher was the backbone of German military and intelligence communications during the last world war. They thought it to be unbreakable, and not without good reason. Enigma’s complexity was bewildering. Messages were encrypted using a series of rotating wheels and electrical contacts. The rotors and wires of the machine could be configured in many, many different ways. The odds against anyone who did not know the settings being able to break Enigma were a staggering 150 million million million to one. There is a fascinating history of how the code was broken at Bletchley Park.