Lecturer	Gavin Lowe
Degrees	Preliminary Examinations — Computer Science and Philosophy Preliminary Examinations — Computer Science Preliminary Examinations — Mathematics and Computer Science
Term	Hilary Term 2013  (16 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. The course uses the programming language Scala, a modern object-oriented programming language, heavily influenced by the functional programming paradigm.

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

• Basic imperative programming constructs: assignments, conditionals, procedures and loops. Comparison of imperative and functional programming. Example: factorials.
• Method of invariants: correctness rules for while loops; proof of termination.  Examples including summing an array, slow and fast exponentiation.  Unit testing; debugging.
• Examples: string comparison, printing numbers in decimal.
• Binary search.
• Quicksort.
• Programming with abstract datatypes.
• Objects and classes as modules; specification; data abstraction.
• Reference-linked data structures: linked lists, binary trees.

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

Students will benefit from having access to the following book:

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

This book gives a good description of the Scala language; however, it assumes that the reader already knows how to program in an imperative style. It should therefore be read in conjunction with the lectures.

The following book will provide useful additional reading; it is recommended for reading after the course, 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.