## 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

Your final mark F in the paper will be calculated according to this formula:

**F = max(E, (2E + 0.5A + 0.2Q + 0.3T)/3)**

where:

- E is the Exam mark
- A is the Assignments mark
- T is the Tests mark
- Q is the Quizzes mark

and all quantities are expressed as percentages.

### Students must abide by the University’s Academic Integrity Policy

**Academic endeavours at the University of Otago are built upon an essential commitment to academic integrity.**

The two most common forms of academic misconduct are *plagiarism* and *unauthorised collaboration*.

#### Academic misconduct: **Plagiarism**

Plagiarism is defined as:

- Copying or paraphrasing another person’s work and presenting it as your own.
- Being party to someone else’s plagiarism by letting them copy your work or helping them to copy the work of someone else without acknowledgement.
- Using your own work in another situation, such as for the assessment of a different paper or program, without indicating the source.
- Plagiarism can be unintentional or intentional. Even if it is unintentional, it is still considered to be plagiarism.

All students have a responsibility to be aware of acceptable academic practice in relation to the use of material prepared by others and are expected to take all steps reasonably necessary to ensure no breach of acceptable academic practice occurs. You should also be aware that plagiarism is easy to detect and the University has policies in place to deal with it.

#### Academic misconduct: **Unauthorised Collaboration**

Unauthorised Collaboration occurs when you work with, or share work with, others on an assessment which is designed as a task for individuals and in which individual answers are required. This form does not include assessment tasks where students are required or permitted to present their results as collaborative work. Nor does it preclude collaborative effort in research or study for assignments, tests or examinations; but unless it is explicitly stated otherwise, each student’s answers should be in their own words. If you are not sure if collaboration is allowed, check with your lecturer.

### 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?**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...

..., 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). (Comprehensive biography)### Sample problem

What is the*inverse*of 5 (mod 26)? That is, what integer

*k*(between 0 and 25) is such that

*k*= 1 (mod 26)?

The encoding was done using the transformation

*k*(E - 3) (mod 26)

*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.