# Module MA2C03: Discrete Mathematics

Credit weighting (ECTS)
10 credits
Semester/term taught
Michaelmas and Hilary terms 2015-16
Contact Hours
22 weeks, 3 lectures including tutorials per week
Lecturer
Prof. Andreea Nicoara and Prof. David Wilkins
Learning Outcomes
On successful completion of this module, students will be able to
• justify, with reasoned logical argument, basic properties of mathematical objects that are specified as sets, relations on sets, functions between sets, and/or monoids;
• analyse simple context-free grammars to determine the formal languages that they generate, and construct specifications of context-free grammars and finite state machines that generate and/or determine formal languages, given specifications of such formal languages;
• recognize, identify and justify properties of undirected graphs that are networks consisting of vertices together with edges joining pairs of vertices;
• apply standard algorithms in order to determine spanning trees in connected graphs;
• determine solutions to certain types of homogeneous and inhomogeneous linear ordinary differential equations of degree at least two, where the coefficients of the differential equation are constants and the forcing function is typically constructed from polynomial, exponential and/or trigonometric functions;
• apply procedures founded in the algebra of vectors in three-dimensional space in order to solve simple geometrical problems;
• calculate quantities in modular arithmetic using methods, justified on the basis of theorems explicitly presented and proved within the module, that have relevance to the implementation of public key cryptographic systems such as the Rivest-Shamir-Adelman (RSA) public key cryptosystem.
Module Content
Specific topics addressed in this module include the following:
• The Principle of Mathematical Induction
• Sets, Relations and Functions
• Introduction to Abstract Algebra
• Introduction to Formal Languages and Context-Free Grammars
• Introduction to Graph Theory
• Algorithms for computing Minimal Spanning Trees
• Spanning Trees in Connected Graphs
• Ordinary Differential Equations
• Vectors
• Introduction to Number Theory and Cryptography
Lecture notes, assignments, worked solutions to problems from previous years and further information relevant to the module are available from the module webpage at http://www.maths.tcd.ie/~dwilkins/Courses/MA2C03/.
Module Prerequisite
Module CS1001 (Mathematics I), or an equivalent module developing the necessary mathematical skills in areas such as calculus and linear algebra.
Assessment Detail
This module will be examined in a 3 hour examination in Trinity term. Also students should complete a small number of assignments during the academic year. The final grade at the annual examination session will be a weighted average over the examination mark (90%) and the continuous assessment mark (10%). The final grade at the supplemental examination session will be wholly determined by the supplemental examination paper.