MATH220-24S1 (C) Semester One 2024

Discrete Mathematics and Cryptography

15 points

Details:
Start Date: Monday, 19 February 2024
End Date: Sunday, 23 June 2024
Withdrawal Dates
Last Day to withdraw from this course:
  • Without financial penalty (full fee refund): Sunday, 3 March 2024
  • Without academic penalty (including no fee refund): Sunday, 12 May 2024

Description

Discrete mathematics underpins many areas of modern-day science. This course is an introduction to graph theory and cryptography, two central topics in discrete mathematics.

Discrete mathematics underpins many areas of modern-day science. This course is an introduction to graph theory and cryptography, two central topics in discrete mathematics, each having fundamental links to many branches of science. Graph theory underlies the solution to many problems in a variety of disciplines including operations research and computational biology. Cryptography has applications to all communications security, from state security to online banking and mobile phone conversations. This course is designed for mathematics and computer science students.

Topics covered:

Cryptography: Basic ideas and terminology of cryptography. Shift and affine ciphers. One-time pads. Basic properties of the integers. Euclid’s algorithm. Modular arithmetic. Public key ciphers. The RSA, Rabin and ElGamal ciphers. Diffie-Hellman key exchange. Arithmetic of polynomials over finite fields. Constructing finite fields. Linear and non-linear shift registers.

Graph theory: Concepts and terminology of graphs. Eulerian and Hamiltonian graphs. Complexity, polynomial-time and exponential-time algorithms. Chromatic polynomials. Matchings and Hall’s Marriage Theorem. The Greedy Algorithm. Directed graphs. Network flows.

Learning Outcomes

  • At the end of the course, students will:

  • Be familiar with  some of the old and modern cryptographic schemes and have developed the necessary mathematics to understand and analyse them.
  • Have an understanding of some topics in graph theory with an emphasis on graph algorithms and proof techniques.
    • University Graduate Attributes

      This course will provide students with an opportunity to develop the Graduate Attributes specified below:

      Critically competent in a core academic discipline of their award

      Students know and can critically evaluate and, where applicable, apply this knowledge to topics/issues within their majoring subject.

      Employable, innovative and enterprising

      Students will develop key skills and attributes sought by employers that can be used in a range of applications.

      Globally aware

      Students will comprehend the influence of global conditions on their discipline and will be competent in engaging with global and multi-cultural contexts.

Prerequisites

Restrictions

MATH221, MATH231

Timetable 2024

Students must attend one activity from each section.

Lecture A
Activity Day Time Location Weeks
01 Monday 14:00 - 15:00 E5 Lecture Theatre
19 Feb - 31 Mar
22 Apr - 2 Jun
Lecture B
Activity Day Time Location Weeks
01 Friday 13:00 - 14:00 Meremere 108 Lecture Theatre
19 Feb - 31 Mar
22 Apr - 2 Jun
Lecture C
Activity Day Time Location Weeks
01 Thursday 09:00 - 10:00 A3 Lecture Theatre
19 Feb - 31 Mar
22 Apr - 2 Jun
Tutorial A
Activity Day Time Location Weeks
01 Monday 12:00 - 13:00 Jack Erskine 235
26 Feb - 31 Mar
22 Apr - 2 Jun
02 Monday 13:00 - 14:00 Jack Erskine 235
26 Feb - 31 Mar
22 Apr - 2 Jun
03 Tuesday 13:00 - 14:00 Meremere 409
26 Feb - 31 Mar
22 Apr - 2 Jun
04 Thursday 15:00 - 16:00 Ernest Rutherford 225
26 Feb - 31 Mar
22 Apr - 2 Jun
05 Tuesday 14:00 - 15:00 Meremere 409
26 Feb - 31 Mar
22 Apr - 2 Jun

Examination and Formal Tests

Test A
Activity Day Time Location Weeks
01 Monday 19:00 - 20:15 C2 Lecture Theatre
22 Apr - 28 Apr
02 Monday 19:00 - 20:15 Rehua 329
22 Apr - 28 Apr

Course Coordinator

Brendan Creutz

Lecturer

Jeanette McLeod

Assessment

Assessment Due Date Percentage 
Assignments 25%
Test 25%
Final Examination 50%


To obtain a passing grade in this course you must pass the course as a whole (which requires an overall mark of 50% or more) and score at least 40% in the final exam.

Textbooks / Resources

Recommended Reading

Buchmann, Johannes; Introduction to cryptography ; 2nd ed; Springer, 2004.

Clark, John. , Holton, Derek Allan; A first look at graph theory ; World Scientific, 1991.

Copies of these books will be on reserve in the Engineering and Physical Sciences Library. Also, there are a number of other good books on cryptography and graph theory in the library.

Indicative Fees

Domestic fee $847.00

International fee $4,988.00

* All fees are inclusive of NZ GST or any equivalent overseas tax, and do not include any programme level discount or additional course-related expenses.

For further information see Mathematics and Statistics .

All MATH220 Occurrences

  • MATH220-24S1 (C) Semester One 2024