MA407: Algorithms and Computation 2009/10
General information about MA407:
Algorithms and Computation
Course format
This is a half unit course, with lectures given biweekly,
interleaved with classes, in the Michaelmas and Lent term. There
will also be revision lectures in the Summer term.
Availability
This course is compulsory for the MSc in Applicable
Mathematics. Students from other MSc programmes may follow
this course, provided they fulfil the pre-requisites.
Homework
Exercise sheets will be given out in each lecture week,
to be handed back at the beginning of the class in the following week.
This course also has assessed coursework, in the form of two
assignments that count as 10 percent and 20 percent of the
final class mark, respectively.
The first assignment is due in Michaelmas Term.
The second assignment is due in Lent Term.
These assignments have the status of examinations.
Details will be given in due course.
Prerequisites
Good general knowledge of mathematics, including familiarity
with abstract concepts, and a willingness to cope with
technical details of computer usage.
No previous programming experience is required, but
the course will proceed rapidly as concerns computer
programming.
For that reason, students unfamiliar with Java programming
are invited to sit in on the undergraduate course MA314
Theory of Algorithms.
For those students, the exercises of MA314 are also discussed
in the MA407 Computer Help Sessions, taught by
Raminder Ruprai. Week 1 of the Computer Help Sessions gives an
introduction to the Java system at the LSE.
Assessment
The course is examined by projects and a written examination
as follows:
10% for a first short programming project, due in MT;
20% for a second larger programming project due in LT;
70% for a two-hour written examination in the ST.
Course description of MA407:
Algorithms and Computation
The course aims to provide an introduction to
algorithms, data structures and computation.
Algorithms are the methods by which a computer performs certain
tasks. The design of algorithms goes hand in hand with the design
of data structures, which define how data are organised.
An example of a data structure is a sorted array of keys,
which allows identifying in logarithmic time (by ``binary
search'' as one would try to find a name in a phone book)
whether a key is present and where it would have to be
inserted in order to preserve the sort order.
Other data structures concern the storage of graphs (or networks),
which form the basis for many
optimisation problems.
The classic "Introduction to Algorithms" by
Cormen/Leiserson/Rivest, see the reading
list below, is a comprehensive, if sometimes over-detailed,
textbook on algorithms.
The background of students for this course tends to be
varied. In particular, many students will not have
previous experience in computer programming, whereas
others will.
One has to understand the precision needed to get a computer
program to work in order to appreciate algorithms.
Much homework and the assessed coursework concern the implementation of
basic algorithmic problems.
The programming language chosen for these assignments is the
language Java.
The course deals only with a basic subset of Java in
order to specify algorithms.
In particular, this means a very basic form of input and
output via the "command line prompt" as it is used in the
DOS (the precursor to Windows, accessible with the "cmd"
command under "Run" in a Windows start menu) and UNIX or
Linux operating systems.
The book by Flanagan, see reading
list, is a standard reference for Java and may serve a
very concise introduction.
In the classes, the features of Java necessary for the
course will be explained.
For the student unfamiliar with programming, this may require intense
work in the beginning weeks, so please
attend the MA314 lectures and MA407 Computer Help Sessions.
Learning Outcomes
Knowledge of basic data structures and their role in
solving programming tasks. Ability to design correct and efficient
algorithms, to describe their steps precisely and understandably, and
to
code them in simple programming contexts. Understanding of running time
analysis techniques.
Reading list
The following books are recommended.
The basic level of Java used in the course can be found in almost any
book on Java.
Consider also the online Sun
Java
tutorial, http://java.sun.com/docs/books/tutorial/
-
T. H. Cormen, C. E. Leiserson, and R. L. Rivest (1990,
2001),
Introduction to Algorithms.
First or Second Edition (with C. Stein as additional author).
MIT Press, Cambridge, Mass.
The main text on algorithms.
- D. Flanagan (1999, 2002, 2005),
Java in a Nutshell, 3rd, 4th, or 5th Edition.
O'Reilly UK.
This book has concise introductions to the important
concepts in Java, very suitable for someone familiar with
programming, and has a by now huge reference section
(almost none of which is needed in the course).
- J. R. Hubbard (2004),
Programming with Java (Schaum Outline). McGraw-Hill.
This is a short (and very economically priced) book covering the basics
of
Java, which is all that is needed in the course.
It still requires some basic understanding of using a
computer.
Supplementary reading
-
N. L. Biggs (1998), Discrete Mathematics.
Clarendon Press.
-
C. H. Papadimitriou and K. Steiglitz (1982),
Combinatorial
Optimization: Algorithms and Complexity.
Prentice-Hall. [Dover reprint 1998, ISBN: 0486402584].
-
N. Carter (2001),
Computer Architecture (Schaum Outline). McGraw-Hill.
A very economically priced book on Computer Architecture, which
explains
the internal workings of a computer.
Past exam papers for this course
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
![[pdf]](http://www.maths.lse.ac.uk/Figures/Icons/pdf.gif)
MA407
Examination 2006 MA407
Examination Solutions 2006
MA407
Examination 2007 MA407
Examination Solutions 2007
MA407
Examination 2008 MA407
Examination Solutions 2008
Copyright © London
School of Economics & Political Science 2009
Last change: 14th October 2009
Send
comments to webmaster
nash.lse.ac.uk