By Lawrence C Paulson
This course has two objectives. First (and obvious) is to teach programming. Second is to present some fundamental principles of computer science, especially algorithm design. Most students will have some programming experience already, but there are few people whose programming cannot be improved through greater knowledge of basic principles. Please bear this point in mind if you have extensive experience and find parts of the course rather slow.
The programming in this course is based on the language ML and mostly concerns the functional programming style. Functional programs tend to be shorter and easier to understand than their counterparts in conventional languages such as C. In the space of a few weeks, we shall be able to cover most of the forms of data structures seen in programming. The course also covers basic methods for estimating efficiency.
Courses in the Computer Laboratory are now expected to supply a Learning Guide to suggest extra reading, discussion topics, exercises and past exam questions. For this course, such material is attached at the end of each lecture. Extra reading is mostly drawn from my book ML for the Working Programmer (second edition), which also contains many exercises.
Contents
Introduction
Recursive Functions
O Notation: Estimating Costs in the Limit
Lists
More on Lists
Sorting
Datatypes and Trees
Dictionaries and Functional Arrays
Queues and Search Strategies
Functions as Values
List Functionals
Polynomial Arithmetic
Sequences, or Lazy Lists
Elements of Procedural Programming
Linked Data Structures