Introduction to Algorithms

Paul Taylor

1999-2001

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.