MA408: Discrete Mathematics and Complexity 2009/10
Course
Materials
General information about MA408: Discrete
Mathematics and Complexity
Timetable
This is a half-unit course, with lectures in the Lent Term.
There will also be revision lectures in the Summer Term.
Classes will start in Week 2 of the Lent Term.
Full timetabling information can be found here:
http://www.lse.ac.uk/admin/timetables/confirmed/module_sessional/ma/24.htm
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. Additional notes/summaries will be
distributed from time to time.
In the Summer Term there will be additional lectures 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 presenting a proof or
performing some calculations and being able to do these things
yourself. 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 in the class.
Presentation of work is a very important part of this
course.
It is not enough to obtain the correct answer;
it is
expected that the arguments used to arrive at
that answer
should be correct and understandable. Students
are
expected to explain their reasoning using proper English, and to
use mathematical notation and terminology correctly.
Homework
Homework announcements will be made during lectures
each week. The homework has to be handed in within 7 days, either
during one of the lecturers, of in the class teacher's homework box
(blue
boxes on the Ground Floor of Columbia House House). No late work will
be
accepted. If you don't finish the assignment, hand in whatever you
have.
Label all work with your name and the course number (MA408).
Corrected work will be handed back and discussed in the classes.
Solutions
for some of the homework exercises will be given out as well. This
means
that not all exercises need to be discussed in class.
Course material
Students are expected to make notes during the lectures and study the
recommended parts in the literature. When appropriate, extra notes will
be
distributed in the lectures.
The most relevant books for the course are:
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and
Clifford
Stein, Introduction to Algorithms (2nd edition). MIT Press
(2001).
- J.A. Bondy and U.S.R. Murty, Graph Theory with Applications.
North Holland (1976).
- Reinhard Diestel, Graph Theory (1st, 2nd or 3rd edition).
Springer-Verlag (1997,2000,2005).
- Herbert S. Wilf, Algorithms and Complexity (1st or 2nd
edition).
A K Peter (1985,2002).
- Norman L. Biggs, Discrete Mathematics (2nd edition).
Oxford
University Press (2002).
Please read the relevant part of
the
Course material page (or wait for the first lecture) before buying
any
of these books.
All course material produced by the lecturer, including lecture
notes,
exercise sheets, model answers, etc., will also be made available on
this
website via the course
material page.
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.
The times of the office hours for lectures and class teachers can be
found
on the departmental
office hours
page.
Course description of MA408: Discrete
Mathematics and Complexity
Overview
The first part of this course aims to give an idea of some of the main
ideas studied in the broad area that is Discrete Mathematics, where the
emphasis will be on subject that have clear algorithmic aspects. In the
second part we will use some of the ideas from the first part to start
building a formal theory of "computability" and "efficiency of
algorithms".
The approach will be fairly theoretical, in the sense that the aim is
not
to study "real-life" problems. Concepts and problems considered will
usually have a formal theoretical description. But using such a more
abstract description, it is often easier to understand what the
relation
between problems is; and what propeerties make certain problems hard or
easy to answer or compute.
Course Content
The course covers the following topics:
- general combinatorial techniques such as the Pigeon Hole
Principle;
- order of functions, big-oh and small-oh notation;
- brief review of graph-theoretic terminology;
- matchings, Hall's theorem;
- vertex and edge colourings;
- network flows, the max-flow min-cut theorem, and its algorithmic
version; connections to graph connectivity;
- fundamental ideas about computability, Turing machines;
- the halting problem;
- polynomial time;
- polynomial reducibility;
- non-deterministic polynomial time, NP-hard and NP-complete
problems.
Connections to Other Courses
MA407
Algorithms
and Computation is a prerequisite for this course. Students will be
expected that they have obtained sufficient programming skills to be
able
to implement simple algorithms without too much difficulties.
There are several other courses in the programme that look at topics
that
can be described as being "discrete" in nature. From the mathematics
courses these are MA401
Computational
Learning Theory and Neural Networks (although this is not running in 2008/9) and MA410
Information,
Communication and Cryptography. From the outside options, a course
which has close relations with this one is
OR408 Combinatorial
Optimisation.
Assessment and Exam Papers
The assessment for this course will be based on two parts:
One set of coursework will count for 20%.
The remaining 80% will be based on a formal 2-hour examination in the
Summer Term.
Please note: students are advised not to rely too heavily on past exam
papers when revising for their exams, as they can only offer a limited
indication of what might be covered in a future exam. For further information,
please see the guidance here:
http://www.maths.lse.ac.uk/examinations_in_mathematics.html#past_papers
Past Exam Papers
MA408
Exam Paper 2007
MA408
Exam Paper 2008
Solutions
to MA408 Exam 2008
Copyright © London
School of
Economics & Political Science 2009
Last changed: 12th January 2010
Send comments to
webmaster