Next: Help Sessions
Up: Michaelmas Term 2001: Part
Previous: Discrete Mathematics
  Contents
Lecturer: Dr L.C. Paulson
(lcp@cl.cam.ac.uk)
No. of lectures + practicals: 15 + 6
Aims
The principal aim of this course is to present the basic principles of
programming. As the introductory course of the Computer Science Tripos, it
caters to students from all backgrounds. To those who have had no
programming experience, it will be comprehensible; to those experienced in
languages such as C, it will attempt to correct any bad habits that they have
learnt.
A further aim is to introduce the principles of data structures and
algorithms. The course will emphasise the algorithmic side of programming,
focusing on problem-solving rather than on hardware-level bits and bytes.
Accordingly it will present basic algorithms for sorting, searching, etc., and
discuss their efficiency using O-notation. Worked examples (such as
polynomial arithmetic) will demonstrate how algorithmic ideas can be used to
build efficient applications.
The course will use a functional language (ML). ML is particularly
appropriate for inexperienced programmers, since a faulty program
cannot crash. The course will present the elements of functional
programming, such as curried and higher-order functions. But it will
also discuss traditional (procedural) programming, such as
assignments, arrays, pointers and mutable data structures.
Lectures
- 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.
Objectives
At the end of the course, students should
- be able to write simple ML programs
- understand the importance of abstraction in computing
- be able to estimate the efficiency of simple algorithms, using the
notions of average-case, worse-case and amortised costs
- know the comparative advantages of insertion sort, quick sort and merge
sort
- understand binary search and binary search trees
- know how to use currying and higher-order functions
Recommended books
Paulson, L.C. (1996). ML for the Working Programmer. Cambridge
University Press (2nd ed.).
Okasaki, C. (1998). Purely Functional Data Structures. Cambridge
University Press.
Next: Help Sessions
Up: Michaelmas Term 2001: Part
Previous: Discrete Mathematics
  Contents
Christine Northeast
Tue Sep 4 09:34:31 BST 2001