Skip to main content

Trinity College Dublin, The University of Dublin

Trinity Menu Trinity Search

School of Mathematics

You are here Courses > Undergraduate > Courses & Modules

Module MAU22C00 Discrete Mathematics

Credit weighting (ECTS)
10 credits
Semester/term taught
Michaelmas and Hilary terms 2020-21
Contact Hours
22 weeks, 3 lectures plus one tutorial per week
Lecturer
Prof. Andreea Nicoara
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;
  • figure out whether a set is finite, countably infinite or uncountably infinite and apply these ideas to the study of formal languages;
  • construct a Turing machine that recognises a given formal language;
  • understand variants of Turing machines, the classes of Turing-decidable and Turing-recognisable languages, and why not all formal languages are Turing-recognisable.
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
  • Countability of Sets
  • Turing Machines
Module Prerequisite
Modules CSU11001 (Mathematics I) and CSU11002 (Mathematics II) or equivalent modules developing the necessary mathematical skills in areas such as calculus, linear algebra, first order logic, and set theory.
Assessment Detail
This module will be examined in a 3 hour examination in Trinity term. Also, students should complete a number of assignments during the academic year, although no minimum level of engagement is specified. The final grade at the annual examination session will be a weighted average over the examination mark (70%) and the continuous assessment mark (30%). Re-assessments if required will consist of 100% exam.