Foundations of Computer Science (2024-2025)
Anil Madhavapeddy, Jonathan Ludlam
Computer Laboratory Version 1.6
Contents
1 Lecture 1: Introduction to Programming 5
1.1 Basic Concepts in Computer Science................................................................................. 5
1.2 Goals of Programming.......................................................................................................6
1.3 Why Program in OCaml? .................................................................................................. 7
1.4 A first session with OCaml ................................................................................................8
1.5 Raising a Number to a Power ............................................................................................9
1.6 Efficiently Raising a Number to a Power..........................................................................11
2 Lecture 2: Recursion and Efficiency 13
2.1 Expression Evaluation...................................................................................................... 13
2.2 Summing the first n integers ........................................................................................... 13
2.3 Iteratively summing the first n integers .......................................................................... 14
2.4 Recursion vs Iteration ...................................................................................................... 14
2.5 Silly Summing the First n Integers ................................................................................. 15
2.6 Comparing Algorithms: O Notation ................................................................................ 16
2.7 Simple Facts About O Notation ...................................................................................... 17
2.8 Common Complexity Classes........................................................................................... 17
2.9 Sample costs in O notation .............................................................................................. 18
2.10 Some Simple Recurrence Relations .................................................................................. 18
3 Lecture 3: Lists 21
3.1 The List Primitives ..........................................................................................................22
3.2 Getting at the Head and Tail ...........................................................................................22
3.3 Computing the Length of a List.......................................................................................24
3.4 Efficiently Computing the Length of a List ..................................................................... 25
3.5 Append: List Concatenation............................................................................................26
3.6 Reversing a List in 𝑂(𝑛2)................................................................................................................................ 26
1
, 3.7 Reversing a List in ........................................................................................................... 27
3.8 Lists, Strings and Characters ...........................................................................................28
4 Lecture 4: More on Lists 30
4.1 List Utilities: take and drop ........................................................................................... 30
4.2 Linear Search ................................................................................................................... 31
4.3 Equality Tests .................................................................................................................. 31
4.4 Building a List of Pairs .................................................................................................... 32
4.5 Building a Pair of Results ................................................................................................ 33
4.6 An Application: Making Change ..................................................................................... 33
4.7 All Ways of Making Change ............................................................................................34
4.8 All Ways of Making Change — Faster! ........................................................................... 35
5 Lecture 5: Sorting 37
5.1 How Fast Can We Sort?................................................................................................... 37
5.2 Insertion Sort ...................................................................................................................39
5.3 Quicksort: The Idea ........................................................................................................ 40
5.4 Quicksort: The Code....................................................................................................... 40
5.5 Append-Free Quicksort .................................................................................................... 41
5.6 Merging Two Lists ...........................................................................................................42
5.7 Top-down Merge sort .......................................................................................................42
5.8 Summary of Sorting Algorithms ......................................................................................43
6 Lecture 6: Datatypes and Trees 45
6.1 An Enumeration Type ...................................................................................................... 45
6.2 Declaring a Function on Vehicles ....................................................................................46
6.3 A Datatype whose Constructors have Arguments ...........................................................46
6.4 A Finer Wheel Computation ........................................................................................... 47
6.5 Error Handling: Exceptions ............................................................................................. 47
6.6 Exceptions in OCaml ...................................................................................................... 48
6.7 Making Change with Exceptions .....................................................................................49
6.8 Making Change: A Trace................................................................................................. 51
6.9 Binary Trees, a Recursive Datatype ................................................................................. 52
6.10 Basic Properties of Binary Trees ..................................................................................... 53
7 Lecture 7: Dictionaries and Functional Arrays 55
7.1 Dictionaries...................................................................................................................... 55
7.2 Binary Search Trees ......................................................................................................... 56
7.3 Lookup: Seeks Left or Right ............................................................................................ 56
7.4 Update ............................................................................................................................. 57
7.5 Aside: Traversing Trees (3 Methods)...............................................................................58
7.6 Efficiently Traversing Trees.............................................................................................. 59
7.7 Arrays .............................................................................................................................. 59
7.8 Functional Arrays as Binary Trees ................................................................................. 60
7.9 The Lookup Function ...................................................................................................... 61
7.10 The Update Function ......................................................................................................62
8 Lecture 8: Functions as Values 64
2
, 8.1 Functions Without Names ...............................................................................................64
8.2 Curried Functions ............................................................................................................ 65
8.3 Shorthand for Curried Functions..................................................................................... 67
8.4 Partial Application: A Curried Insertion Sort ................................................................ 68
8.5 map: the ―Apply to All‖ Function ..................................................................................69
8.6 Example: Matrix Transpose ............................................................................................69
8.7 Review of Matrix Multiplication......................................................................................70
8.8 Matrix Multiplication in OCaml ...................................................................................... 71
8.9 List Functionals for Predicates ........................................................................................ 71
8.10 Applications of the Predicate Functionals ....................................................................... 72
9 Lecture 9: Sequences, or Lazy Lists 75
9.1 A Pipeline ........................................................................................................................ 75
9.2 Lazy Lists (or Streams) ................................................................................................... 75
9.3 Lazy Lists in OCaml ........................................................................................................ 76
9.4 The Infinite Sequence: 𝑘, 𝑘 1, 𝑘 2,............................................................................. 77
9.5 Consuming a Sequence .................................................................................................... 77
9.6 Sample Evaluation ........................................................................................................... 78
9.7 Joining Two Sequences .................................................................................................... 78
9.8 Functionals for Lazy Lists ................................................................................................ 79
9.9 Numerical Computations on Infinite Sequences .............................................................. 79
10 Lecture 10: Queues and Search Strategies 82
10.1 Breadth-First v Depth-First Tree Traversal ................................................................... 82
10.2 Breadth-First Tree Traversal — Using Append .............................................................. 83
10.3 An Abstract Data Type: Queues.................................................................................... 83
10.4 Efficient Functional Queues: Idea ................................................................................... 83
10.5 Efficient Functional Queues: Code .................................................................................. 84
10.6 Breadth-First Tree Traversal — Using Queues................................................................85
10.7 Iterative deepening: Another Exhaustive Search ........................................................... 86
10.8 Another Abstract Data Type: Stacks ............................................................................. 86
10.9 A Survey of Search Methods ........................................................................................... 87
11 Lecture 11: Elements of Procedural Programming 89
11.1 Procedural Programming ............................................................................................... 89
11.2 OCaml Primitives for References ................................................................................... 89
11.3 Trying Out References ................................................................................................... 90
11.4 Commands: Expressions with Effects .............................................................................. 91
11.5 Iteration: the while command........................................................................................92
11.6 Private, Persistent References .........................................................................................92
11.7 Two Bank Accounts .........................................................................................................93
11.8 OCaml Primitives for Arrays ...........................................................................................94
11.9 Array Examples ............................................................................................................... 95
11.10 References: OCaml vs conventional languages .................................................................96
3
, This course has two aims. The first is to teach programming. The second is to present some
fundamental principles of computer science, especially algorithm design. Most students will have
some programming experience already, but there are few people whose programming cannot be
improved through greater knowledge of basic principles. Please bear this point in mind if you have
extensive experience and find parts of the course rather slow.
The programming in this course is based on the language OCaml and mostly concerns the functional
programming style. Functional programs tend to be shorter and easier to understand than their
counterparts in conventional languages such as C. In the space of a few weeks, we shall cover many
fundamental data structures and learn basic methods for estimating efficiency.
The first thing you will notice about this course is that there is an interactive version hosted online
at https://hub.cl.cam.ac.uk/, where you can login with your Cambridge Raven identity and
edit the code fragments in your browser. You are encouraged to do so – such edits will only persist
in your session, and will help you to explore the world of functional programming. If you are using
the web-based version, then you need to know a few concepts:
• The notebook consists of a sequence of textual and code snippets.
• The code snippets can be executed individually, and will ―remember‖ the results of the
previous snippets.
• To begin with, click on Cell / Run All in the menu to execute the entire notebook.
• You can later double click on any cell and modify its contents, and press Shift+Enter to
reevaluate its contents. This will only modify the current cell, so you will have to Run All
again to see the effects on the whole notebook.
• While editing longer snippets, you can also press Shift+Tab while typing to get more docu-
mentation hints about the code you are writing.
This course is lectured by Anil Madhavapeddy, with the practical exercises managed by Jonathan
Ludlam. These notes are translated from Lawrence C. Paulson‘s earlier course on Standard ML,
which had credits to David Allsopp, Stuart Becker, Gavin Bierman, Chloë Brown, Silas Brown,
Qi Chen, David Cottingham, William Denman, Robert Harle, Daniel Hulme, Frank King, Jack
Lawrence-Jones, Joseph Lord, Dimitrios Los, Farhan Mannan, James Margetson, David Morgan,
Alan Mycroft, Sridhar Prabhu, Frank Stajano, Alex Trifanov, Thomas Tuerk, Xincheng Wang,
Philip Withnall and Assel Zhiyenbayeva for pointing out errors. The current notes were ported to
OCaml in 2019 by Anil Madhavapeddy, David Allsopp, and Jon Ludlam and subsequently edited
by Jeremy Yallop. We thank Richard Sharp, Srinivasan Keshav, Ambroise Lafont, Vojtěch Tvrdík
and Jeremy Yallop for further feedback and corrections since 2020.
Some books that are complementary to this course are:
• OCaml from the Very Beginning by John Whitington.
4
Anil Madhavapeddy, Jonathan Ludlam
Computer Laboratory Version 1.6
Contents
1 Lecture 1: Introduction to Programming 5
1.1 Basic Concepts in Computer Science................................................................................. 5
1.2 Goals of Programming.......................................................................................................6
1.3 Why Program in OCaml? .................................................................................................. 7
1.4 A first session with OCaml ................................................................................................8
1.5 Raising a Number to a Power ............................................................................................9
1.6 Efficiently Raising a Number to a Power..........................................................................11
2 Lecture 2: Recursion and Efficiency 13
2.1 Expression Evaluation...................................................................................................... 13
2.2 Summing the first n integers ........................................................................................... 13
2.3 Iteratively summing the first n integers .......................................................................... 14
2.4 Recursion vs Iteration ...................................................................................................... 14
2.5 Silly Summing the First n Integers ................................................................................. 15
2.6 Comparing Algorithms: O Notation ................................................................................ 16
2.7 Simple Facts About O Notation ...................................................................................... 17
2.8 Common Complexity Classes........................................................................................... 17
2.9 Sample costs in O notation .............................................................................................. 18
2.10 Some Simple Recurrence Relations .................................................................................. 18
3 Lecture 3: Lists 21
3.1 The List Primitives ..........................................................................................................22
3.2 Getting at the Head and Tail ...........................................................................................22
3.3 Computing the Length of a List.......................................................................................24
3.4 Efficiently Computing the Length of a List ..................................................................... 25
3.5 Append: List Concatenation............................................................................................26
3.6 Reversing a List in 𝑂(𝑛2)................................................................................................................................ 26
1
, 3.7 Reversing a List in ........................................................................................................... 27
3.8 Lists, Strings and Characters ...........................................................................................28
4 Lecture 4: More on Lists 30
4.1 List Utilities: take and drop ........................................................................................... 30
4.2 Linear Search ................................................................................................................... 31
4.3 Equality Tests .................................................................................................................. 31
4.4 Building a List of Pairs .................................................................................................... 32
4.5 Building a Pair of Results ................................................................................................ 33
4.6 An Application: Making Change ..................................................................................... 33
4.7 All Ways of Making Change ............................................................................................34
4.8 All Ways of Making Change — Faster! ........................................................................... 35
5 Lecture 5: Sorting 37
5.1 How Fast Can We Sort?................................................................................................... 37
5.2 Insertion Sort ...................................................................................................................39
5.3 Quicksort: The Idea ........................................................................................................ 40
5.4 Quicksort: The Code....................................................................................................... 40
5.5 Append-Free Quicksort .................................................................................................... 41
5.6 Merging Two Lists ...........................................................................................................42
5.7 Top-down Merge sort .......................................................................................................42
5.8 Summary of Sorting Algorithms ......................................................................................43
6 Lecture 6: Datatypes and Trees 45
6.1 An Enumeration Type ...................................................................................................... 45
6.2 Declaring a Function on Vehicles ....................................................................................46
6.3 A Datatype whose Constructors have Arguments ...........................................................46
6.4 A Finer Wheel Computation ........................................................................................... 47
6.5 Error Handling: Exceptions ............................................................................................. 47
6.6 Exceptions in OCaml ...................................................................................................... 48
6.7 Making Change with Exceptions .....................................................................................49
6.8 Making Change: A Trace................................................................................................. 51
6.9 Binary Trees, a Recursive Datatype ................................................................................. 52
6.10 Basic Properties of Binary Trees ..................................................................................... 53
7 Lecture 7: Dictionaries and Functional Arrays 55
7.1 Dictionaries...................................................................................................................... 55
7.2 Binary Search Trees ......................................................................................................... 56
7.3 Lookup: Seeks Left or Right ............................................................................................ 56
7.4 Update ............................................................................................................................. 57
7.5 Aside: Traversing Trees (3 Methods)...............................................................................58
7.6 Efficiently Traversing Trees.............................................................................................. 59
7.7 Arrays .............................................................................................................................. 59
7.8 Functional Arrays as Binary Trees ................................................................................. 60
7.9 The Lookup Function ...................................................................................................... 61
7.10 The Update Function ......................................................................................................62
8 Lecture 8: Functions as Values 64
2
, 8.1 Functions Without Names ...............................................................................................64
8.2 Curried Functions ............................................................................................................ 65
8.3 Shorthand for Curried Functions..................................................................................... 67
8.4 Partial Application: A Curried Insertion Sort ................................................................ 68
8.5 map: the ―Apply to All‖ Function ..................................................................................69
8.6 Example: Matrix Transpose ............................................................................................69
8.7 Review of Matrix Multiplication......................................................................................70
8.8 Matrix Multiplication in OCaml ...................................................................................... 71
8.9 List Functionals for Predicates ........................................................................................ 71
8.10 Applications of the Predicate Functionals ....................................................................... 72
9 Lecture 9: Sequences, or Lazy Lists 75
9.1 A Pipeline ........................................................................................................................ 75
9.2 Lazy Lists (or Streams) ................................................................................................... 75
9.3 Lazy Lists in OCaml ........................................................................................................ 76
9.4 The Infinite Sequence: 𝑘, 𝑘 1, 𝑘 2,............................................................................. 77
9.5 Consuming a Sequence .................................................................................................... 77
9.6 Sample Evaluation ........................................................................................................... 78
9.7 Joining Two Sequences .................................................................................................... 78
9.8 Functionals for Lazy Lists ................................................................................................ 79
9.9 Numerical Computations on Infinite Sequences .............................................................. 79
10 Lecture 10: Queues and Search Strategies 82
10.1 Breadth-First v Depth-First Tree Traversal ................................................................... 82
10.2 Breadth-First Tree Traversal — Using Append .............................................................. 83
10.3 An Abstract Data Type: Queues.................................................................................... 83
10.4 Efficient Functional Queues: Idea ................................................................................... 83
10.5 Efficient Functional Queues: Code .................................................................................. 84
10.6 Breadth-First Tree Traversal — Using Queues................................................................85
10.7 Iterative deepening: Another Exhaustive Search ........................................................... 86
10.8 Another Abstract Data Type: Stacks ............................................................................. 86
10.9 A Survey of Search Methods ........................................................................................... 87
11 Lecture 11: Elements of Procedural Programming 89
11.1 Procedural Programming ............................................................................................... 89
11.2 OCaml Primitives for References ................................................................................... 89
11.3 Trying Out References ................................................................................................... 90
11.4 Commands: Expressions with Effects .............................................................................. 91
11.5 Iteration: the while command........................................................................................92
11.6 Private, Persistent References .........................................................................................92
11.7 Two Bank Accounts .........................................................................................................93
11.8 OCaml Primitives for Arrays ...........................................................................................94
11.9 Array Examples ............................................................................................................... 95
11.10 References: OCaml vs conventional languages .................................................................96
3
, This course has two aims. The first is to teach programming. The second is to present some
fundamental principles of computer science, especially algorithm design. Most students will have
some programming experience already, but there are few people whose programming cannot be
improved through greater knowledge of basic principles. Please bear this point in mind if you have
extensive experience and find parts of the course rather slow.
The programming in this course is based on the language OCaml and mostly concerns the functional
programming style. Functional programs tend to be shorter and easier to understand than their
counterparts in conventional languages such as C. In the space of a few weeks, we shall cover many
fundamental data structures and learn basic methods for estimating efficiency.
The first thing you will notice about this course is that there is an interactive version hosted online
at https://hub.cl.cam.ac.uk/, where you can login with your Cambridge Raven identity and
edit the code fragments in your browser. You are encouraged to do so – such edits will only persist
in your session, and will help you to explore the world of functional programming. If you are using
the web-based version, then you need to know a few concepts:
• The notebook consists of a sequence of textual and code snippets.
• The code snippets can be executed individually, and will ―remember‖ the results of the
previous snippets.
• To begin with, click on Cell / Run All in the menu to execute the entire notebook.
• You can later double click on any cell and modify its contents, and press Shift+Enter to
reevaluate its contents. This will only modify the current cell, so you will have to Run All
again to see the effects on the whole notebook.
• While editing longer snippets, you can also press Shift+Tab while typing to get more docu-
mentation hints about the code you are writing.
This course is lectured by Anil Madhavapeddy, with the practical exercises managed by Jonathan
Ludlam. These notes are translated from Lawrence C. Paulson‘s earlier course on Standard ML,
which had credits to David Allsopp, Stuart Becker, Gavin Bierman, Chloë Brown, Silas Brown,
Qi Chen, David Cottingham, William Denman, Robert Harle, Daniel Hulme, Frank King, Jack
Lawrence-Jones, Joseph Lord, Dimitrios Los, Farhan Mannan, James Margetson, David Morgan,
Alan Mycroft, Sridhar Prabhu, Frank Stajano, Alex Trifanov, Thomas Tuerk, Xincheng Wang,
Philip Withnall and Assel Zhiyenbayeva for pointing out errors. The current notes were ported to
OCaml in 2019 by Anil Madhavapeddy, David Allsopp, and Jon Ludlam and subsequently edited
by Jeremy Yallop. We thank Richard Sharp, Srinivasan Keshav, Ambroise Lafont, Vojtěch Tvrdík
and Jeremy Yallop for further feedback and corrections since 2020.
Some books that are complementary to this course are:
• OCaml from the Very Beginning by John Whitington.
4
