Notes for tutors (Imperative Programming)

News for 2011

I've decided that a slightly slower start to the course is better, giving time in the first lecture to show and tell something about the mechanics of working with compilers, the unix command line, etc.; also to link loops with tail recursion; and above all to make the very first example of an invariant utterly straightforward. So I've added an extra lecture to the start of the course, numbering it with zero more to avoid having to renumber everything else than as a tribute to the memory of E.W.D.. The compensating loss is what was lecture 15, about randomised binary search trees; that's a shame, because everyone should know about this simple and highly effective data structure.

The laboratory exercises for this year will be:

• The usual Lab 1 based on simple cryptography, and
• Lab 3 in which the aim is to implement a prototype of the unix utility diff using standard software tools, plus a program written by the student that finds a longest ascending subsequence of a given sequence of integers. This follows an idea of Carroll Morgan, and provides students with the opportunity to write a program from scratch., and this new lab provides an opportunity to do so. The same overall problem – determining the minimum edit distance between two strings – is studied in the algorithms course with a very different algorithm, so there are interesting parallels to explore.
• Very optionally, we will also support students who want to do Lab 4, an implementation of Dijkstra's algorithm; but it's proven too difficult to cover enough about pointer-linked structures early in term to make that feasible as a main lab exercise.

I'm not sure whether the extra problems classes I put on last year had any good effect, enjoyable as they were to give. I'm busier this year, so I've decided not to repeat the experiment.

News for 2010 (edited)

This year's course will continue with the minor adjustments in the way the course is given that were introduced last year.

• In order to encourage attendance and active listening, I have decided that instead of full notes, I will be issuing only a brief handout in each lecture. The handout will contain an outline of the lecture and the text of important programs and formulas, but students will be expected to supplement it by taking their own notes. I shall not be handing out copies of slides because I will not be using any. An online copy of each handout will be accessible from the course outline page. Fuller notes from an earlier year are accessible here for the use of tutors. I may well make them accessible to everyone at the end of term for use in revision.

• I've selected some of the problems from previous years and organised them into four sheets, each of about the right length to be covered in one tutorial. I will be suggesting that (unless their own tutors direct them otherwise) students do these problems for tutorials. For tutors who wish to spend more tutorial time on the course, or to find more challenging problems for students with prior programming experience, there is another document containing extra problems. The first four sections of this document correspond to the four main problem sheets, and the last section contains a few extra problems on using invariants to help those who need a bit more practice with them. Finally, there's also a sheet of revision problems. I leave it up to tutors whether they want to cover three of the main sheets during term and set the fourth as vacation work, or to cover all four sheets during term and set the revision problems for the vacation.

• The practical work will be supported by a new GUI-based debugger that is partly the result of a student project. Although for stability we will have an older release of the compiler to fall back on, I hope also to make available a JIT-based implementation that is the subject of a current student project.