Foundations of Computer Science

Lecturer: Dr L.C. Paulson (lcp@cl.cam.ac.uk)

No. of lectures + practicals: 15 + 6

Introduction.

Levels of abstraction. Floating-point numbers, and why von Neumann was wrong. Why ML? Integer arithmetic. Giving names to values. Declaring functions. Static binding, or declaration versus assignment.

Recursive functions.

Examples: Exponentiation and summing integers. Overloading. Decisions and booleans. Iteration versus recursion.

O Notation.

Examples of growth rates. Dominance. O, Omega and Theta. The costs of some sample functions. Solving recurrence equations.

Lists.

Basic list operations. Append. Naive versus efficient functions for length and reverse. Strings.

More on lists.

The utilities take and drop. Pattern-matching: zip, unzip. A word on polymorphism. The ``making change'' example.

Sorting.

A random number generator. Insertion sort, mergesort, quicksort. Their efficiency.

Datatypes and trees.

Pattern-matching and case expressions. Exceptions. Binary tree traversal (conversion to lists): preorder, inorder, postorder.

Dictionaries and functional arrays.

Functional arrays. Dictionaries: association lists (slow) versus binary search trees. Problems with unbalanced trees.

Queues and search strategies.

Depth-first search and its limitations. Breadth-first search (BFS). Implementing BFS using lists. An efficient representation of queues. Importance of efficient data representation.

Functions as values.

Nameless functions. Currying.

List functionals.

The ``apply to all'' functional, map. Examples: matrix transpose and product. The ``fold'' functionals. Predicate functionals ``filter'' and ``exists''.

Polynomial arithmetic.

Addition, multiplication of polynomials using ideas from sorting, etc.

Sequences, or lazy lists.

Non-strict functions such as IF. Call-by-need versus call-by-name. Lazy lists. Their implementation in ML. Applications, for example Newton-Raphson square roots.

Elements of procedural programming.

Address versus contents. Assignment versus binding. Own variables. Arrays, mutable or not.

Linked data structures.

Linked lists. Surgical concatenation, reverse, etc.

Recommended books:

Paulson, L.C. (1996). ML for the Working Programmer. Cambridge University Press (2nd ed.).

Harrison, R. (1993). Abstract Data Types in Standard ML. Wiley.