Lecturer	Michael Spivey
Degrees	Moderations — Computer Science
Term	Hilary Term 2009  (16 lectures)

Overview

This course applies lessons that have been learnt in Functional Programming to the design of programs written in a procedural style. By studying a sequence of programming examples, each a useful software tool in its own right, students learn to construct programs in a systematic way, structuring them as a collection of modules with well-defined interfaces. The course also deals with the translation of functional programs into procedural ones, and introduces the idea of loop invariants for understanding and reasoning about loops. The course concludes with the study of a larger programming example, such as a graphical program for finding the best route for driving between specified towns in the UK. Through lab exercises, students learn to create, debug and maintain programs of a non-trivial but moderate size.

Learning outcomes

After studying this course, undergraduates will be able to:

1. Translate basic functional idioms into procedural ones.
2. Design simple loops, using invariants to explain why they work correctly
3. Use subroutines and modules to structure more complex programs.
4. Design data structures using arrays, records and pointers.
5. Understand the procedural implementation of some common algorithms.

Synopsis

[1] Basic imperative programming constructs: assignments, conditionals and loops. Comparison of procedural and functional programming. Example: summing an array.

[2] Method of invariants. Example: slow and fast exponentiation.

[3] Examples of invariants. Example: printing numbers in decimal.

[4] Correctness rules for while loops. Example: string comparison.

[5] Proof of termination. repeat, loop and for statements. Example: printing matching lines.

[6] Procedures and parameters.

[7] Binary search.

[8] Quicksort.

[9] Contour search (= saddleback search).

[10] Simple regular expressions.

[11] Modules. Introducing pointer-linked structures.

[12] Operations on linked lists.

[13] Hash tables.

[14] Binary trees.

[15] Doubly-linked lists and priority queues.

[16] Implementing Dijkstra's algorithm.

Syllabus

Imperative programming constructs, with informal treatment of invariants. Procedures and modules; their use in the design of large programs. Data structures, including arrays, records and pointers. Basic tools for program development. Case studies in design of medium-sized programs.

Reading list

• Martin Reiser and Niklaus Wirth, Programming in Oberon: steps beyond Pascal and Modula, Addison-Wesley, 1992.
• Brian W Kernighan and Philip J Plauger, Software Tools in Pascal, Addison-Wesley, 1981.
• Jon Louis Bentley, Programming Pearls, Addison-Wesley, 1986.

Taking our courses

This form is not to be used by students studying for a degree in the Department of Computer Science, or for Visiting Students who are registered for Computer Science courses

Other matriculated University of Oxford students who are interested in taking this, or other, courses in the Department of Computer Science, must complete this online form by 17.00 on Friday of 0th week of term in which the course is taught. Late requests, and requests sent by email, will not be considered. All requests must be approved by the relevant Computer Science departmental committee and can only be submitted using this form.