# Introduction to Algorithms

### Paul Taylor

### 1999-2001

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
Richard Bornat,
who had written an excellent set of
lecture notes
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
Imperial College
lectured by
Steve Vickers
that had led to the textbook
*Reasonned Programming*
that he wrote jointly with
Krysia Broda,
Susan Eisenbach
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.
## Teaching materials

Please note that the following are not *lecture* notes.
They are an amalgamation of
- 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
Web pages.

Full treatment of some theoretical topics is therefore missing from
the collection, *cf*. the exam questions.

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.
## The Tester

A substantial innovation that I made in teaching this material was
my TESTER.
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
this directory,
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
./check quick-sort

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".
This is
`www.PaulTaylor.EU/algorithms/index.html`
and it was derived from `algorithms/index.tex`
which was last modified on 29 August 2008.