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 integrity means being honest in your studying and assessments. It is the basis for ethical decision-making and behaviour in an academic context. Academic integrity is informed by the values of honesty, trust, responsibility, fairness, respect and courage.
Academic misconduct is seeking to gain for yourself, or assisting another person to gain, an academic advantage by deception or other unfair means. The most common form of academic misconduct is plagiarism.
Academic misconduct in relation to work submitted for assessment (including all course work, tests and examinations) is taken very seriously at the University of Otago.
All students have a responsibility to understand the requirements that apply to particular assessments and also to be aware of acceptable academic practice regarding the use of material prepared by others. Therefore it is important to be familiar with the rules surrounding academic misconduct at the University of Otago; they may be different from the rules in your previous place of study.
Any student involved in academic misconduct, whether intentional or arising through failure to take reasonable care, will be subject to the University’s Student Academic Misconduct Procedures which contain a range of penalties.
If you are ever in doubt concerning what may be acceptable academic practice in relation to assessment, you should clarify the situation with your lecturer before submitting the work or taking the test or examination involved.
Types of academic misconduct are as follows:
Plagiarism
The University makes a distinction between unintentional plagiarism (Level One) and intentional plagiarism (Level Two).
- Although not intended, unintentional plagiarism is covered by the Student Academic Misconduct Procedures. It is usually due to lack of care, naivety, and/or to a lack to understanding of acceptable academic behaviour. This kind of plagiarism can be easily avoided.
- Intentional plagiarism is gaining academic advantage by copying or paraphrasing someone elses work and presenting it as your own, or helping someone else copy your work and present it as their own. It also includes self-plagiarism which is when you use your own work in a different paper or programme without indicating the source. Intentional plagiarism is treated very seriously by the University.
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 students answers should be in their own words. If you are not sure if collaboration is allowed, check with your lecturer..
Impersonation
Impersonation is getting someone else to participate in any assessment on your behalf, including having someone else sit any test or examination on your behalf.
Falsification
Falsification is to falsify the results of your research; presenting as true or accurate material that you know to be false or inaccurate.
Use of Unauthorised Materials
Unless expressly permitted, notes, books, calculators, computers or any other material and equipment are not permitted into a test or examination. Make sure you read the examination rules carefully. If you are still not sure what you are allowed to take in, check with your lecturer.
Assisting Others to Commit Academic Misconduct
This includes impersonating another student in a test or examination; writing an assignment for another student; giving answers to another student in a test or examination by any direct or indirect means; and allowing another student to copy answers in a test, examination or any other assessment.
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
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.
