Courses in the Department of Mathematics

MA210: Discrete Mathematics 2009/10

General information about MA210: Discrete Mathematics

Teacher responsible: Dr Robert Simon

Room: B404 (Columbia House)

Email: r.s.simon@lse.ac.uk

Office hours: Please see the office hours page

Lectures can classes

This is a half-unit course, with lectures in the Lent Term.
Classes start in Week 2 of Term. Please see the Timetables webpage for full details: http://www.lse.ac.uk/admin/timetables/confirmed/module_sessional/ma/10.htm.

There will also be revision lectures in the Summer Term.

Exercises

Homework will be assigned weekly. It is important that students hand in work for marking before each class.
Corrected work will be handed back and, where appropriate, discussed in the classes. Full solutions for the homework exercises will be given out as well. This means that not all exercises need to be discussed in class.

Course material

Lecture notes will be provided. Additionally, students may wish to refer to the following books:

"Discrete Mathematics" by Norman L. Biggs (2nd edition, Oxford University Press, 2002) ISBN: 0198507178;
Library code: QA76.9 M35 B59;
"Combinatorics" by Peter J. Cameron (Cambridge University Press, 1994) ISBN: 0521457610;
Library code: QA164.C18.

All course material distributed, including lecture notes, exercise sheets and homework solutions, will also be made available via the course materials page.

Assessment

There will be a formal 2-hour examination in the Summer term.

Course description of MA210: Discrete Mathematics

Overview

This is a course intended to give an introduction to the area of mathematics called "discrete mathematics". Discrete mathematics is that part of mathematics dealing with finite - but often large - sets of objects (think of all 147 airports served by BA or all the computers connected to the Internet). Many real-world problems are inherently discrete. For instance, managers for BA may want to know how many routes should be opened to be able connect all the airports. In this simplistic example, 146 is the correct answer (Can you think of any reason why this is the smallest possible number?) but for more complex problems such a straightforward extraction is no longer possible. In order to tackle these discrete problems, we need to use tools provided by discrete mathematics.

Aims

The course is designed to:

enable students to obtain general knowledge about the area of discrete mathematics, and more in-depth knowledge of selected topics;
enable students to understand and appreciate the methods used to construct mathematical proofs.

Learning outcomes

After having followed this course, students should

have knowledge of basic definitions and concepts, and how to apply these;
have knowledge of more complicated definitions and concepts, and how to apply these in situations similar to known ones;
have knowledge of the basic techniques and methodologies in the topics covered;
be able to understand new situations and definitions, derive their formal meaning, and relate them to existing knowledge;
be able to model actual situations in a mathematical way and derive useful results.

Connections to Other Courses

MA103: Introduction to Abstract Mathematics is a prerequisite for this course. Students who are not sure if their knowledge is up to the level expected, are advised to contact the lecturer before the start of the course. Students in Mathematics and Economics must do this course or one of its sister courses MA208: Optimisation Theory, MA209: Differential Equations as part of their "pure mathematics" programme.

The course is aimed at students who are interested in more abstract mathematical ideas. Students who are interested in this type of mathematics should also consider taking MA314: Theory of Algorithms, MA315: Algebra and its Applications, or MA316: Graph Theory (new course in 2009/10).

Course Content

The course covers the following topics.

Counting: selections, inclusion-exclusion, partitions and permutations, Stirling numbers, generating functions, recurrence relations.
Graph Theory: basic concepts (graph, adjacency matrix, etc.), walks and cycles, trees and forests, colourings.
Set Systems: matching, finite geometries, block designs, Ramsey Theory.

Lectures

During the lectures, the theory will be developed and explained, proofs given, and many examples demonstrated. Students are expected to make their own notes during the lecture. In the Summer Term there will be additional lectures, mainly for revision purposes.

Classes and Exercises

In this course, as in other courses in Mathematics, it is very important that all homework questions are attempted and handed in for grading. There is a big difference between watching other people carry out calculations and being able to do them yourself, and it is vital to get practice in the various techniques covered in the course. It is also important to hand in homework, so that feedback on it can be given. Corrected work will be handed back and discussed as soon as possible. A complete set of solutions to the homework exercises will also be made available.

The lecturer of this course pays great attention to the presentation of the homework. It is not enough to have the correct answer, but also the reasoning used to obtain that answer should be correct and understandable. Students will be expected to maintain reasonable standards of written English, to write clear logical arguments, and to use mathematical notation correctly.

Office Hours

The office hours are meant for any questions and problems with the course material that have not or cannot be covered in the normal lectures and classes. You are strongly recommended to make use of them. It is expected that students utilise the office hours of their class teacher.

Exams

A mock examination paper can download from here.