Syllabus and synopsis
This course applies lessons that have been learnt in Functional Programming to the design of programs written in a 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 procedures with well-defined interfaces. The course also 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.
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.
- Design data structures using arrays, records and pointers.
- Understand the imperative implementation of some common algorithms.
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.
 Basic imperative programming constructs: assignments, conditionals and loops. Comparison of imperative and functional programming. Example: summing an array.
 Method of invariants. Example: slow and fast exponentiation.
 Examples of invariants. Example: printing numbers in decimal.
 Correctness rules for WHILE loops. Example: string searching.
 REPEAT, LOOP and FOR statements. Overview of first lab exercise.
 Procedures and parameters.
 Binary search.
 Overview of second lab exercise.
 Contour search (= saddleback search). Common mistakes with invariants.
 Modules. Introducing pointer-linked structures.
 Operations on linked lists.
 Hash tables.
 Binary trees.
 Doubly-linked lists and priority queues.
 Implementing Dijkstra's algorithm.