Imperative Programming Parts 1 and 2: 2017-2018
OverviewThis 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.
After studying this course, undergraduates will be able to:
- Translate basic functional idioms into imperative ones.
- Design simple loops, using invariants to explain why they work correctly.
- Use subroutines and modules to structure more complex programs.
- Specify a module as an abstract datatype, and formalise the relationship between that specification and an implementation.
- Design simple data structures.
- Understand the imperative implementation of some common algorithms.
Numbers in square brackets indicate the approximate number of lectures.
Part 1: Programming with state
-  Basic imperative programming constructs: assignments, conditionals, procedures and loops. Comparison of imperative and functional programming. Examples.
-  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.
-  Unit testing; debugging.
-  Binary search.
-  Quicksort.
Total for this part: 9 lectures
Part 2: Datatypes and data structures
-  Modularisation and abstract datatypes. Specification, interfaces and (some) implementation. Relevant classes from the API (HashSet, Map). Examples: spell-checking, dictionary and phone book.
-  Programming with abstract datatypes. Relevant classes from the API (List, Queue, Option). Example: the word path.
-  Implementing abstract datatypes: abstraction functions; datatype invariants; correctness conditions; encapsulation. Example: phone book.
-  Documentation and testing of objects and classes
- [1.5] Linked lists.
-  Bit maps and hash tables
-  Binary trees.
- [1.5] Priority queues
Total for this part: 11 lectures
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.
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.