Foundations of Computer Science
Supervision Work
- Supervision 1 (pdf)
- Supervision 2 (pdf)
- Supervision 3 (pdf)
Revision work
Handouts/notes
- Techniques for generating lazy sequences (pdf, code)
- Brief notes on complete search (pdf, code)
- Three ways to generate all permutations (+) (pdf, code)
- Generating all balanced parentheses (++) (pdf, code)
- Enumerating the entries of a functional array in O(n) (+) (pdf, code)
- General removal from functional array takes Omega(n) time (+) (pdf)
Past papers
- Past papers categorised by topic (pdf)
- Past papers converted to OCaml by Dr Anil Madhavapeddy and David Allsopp (statements, solutions)
Projects
If you are interested in going in more depth in some aspects of the course, then you might want to look at these projects. If you email me, I can give you hints and further references. Do let me know if you attempt one of this, even if you have a partial solution.
- Projects (html, pdf)
- See further resources below (e.g. “Pearls of Functional Algorithm Design”)
Solution notes
Do not look at the solution notes before giving serious thought to the exercises.
Dima Szamozvancev has written solution notes for many of the core exercises. Below you will find some solution notes for the exercises in the Example Sheets. If you find any mistake/typo (even if it is a small one), then email me.
- Supervision 1 (pdf)
- Supervision 2 (pdf)
- Supervision 3 (pdf)
Further resources
- The previous version of this course was based on “ML for the working programmer” (2nd Edition) by Larry Paulson, so in the relevant sections you can find more details and extra problems.
- 99 problems in OCaml with solutions (link)
- “Pearls of Functional Algorithm Design” by R. Bird (some of the articles in OCaml)
- “Elements of ML programming” by J. Ullman
- Hackerrank’s Functional Programming section (link)
- FoCS Glossary (link).
- “Purely Functional Data Structures” by C. Okasaki (mostly outside the scope of the course, but useful connections to the algorithms course)
- “OCaml Programming: Correct + Efficient + Beautiful” (link and older version)
- “OCaml for the skeptical” (link)