Computer Laboratory > Teaching > Course material 2008–09 > Computer Science Tripos Syllabus and Booklist 2008-2009 > Paper 1: Foundations of Computer Science

next up previous contents
Next: How to Study Computer Up: Michaelmas Term 2008: Part Previous: Paper 1: Discrete Mathematics   Contents


Paper 1: Foundations of Computer Science

Lecturer: Professor L.C. Paulson

No. of lectures and practicals: 15 + 6

This course is a prerequisite for Programming in Java and Prolog (Part IB).

Aims

The main 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

Objectives

At the end of the course, students should

Recommended reading

* Paulson, L.C. (1996). ML for the working programmer. Cambridge University Press (2nd ed.).
Okasaki, C. (1998). Purely functional data structures. Cambridge University Press.

Gentler alternative to the main text:
Hansen, M. & Rischel, H. (1999). Introduction to programming using SML. Addison-Wesley.

For reference only:
Gansner, E.R. & Reppy, J.H. (2004). The Standard ML Basis Manual. Cambridge University Press. ISBN: 0521794781



next up previous contents
Next: How to Study Computer Up: Michaelmas Term 2008: Part Previous: Paper 1: Discrete Mathematics   Contents