Lecturer	Joe Pitt-Francis
Degrees	Preliminary Examinations — Computer Science and Philosophy Preliminary Examinations — Computer Science Preliminary Examinations — Mathematics and Computer Science
Term	Hilary Term 2018  (20 lectures)

Overview

This course applies lessons that have been learnt in Functional Programming to the design of programs written in an imperative 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 introduces the idea of loop invariants for understanding and reasoning about loops. The course also introduces the idea of modularising larger programs, capturing the functionality of a component of the program using an abstract mathematical specification, and describing formally the relationship between that specification and the implementation.

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 imperative ones.
2. Design simple loops, using invariants to explain why they work correctly.
3. Use subroutines and modules to structure more complex programs.
4. Specify a module as an abstract datatype, and formalise the relationship between that specification and an implementation.
5. Design simple data structures.
6. Understand the imperative implementation of some common algorithms.

Synopsis

Numbers in square brackets indicate the approximate number of lectures.

Part 1: Programming with state

• [1] Basic imperative programming constructs: assignments, conditionals, procedures and loops. Comparison of imperative and functional programming. Examples.
• [5] Method of invariants: correctness rules for while loops; proof of termination.  Examples including summing an array, slow and fast exponentiation. Examples: string comparison, printing numbers in decimal.
• [1] Unit testing; debugging.
• [1] Binary search.
• [1] Quicksort.

Total for this part: 9 lectures

Part 2: Datatypes and data structures

• [2] Modularisation and abstract datatypes. Specification, interfaces and (some) implementation. Relevant classes from the API (HashSet, Map). Examples: spell-checking, dictionary and phone book.
• [1] Programming with abstract datatypes. Relevant classes from the API (List, Queue, Option). Example: the word path.
• [2] Implementing abstract datatypes: abstraction functions; datatype invariants; correctness conditions; encapsulation. Example: phone book.
• [1] Documentation and testing of objects and classes
• [1.5] Linked lists.
• [1] Bit maps and hash tables
• [1] Binary trees.
• [1.5] Priority queues

Total for this part: 11 lectures

Syllabus

Imperative programming constructs, with informal treatment of invariants. Procedures and modules; their use in the design of large programs; specification and implementation of abstract datatypes. Data structures: arrays, reference-linked data structures. Basic tools for program development. Case studies in design of medium-sized programs.

Reading list

There is no set text for the course, in the sense of a book that is followed by the lectures.

This year's course will be taught using the Scala programming language.  As a guide to Scala, you might use

• Martin Odersky, Lex Spoon and Bill Venners, Programming in Scala.

There are many adequate treatments of the use of logic and invariants in the development of imperative programs; one reasonably pitched one is

• Gries, The Science of Programming, Springer, 1981.

Useful additional cultural reading, recommended for reading after the course, perhaps during the Easter vacation:

• Jon Bentley, Programming Pearls, Dorling Kindersley, 2006.

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.