Imperative Programming I: 2011-2012
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 also introduces the idea of loop invariants for understanding and reasoning about loops. 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.
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 simple data structures.
- Understand the imperative implementation of some common algorithms.
- 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.
- Programming with abstract datatypes.
- Objects and classes as modules; data abstraction.
- Reference-linked data structures: linked lists.
- Hash tables.
- Binary trees.
Imperative programming constructs, with informal treatment of invariants. Procedures and modules; their use in the design of large programs. Data structures: arrays, reference-linked data structures. Basic tools for program development. Case studies in design of medium-sized programs.
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:
- Jon Bentley, Programming Pearls, Dorling Kindersley, 2006.