Introduction to Algorithms
www.Paul Taylor. EU/algorithms
First year Computer Science at Queen Mary
I was a lecturer in computer science at
Queen Mary, University of London
on a temporary contract for the calendar years 1999-2001.
I was assigned to teach a core (compulsory) module to
first year BSc G500 Computer Science students,
together with some second year joint-honours Maths & CS students.
The course had been introduced by
who had written an excellent set of
about a wide variety of algorithms.
He had recommended
Data Structures and Problem-Solving using Java
by Mark Allen Weiss.
In my version of the course, I substantially reduced the number of
algorithms, but added some ideas for proving correctness that
I had learned from tutoring a course at
that had led to the textbook
that he wrote jointly with
and Hessam Khoshnevisan.
However, I replaced their symbolic methods with a diagrammatic one
of my own.
In both the programming and the reasoning, I restricted myself to
algorithms that could be implemented on arrays, without using the
object-oriented features of the the programming language (Java).
In other words, this was not an Algorithms and Data
Structures course, such as is commonly taught to second
year computer science students.
I was also supposed to introduce ideas of complexity, which I did
at a strictly jargon level, having come to the conclusion that the
mathematical methods that are popular especially in algorithms
courses in American universities.
For further discussion, see
how I taught this course.
Please note that the following are not lecture notes.
They are an amalgamation of
Full treatment of some theoretical topics is therefore missing from
the collection, cf. the exam questions.
- instructions for experiments and programming that students do
during supervised labs;
- model answers for exams and tests on the theoretical material
that had been presented on the blackboard in lectures; and
- administrative documents that were originally published as
The chapters listed below are HTML translations that are only suitable
for quick browsing. In particular, the diagrams had to be removed,
and there may be other mathematical symbols missing.
If you would like to print the complete set, or to study the
contents in detail (whether as a student, a teacher or in order
to give me a job) please
download this in compressed PostScript.
A substantial innovation that I made in teaching this material was
This provides the main program, so that students only write
the modules that implement the algorithms themselves;
it allows them to supply test data from the keyboard.
After that, it does comprehensive black-box testing of the correctness
of their algorithm modules.
Finally, it finds out the complexity of their algorithms emprically,
by running them on test data of increasing size.
The TESTER is provided in a JAR file, along with templates
for each of the student exercises in
although it is easier to download these in one go
in tar-compressed form.
You can see the TESTER in action on the exercises in the
course without doing them yourself by running, for example
The TESTER is not available on the web because it contains
exactly the exercises that the students are supposed to do, and there
are JAVA decompilers that more or less recover the source
code from the class file.
Before it is used again for teaching,
the class file needs to be "obfuscated".
and it was derived from algorithms/index.tex
which was last modified on 29 August 2008.