# MATH272 Discrete Mathematics

Graph theory and algorithms; combinatorial counting techniques; sets, relations, modular arithmetic and applications to cryptography. There will be an emphasis on both proof techniques and practical algorithms.

Paper title Discrete Mathematics MATH272 Mathematics 0.1500 18 points First Semester \$779.70 \$3,307.50
Prerequisite
MATH 170
Schedule C
Arts and Music, Science

## Timetable

### First Semester

Location
Dunedin
Teaching method
This paper is taught On Campus
Learning management system
Other

View 2014 timetable information in the Web Timetable Viewer

Graph theory and algorithms; combinatorial counting techniques; sets, relations, modular arithmetic and applications to cryptography. There will be an emphasis on both proof techniques and practical algorithms.

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 is not finalized, but it will include a selection from the following topics: combinatorics, logic, graph theory, set theory, number theory.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.

Paper title Discrete Mathematics MATH272 Mathematics 0.1500 18 points Not offered in 2015, expected to be offered in 2016 Tuition Fees for 2015 have not yet been set Tuition Fees for international students are elsewhere on this website.
Prerequisite
MATH 170 or MATH 103
Schedule C
Arts and Music, Science
Teaching staff
Professor Robert Aldred
View further information about MATH 272
Paper Structure
Main topics
• Basic counting, inclusion-exclusion
• Logical equivalence, rules of inference
• Introduction to graph theory
• Set theory
• Congruences and elementary number theory
• Cryptography
Textbooks
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)
Course outline
View course outline for MATH 272
Learning Outcomes
Students will learn how to formulate and test rigourous discrete mathematical concepts.
Eligibility
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.
Contact
maths@otago.ac.nz

## Timetable

### Not offered in 2015, expected to be offered in 2016

Location
Dunedin
Teaching method
This paper is taught On Campus
Learning management system
Other