Note: I've just migrated to a different physical server to run Spivey's Corner,
with a new architecture, a new operating system, a new version of PHP, and an updated version of MediaWiki.
Please let me know if anything needs adjustment! – Mike

Syllabus and synopsis (Imperative Programming)

Copyright © 2024 J. M. Spivey
Jump to navigation Jump to search

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.