Course outline (Imperative Programming)

Copyright © 2024 J. M. Spivey
Jump to navigation Jump to search

This page gives an outline of the course, supplemented by links to the handouts and problem sheets, and source code for the example programs.

  • I will not be using slides, and I will not be handing out a transcript of each lecture, but only a very brief handout, typically containing the text of programs that are discussed in the lecture. Students will be expected to attend the lectures and make their own notes. For help in revision, there is a fuller set of lecture notes from a previous year.
  • Each problem sheet contains problems on all the material up to the place it appears in this outline, but you should be able to do at least some of the problems before we have finished all the lectures up to that point. I shall be handing out a complete set of problem sheets in a lecture near the start of the course.
  • Source code is given for the example programs that are used in the lectures.


[0] First steps: handout.[1]

[1] Slow and fast exponentiation: handout. A second handout.

[2] Printing numbers in decimal: handout.

[3] Method of invariants and proof of termination; String comparison: handout.

[4] Repeat, loop and for statements; introducing Lab 1: handout.

Programming with procedures

[5] Procedures and parameters: handout.

[6] Binary search: handout.

[7] Quicksort: handout. Another handout.

[8] Lab 3 – longest ascending subsequence: handout.

  • Source text of program L7Sort.m.
  • Problem sheet 2.

Modules and pointers

[9] Modules; pointer-linked structures: handout.

[10] Operations on linked lists: handout.

[11] Doubly-linked lists and priority queues: handout.

[12] Implementing Dijkstra's algorithm: handout.

Implementing data structures


[13] Hash tables: handout.

[14] Binary trees: handout. Also a supplementary note about removing recursion from in-order traversal.

[15] Dancing links: handout.

  1. Please don't think that I worship the fetish of numbering everything from zero in everyday life: it's just that I decided to add an extra lecture at the start, and didn't want to renumber everything else.