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

Annual Examination - Hilary Term 2016

• Notes regarding the Annual Examination 2016
• Some Sample Examination Questions - Annual Examination 2016

Lecture Notes - Hilary Term 2016

• Spanning Trees
• Vectors
• Ordinary Differential Equations
• Harmonic Analysis
• Number Theory and RSA

Additional Problems - Hilary Term 2016

• Additional Vector Problem

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 NP-completeness 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 multiplication-by-scalars.

Lecture 42

This lecture discussed linear combinations of vectors in three-dimensional space, linear independence and dependence. In particular, a theorem was proved showing that, given three linearly independent vectors in Euclidean space, any three-dimensional 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 three-dimensional 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 three-dimensional 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 three-dimensional 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 = |u||v| cos θ that expresses the scalar product of vectors u and v in three-dimensional 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 three-dimensional 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 three-dimensional 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 three-dimensional 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², (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