Foundations of Computer Science
This course provides its teaching materials in a few formats for your convenience.
Printable
The course notes are published as a versioned PDF, with changes to subsequent versions noted here. You will receive v1.7 of these notes as a hardcopy.
- v1.7.pdf: initial release
Online Notebook
You can also access an interactive version of the same notes online at hub.cl.cam.ac.uk. You will need to login via your Raven id, and then navigate to the focs-notebooks/ directory and click on the 1A Foundations of Computer Science.ipynb file.
The first thing you should do when you access it is to go to the Cell / Run All menu to execute all the code fragments. This interactive notebook spins up your own version of the notes, which you can edit and manipulate from your web browser. If you click on a code cell, edit it, and then press Shift+Enter, the server will evaluate your new code and show you the output.
You are encouraged to experiment with the OCaml code in this sandbox. If you need to reset your environment, simply click on Control Panel and restart your server, and you will be back to the original copy. Do not store precious notes in this notebook, as it may reset unexpectedly.
Lecture Slides
The slides given during each lecture will be available after the lectures have been given. Available so far are:
- Lecture 1: Introduction
- Lecture 2: Recursion and Complexity
- Lecture 3: Lists and Polymorphism
- Lecture 4: More Lists and Making Change
- Lecture 5: Sorting
- Lecture 6: Datatypes and Trees
- Lecture 7: Dictionaries and Functional Arrays
- Lecture 8: Currying
- Lecture 9: Sequences, or Lazy Lists
- Lecture 10: Search
- Lecture 11: Procedural Programming
- Lecture 12: Recap and Real World Use!
Extra Material
Some extra material to complement the lectures. The notebooks here should be uploaded to hub.cl.cam.ac.uk to view them.
- Explaining the trace of an interleaved sequence
- A notebook with the trace of the 'change' function with backtracking
- A notebook with the trace of 'get' running on an interleaved sequence. See also the link above to the explanation
- A notebook with the trace of some quicksort implementations
- A notebook with the trace of insertion sort
- A notebook with the trace of mergesort
Offline Programming
Although not essential, you may find it convenient to install OCaml on your own computer. For that, you can follow the installation instructions at ocaml.org.
Source Code examples
Past papers
The official past papers are available online. The unofficial translations below use OCaml rather than Standard ML (which was the language used for the course until 2020).
- 2017 Paper 1 Question 2
- 2017 Paper 1 Question 1
- 2016 Paper 1 Question 2
- 2016 Paper 1 Question 1
- 2015 Paper 1 Question 2
- 2015 Paper 1 Question 1 - solution notes
- 2014 Paper 1 Question 2 - solution notes
- 2014 Paper 1 Question 1 - solution notes
- 2013 Paper 1 Question 2 - solution notes
- 2013 Paper 1 Question 1 - solution notes
- 2012 Paper 1 Question 2 - solution notes
- 2012 Paper 1 Question 1 - solution notes
- 2011 Paper 1 Question 2
- 2011 Paper 1 Question 1
- 2010 Paper 1 Question 2
- 2010 Paper 1 Question 1
- 2009 Paper 1 Question 2
- 2009 Paper 1 Question 1
- 2008 Paper 1 Question 6
- 2008 Paper 1 Question 5
- 2008 Paper 1 Question 1
- 2007 Paper 1 Question 6
- 2007 Paper 1 Question 5
- 2007 Paper 1 Question 1
- 2006 Paper 1 Question 6
- 2006 Paper 1 Question 5
- 2006 Paper 1 Question 1
- 2005 Paper 1 Question 6
- 2005 Paper 1 Question 5
- 2005 Paper 1 Question 1
- 2004 Paper 1 Question 6 - solution notes
- 2004 Paper 1 Question 5 - solution notes
- 2004 Paper 1 Question 1 - solution notes
- 2003 Paper 1 Question 6
- 2003 Paper 1 Question 5
- 2003 Paper 1 Question 1
- 2002 Paper 1 Question 6
- 2002 Paper 1 Question 5
- 2002 Paper 1 Question 1
- 2001 Paper 1 Question 6
- 2001 Paper 1 Question 5
- 2001 Paper 1 Question 1
- 2000 Paper 1 Question 6
- 2000 Paper 1 Question 5
- 2000 Paper 1 Question 1
- 1999 Paper 1 Question 6
- 1999 Paper 1 Question 5
- 1999 Paper 1 Question 1
- 1998 Paper 1 Question 6
- 1998 Paper 1 Question 5
- 1998 Paper 1 Question 1
- 1997 Paper 1 Question 6
- 1997 Paper 1 Question 5
- 1997 Paper 1 Question 1
- 1996 Paper 1 Question 6
- 1996 Paper 1 Question 5
- 1996 Paper 1 Question 2
- 1995 Paper 1 Question 6
- 1995 Paper 1 Question 5
- 1995 Paper 1 Question 3
Recommended Reading
A good complement to this course is the OCaml From the Very Beginning book by John Whitington. If you are feeling advanced, then Real World OCaml may interest you -- but note that much of the content there is far beyond the syllabus required for Foundations of CS.
See also the OCaml Practical Classes for information about your ticks.