
MA2C03  Discrete Mathematics
Lecture Notes for MA2C03 in Hilary Term 2016
Dr. David R. Wilkins

Annual Examination  Hilary Term 2016
Lecture Notes  Hilary Term 2016
Additional Problems  Hilary Term 2016
Slides for Individual Lectures
 Lecture 32
(January 20, 2016)
 This lecture reviewed basic definitions and concepts
of graph theory, and revised the definitions and basic
properties of forests and trees.
 Lecture 33
(January 20, 2016)
 This lecture discussed spanning trees in connected
graphs. The lecture began with a proof that every
connected graph contains a spanning tree. A concrete
algorithm for finding such a spanning tree by
successively breaking circuits was discussed. Then
an alternative algorithm to find a spanning tree
through successive enlargement of acyclic subgraphs
was presented, and an example of the application of
algorithm was worked through in detail.
 Lecture 34 (January 22, 2016)
 This was an unscripted “chalk and talk“
tutorial discussing an old examination question
concerning graph theory
(Mathematics 2BA1, Annual Examination 2007, Q6)
 Lecture 35
(January 27, 2016)
 This lecture defined cost functions on edge
sets of undirected graphs, and defined the concept
of a minimal spanning tree for a connected graph.
The lecture then described Kruskal's Algorithm
for constructing a minimal spanning tree for
a connected graph.
 Lecture 36
(January 27, 2016)
 This lecture began with a discussion of issues
related to NPcompleteness and computational
intractibility, outlining the discussion of the
Bandersnatch Problem in the opening
chapter of
Computers and Intractability by Michael Garey and
David S. Johnson. (The discussion of
Computers and Intractability is not
included in the notes for the lecture.)
The lecture continued with an example of the
application of Kruskal's Algorithm to generate
a minimal spanning tree for a given connected
graph.
 Lecture 37 (January 29, 2016)
 This was an unscripted “chalk and talk“
tutorial discussing an old examination question
concerning sets and relations
(Mathematics 2BA1, Annual Examination 2009, Q1, parts (a) and (b)).
 Lecture 38
 The lecture began with a detailed review of the
example of the application of Kruskal's Algorithm
discussed in Lecture 36. The lecture was completed
with a general proof of the result that application
of Kruskal's Algorithm always results in a
minimal spanning tree.
 Lecture 39
 This lecture discussed Prim's algorithm for finding
a minimal spanning tree in a connected graph, where
a cost function is defined on the edges of that
connected graph. The lecture begin with a specific
example and ended with a proof that the spanning
tree generated by Prim's Algorithm is indeed minimal.
 Lecture 40 (February 5, 2016)
 This was an unscripted “chalk and talk“
presentation. Much of the presentation was a review
of the proof of the correctness of Prim's Algorithm.
This was followed by an example of the application
of Prim's Algorithm.
 Lecture 41
 This lecture introduced the basic concept and
formalism for vectors in three dimensional space,
covering displacement and position vectors,
the parallelogram law of vector addition,
and the operation of multiplicationbyscalars.
 Lecture 42
 This lecture discussed linear combinations
of vectors in threedimensional space, linear
independence and dependence. In particular,
a theorem was proved showing that, given
three linearly independent vectors in Euclidean
space, any threedimensional vector can be
expressed as a linear combination of the
three given linearly independent vectors.
The concept of a real vector space was defined.
Standard examples included vectors in
threedimensional space and in the plane,
and the space of polynomials with real coefficients
whose degree does not exceed some fixed value m.
 Lecture 43 (February 12, 2016)
 This was an unscripted “chalk and talk“
tutorial discussing an old examination question
(Question 4 on the 2BA1 examination at the annual
examination in Trinity Term 2009).
concerning finite state automata and regular grammars.
 Lecture 44
 This lecture began with a review of the definition
and basic properties of vectors in threedimensional
space, covering a selection of material developed
at more length in Lectures 41 and 42. The definition
of a real vector space was discussed, and also the
example of a real vector space provided by the set
of all polynomials with real coefficients whose
degree does not exceed some fixed positive
integer m. (The material in vector spaces
was introduced at the end of Lecture 42, and is
therefore included in the notes for that lecture.)
The lecture concluded with a discussion of lengths
of vectors, emphasizing how the formula that defines
the length of a vector ensures that the length of
a displacement vector between two points of
threedimensional space is the Euclidean distance
between those points determined through two
appplications of Pythagoras's Theorem.
 Lecture 45
 This lecture began with the definition of the
