Schools
 
Undergraduate
Maths
Papers
MATH272
 
Department

Search Maths/Stats: 
 
Advanced Search

Sample problem

Sandy delivers mail for a living and has a route of contiguous streets (i.e. each street in the route intersects with another street on the route). Being dedicated but not overly fond of exercise, Sandy wants to walk along each side of each street to deliver mail but manage to get back to the start without walking along any side of a street more than once. Is this possible? If so why? If it can be done, how does Sandy do it?

This problem can be tackled using an Euler graph.






Sample problem

At an airbase somewhere in Dingovia a multinational force has been put together comprising 5 pilots (Pam, Pat, Paul, Penny and Prunella) and 5 navigators (Nancy, Nate, Neil, Neville and Ninette). Viable aircrews are formed by pairing up pilots and navigators who speak a common language. The trouble is that, being multinational, not all of the pilots and navigators have a language in common. Given the following information about the languages each speaks, how many possible ways are there to form five viable aircrews?

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

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, 1912-1954, one of the great mathematicians of the 20th century. He contributed to many areas of mathematics including work on probability, computability, artificial intelligence, and group theory. During the war he was asked to join the Bletchley Park team which was attempting to break the German Enigma coding machine (see below). (Go here for a comprehensive biography.)





Sample problem

What is the inverse of 5 (mod 26)? That is, what integer k (between 0 and 25) is such that
5k = 1 (mod 26)?
A message M has been encoded to give the new message E:

The encoding was done using the transformation
E = 5M + 3 (mod 26) on each character. To decode the message the formula is
M = k(E - 3) (mod 26) where k is the integer mentioned above. 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.

MATH272 Discrete Mathematics

First Semester, 18 points
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.

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.

Main topics

  • Basic counting, inclusion-exclusion
  • Logical equivalence, rules of inference
  • Introduction to Graph Theory
  • Set theory
  • Congruences and elementary number theory
  • Cryptography

Prerequisites

MATH170 or HOD approval

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)

Lecturers

Professor Robert Aldred (room 233)

Lectures/Tutorials

Mondays, Wednesdays, and Thursdays at 4 pm. Not all the Thursday lecture times will be used.

There is a one-hour tutorial each week.

Internal Assessment

The internal assessment mark (A) is made up from:
50%: 10 weekly assignments
20%: four 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

The final mark F is calculated from:
F = max { E, (2E + A)/3 }
where E (exam mark) is out of 100, A (internal assessment) is out of 100.

The “max” corresponds to plussage: if your internal assessment mark is greater than your exam mark then it is combined in the proportion shown. If it is less then it is ignored and the exam mark itself is used.


Plagiarism

Students should make sure that all submitted work is their own. “Plagiarism is a form of dishonest practice. Plagiarism is defined as copying or paraphrasing another’s work and presenting it as one’s own” (University of Otago Calendar). In practice this means that plagiarism includes any attempt in any piece of submitted work (e.g. an assignment or test) to present as one’s own work the work of another (whether of another student or a published authority). Any student found to be responsible for plagiarism in any piece of work submitted for assessment shall be subject to the University’s dishonest practice regulations which may result in various penalties, including forfeiture of marks for the piece of work submitted, a zero grade for the paper, or in extreme cases exclusion from the University. The University of Otago reserves the right to use plagiarism detection tools.

While we strive to keep details as accurate and up-to-date as possible, information given here should be regarded as provisional. Individual lecturers will confirm teaching and assessment methods.