www.cs.ox.ac.uk/teaching/courses/imperativeprogramming1/index.html

You are here:

• Home
• Current Students
• Courses
• Imperative Programming I

Imperative Programming I:  2012-2013

Information

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.