scalar product, followed by a definition of the
formula u.v = uv cos θ
that expresses the scalar product of vectors u
and v in threedimensional Euclidean space
in terms of the lengths of these vectors and the angle
θ between them. The lecture concluded with a
sequence of examples containing applications of scalar
products in geometrical problems.
 Lecture 46 (February 19, 2016)
 This was an unscripted “chalk and talk“
presentation in which an example of a connected graph
was given, and minimal spanning trees were determined
using Kruskal's Algorithm and Prim's Algorithm. Other
properties of this graph were discussed. In particular
there could not exist any Eulerian circuit or Hamiltonian
circuit for the given graph.
 Lecture 47
 This lecture introduced the vector product of two vectors
in threedimensional Euclidean space. It was shown that
the vector product u × v of vectors
u and v is perpendicular to both u
and v and has length u v sin θ.
 Lecture 48 (February 24, 2016)
 This was an unscripted “chalk and talk“
presentation to show that, up to multiplication by a
constant scalars, the vector product sending a pair of
vectors u and v to their vector product
u × v is the unique product sending
a pair of vectors to a single vector that satisfies the
identities
(s u + t v ) × w
= s u × w + t v × w
u × (s v + t w)
= s u × v + t u × w
and is consistent with invariance under rotations of Euclidean
space, so that
(R u) × (R v) = R (u × v)
for all rotations R and for all threedimensional vectors
u and v.
 Lecture 49
 This lecture began by explaining how vector and scalar products
can be used in order to determine the equation of the
plane in threedimensional space that passes through
three given points. The lecture continued with a discussion
of basic properties of scalar triple products and
vector triple products, and included a proof of the
vector triple product identity
u × (v × w)
= (u . w) v
 (u . v) w.
 Lecture 50
 This lecture introduced first order differential equations
and presented the general solution of homogeneous
and inhomogeneous linear first order differential equations
with constant coefficient, where the forcing function
for the inhomogeneous equation takes one of the following
three forms: p + qx + rx^{2},
(p + qx) e^{mx},
p cos kx + q sin kx.
 Lecture 51
 This lecture covered the theory of homogeneous
linear second order differential equations with
constant coefficient, deriving the general solution
in cases where the auxiliary polynomial has real
roots, and also in the case where the first derivative
term is absent.
 Lecture 52
 This lecture completed the presentation of
the theory of homogeneous second order linear
differential equations with constant coefficients.
 Lecture 53
 This lecture reviewed the standard solutions
of homogeneous linear second order differential
equations with constant coefficients, and verified
that the standard solutions did indeed satisfy
the equation. The lecture continued with the
solution of inhomogeneous linear second order
differential equations with constant coefficients
in the case where the forcing function is a
quadratic polynomial function.
 Lecture 54
 The lecture obtained the solution of
inhomogeneous homogeneous linear second order
differential equations with constant coefficients
in the cases where the forcing function is a
first degree polynomial multiplied by an
exponential function and in the case where it
is a linear combination of a sine and cosine
function
 Lecture 55
 This lecture provided a brief introduction
to harmonic analysis and Fourier series.
The case of a function expressible on a
bounded interval as a sum of a finite number
of ``harmonics'' represented as sine or
cosine functions was first considered, and
formulae for the Fourier coefficients determining
the contributions of the various harmonics were
obtained. More general functions were then
considered and it was shown that, where an
integrable function (with finitely many
discontinuities) is approximated by the
first 2N + 1 terms of the Fourier
series, the integral of the square of
the difference between the given function
and approximating function is minimized
amongst approximating functions of the
same type.
 Lecture 56
 This lecture was a review of results from
elementary number theory.
 Lecture 57
 This lecture included a discussion of
methods for computing powers in module arithmetic.
 Lecture 58
 This lecture included Fermat's Little Theorem,
the Chinese Remainder Theorem, and the
mathematics underlying RSA cryptosystems.
 Lecture 59
 This lecture completed the discussion
of the RSA cryptographic system, explaining
in particular why it is possible to
perform the relevant calculations in
modular arithmetic using large prime
numbers in reasonable time.
 Lecture 60 (April 6, 2016)
 This was an unscripted “chalk and talk“
presentation discussing problems examined at the
Annual Examination 2015.
 Lecture 61 (April 6, 2016)
 This was an unscripted “chalk and talk“
presentation discussing problems examined at the
Annual Examination 2015.
 Lecture 62 (April 8, 2016)
 This was an unscripted “chalk and talk“
presentation discussing problems examined at the
Annual Examination 2015.
Further Resources
See the Internet
Resources page, which includes links to videos and
lecture slides available elsewhere on the Internet.
Module webpage: MA2C03
Lecture notes for undergraduate courses
Dr. David R. Wilkins
School of Mathematics,
Trinity College,
Dublin 2, Ireland
dwilkins@maths.tcd.ie