Syllabus and synopsis (Imperative Programming)
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.
Learning outcomes
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.
Syllabus
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.
Synopsis
[1] Basic imperative programming constructs: assignments, conditionals and loops. Comparison of imperative and functional programming. Example: summing an array.
[2] Method of invariants. Example: slow and fast exponentiation.
[3] Examples of invariants. Example: printing numbers in decimal.
[4] Correctness rules for WHILE loops. Example: string searching.
[5] REPEAT, LOOP and FOR statements. Overview of first lab exercise.
[6] Procedures and parameters.
[7] Binary search.
[8] Overview of second lab exercise.
[9] Quicksort.
[10] Contour search (= saddleback search). Common mistakes with invariants.
[11] Modules. Introducing pointer-linked structures.
[12] Operations on linked lists.
[13] Hash tables.
[14] Binary trees.
[15] Doubly-linked lists and priority queues.
[16] Implementing Dijkstra's algorithm.