Pages in this section

• Week 0 - Assumed knowledge
  Last edited: 2026-02-05

  # Notes from Fundamentals course

  I followed this Fundamentals course to understand the basics.

  # Lecture 1: Hosts and devices

  Some terminology first:

  Host (networks)

  Client

  Server

• Week 1 - Are you ready?
  Last edited: 2026-02-05

  # C Programming

  Because this course focuses on operating systems, primarily covering Linux, it assumes that students have a reasonable understanding of the C programming language.

  # Concepts to Know

  For this course, a “reasonable understanding” would be defined as having used or been exposed to the following C concepts:

• Week 1 - Basic Model of Locality
  Last edited: 2026-01-28

  This lecture is based on the paper:

  The Input/Output Complexity of Sorting and Related Problems

  High performance computing

  This is a bad name, all computing should be high performance. This course is really about supercomputers, where you need to extract every last ounce of compute you have to solve the problem faster.

• Week 1 - Chapter 1 Machine Learning
  Last edited: 2024-01-13

  This is my notes from the first chapter of MachineLearningTomMitchell.pdf .

  1.1 Well posed learning problems

  Machine Learning

  Checkers

  If we want a programme to learn at checkers we simply need to define $T$, $P$, and $E$!

• Week 1 - Chapter 3, Finite Markov Decision Process
  Last edited: 2026-02-05

  Compulsory reading from Reinforcement learning: An introduction .

  # Finite Markov Decision Process

  Finite Markov Decision Process

  Using the function $p$ (defined in the finite Markov decision process), we can calculate some other probabilities.

  State transition probability: When in state $s_t$ and you take the action $a_t$ the probability of ending up in $s_{t+1}$:

• Week 1 - Course material
  Last edited: 2026-02-05

  # Reference Books

  • Operating System Concepts
  • Operating System Concepts: Essentials
  • Modern Operating Systems
  • Operating Systems: Three Easy Pieces

• Week 1 - Decision Trees
  Last edited: 2024-01-10

  Supervised learning

  Supervised learning falls into two main problems sets

  Classification problems - Mapping from a domain to some discrete set, and Regression problems - mapping from a domain to some continuous space like the Real numbers ($\mathbb{R}$).

  For example, making a decision on whether you should give someone a loan is a classification problem as there are only two outcomes - whereas mapping from someone’s picture to their age would be a regression problem.

• Week 1 - Dynamic Programming
  Last edited: 2025-12-05

  Dynamic programming is a method to speed up recursion especially when the recursive algorithm computes the same step multiple times.

  Fibonacci sequence

  by recursion

• Week 1 - Introduction
  Last edited: 2026-02-05

  Here are some questions you should be able to answer to start the course:

  • What are the advantages and disadvantages of a layered architecture? Modularity, Separation of concerns, and interchange of methods at different layers. Duplication of effort, more covert coupling, and additional overhead. • What are the differences and similarities between the OSI model and the five-layered Internet model? Connection between OSI and IPS models • What are sockets? Socket • Describe each layer of the OSI model. OSI • Provide examples of popular protocols at each layer of the five-layered Internet model. HTTP TCP ARP • What is encapsulation, and how is it used in a layered model? encapsulation • What is the end-to-end (e2e) principle? End to end principle • What are the examples of a violation of e2e principle?

• Week 1 - Introduction
  Last edited: 2026-06-10

  Relational databases have uses all across industry. First we motivate why they are useful by comparing it to a flat file database.

  CODD’s paper

  These are course notes which are enhanced by my reading of: A Relation Model of Data for Large Shared Data Banks .

• Week 1 - Introduction to BuzzDB
  Last edited: 2026-05-26

  In this course we will be using C++ to build a relational database called BuzzDB. In this lecture we cover what BuzzDB is, and why we use C++.

  Simplified introduction

  The BuzzDB shown here is a simplified, introductory version to illustrate the core concepts. Over the course we will evolve it into a more complete database with generic tuple types, schemas, and proper disk-based storage.

• Week 1 - Introduction to Compilers
  Last edited: 2026-01-28
  Compiler

  A program that translates source code written in one programming language into another programming language. Commonly the target programming language is machine code that is executable.

• Week 1 - Introduction to operating systems
  Last edited: 2026-02-05

  Operating system (OS)

  # Metaphor

  The OS is a lot like a toyshop manager. They are required to:

  • Direct the operational resources
    • Controls the use of employees’ time,
    • Distribute tools and parts between workers
  • Enforces working policies
    • Ensures fairness between workers,
    • Make sure toys are made safely,
    • How to clean up after the job has been completed.
  • Mitigates difficulty of complex tasks
    • Simplifies operations for each worker to do,
    • Chooses optimal task allocation to improve performance.

  In comparison an OS does the following:

• Week 1 - Knapsack Problem
  Last edited: 2026-02-05

  # Week 1 - Knapsack Problem

  Statement

  There are different versions of this problem:

  • Where you can have at most one version of each object,
  • Where you can have at most a given number of each object, and
  • Where you can have an infinite amount of each object.

  We will focus on the first problem for the next sections.

• Week 1 - Linear Classifiers and Gradient Descent
  Last edited: 2026-06-01

  The following quote defines machine learning:

  A computer program is said to learn from experience E with respect to some class of tasks T and performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.

  In short, the program’s capacity to do the task increases as it experiences more of it. This is in contradiction to traditional programs as hard-coded algorithms do not improve the more they run on the issues.

• Week 1 - Security Mindset
  Last edited: 2026-01-28

  We need security when two things are met:

  • We have something of value, and

  • We have a threat to that thing.

  # Things of value

  In the context of cyber security usually the thing of value is information. However, there are examples of using cyber attacks to attack things in the physical world such as the Stuxnet attack on Iran’s nuclear facility or digital attacks on electric grids.

• Week 1 - Smoov & Curly's Bogus Journey
  Last edited: 2025-05-12

  # Review

  The first part of this course is a review of:

  Week 12 - Reinforcement learning

  There is a change of notation within this course compared to the referenced lecture. Instead of using $U(s)$ for the utility, we use $V(s)$ for value. Instead of considering the reward function $R: S \rightarrow \mathbb{R}$, we consider it $R: S \times A \rightarrow \mathbb{R}$, i.e. the reward takes into account the action you have taken. Therefore, the Bellman equation in this notation is restated below.

• Week 1 - Supplementary Introduction to Reinforcement Learning
  Last edited: 2025-05-13

  Going down in levels of specificity:

  • Artificial intelligence: The ability of machines to simulate human behaviour.
  • Machine learning: The ability of machines to simulate human behaviour by learning from data.
  • Reinforcement Learning: The ability of machines to simulate human behaviour by learning from data that is simultaneously sequential, evaluative, and sampled.

  

  Later in the course we will be adding deep learning into our use of reinforcement learning . This is mainly using large neural networks to assist with the learning process.

• Week 1 - Writing and reading papers
  Last edited: 2024-01-21

  # Ten simple rules for reading a scientific paper by Maureen A. CareyID, Kevin L. Steiner, William A. Petri Jr

  Reading articles is a large part of research and you should try to keep up to date with your area of interest. However, may people struggle with reading articles and this guide is some tips and tricks for starting.

• Week 10 - Distributed Maxtrix Multiply
  Last edited: 2026-05-27

  In this lecture we are looking to optimise the matrix multiply algorithm. In this lecture this will be, given $A, B, C$ 3 matrices of dimension $m \times k$, $k \times n$ and $m \times n$ calculate $C = C + A \cdot B$. This means that for a given $i, j$ we need to calculate:

  $$ C_{i,j} = C_{i,j} + \sum_{l=1}^k a_{i,l} b_{l,j} $$

  The serial implementation is therefore:

  for i = 1 to m do:
    for j = 1 to n do:
      for l = 1 to k do:
        C[i,j] = C[i,j] + A[i,l] * B[l,j]
  

  Which can be parallelised along i-j and have the final computation be done by a reduce:

• Week 10 - Failures and Recovery
  Last edited: 2025-11-30

  # Week 10 - Failures and Recovery

  Within an operating system, crashes will occur. When they do they need to leave us in state we can recover from. To do this we need persistence and recovery.

  # Lightweight Reliable Virtual Memory (LRVM)

  Whilst the operating system and its subsystems are changing objects in memory if a crash occurs before it has a chance to save it to disk it can leave the OS in a broken state. To combat this LRVM creates an interface to make some objects in virtual memory persistent on the disk. The key to this working is to make this fast and have a clean, easy to use interface for subsystem designers.

• Week 10 - Feature selection
  Last edited: 2026-02-05

  Feature selection is the process of deciding what features of the data are worth training on. Then picking the subset of them that are the most important. The reason to do this is:

  • Knowledge discovery, interpretability, and insight.
    • When you get the results back you are going to have to be able to explain them.
  • The curse of dimensionality
    • If you put too many dimensions in - it will decrease the accuracy of your models!

  # How hard is this problem?

  Assume we want to know the best $m \leq n$ subset of columns. The only way to verify it is the best is to check them all so it is $\binom{n}{m}$. If you don’t know $m$ then it is $2^n$.

• Week 10 - Feature transformation
  Last edited: 2026-02-05

  Feature transformation is the problem of pre-processing a set of features to create a new (smaller/compact) feature set, while retaining as much information as possible. It is a map $p: \mathbb{F}^N \rightarrow \mathbb{F}^M$ where you usually want $M < N$.

  In this course we will focus on linear  feature reduction where $p$ is a linear map .

  Note

  Feature selection is a special case of feature transformation

• Week 10 - Graph problem complexity
  Last edited: 2023-11-19

  # Independent set problem

  independent set

  Therefore we have the following problem.

  Statement

  Though this problem is not known to be in NP as to verify if a set is the largest set we would require to calculate the set of largest size. However, we can edit this question to make one that is in NP .

• Week 10 - Neural attention models
  Last edited: 2026-07-01

  In this lecture we will look more at the foundation of attention and relate this to how a transformer works and was built.

  # Softmax deep dive

  Recall the definition of softmax for a vector $x = \{x_i\}_{i = 1}^N$.

  $$ \text{softmax}(x) = (\frac{e^{x_i}}{\sum_{j=1}^N e^{x_j}})_{i = 1}^N $$

  This is a probability vector over the entries of $\{x_i\}_{i=1}^N$. There are some interesting things to note about this:

• Week 10 - NP overview
  Last edited: 2023-11-11

  # Complexity classes

  Nondeterministic Polynomial time (NP)

  In this class we use the search problem definition.

  Search problems

  Note here we have.

  Statement

  There is an open problem.

  P equals NP or P not equals NP

• Week 10 - NP-completeness
  Last edited: 2023-11-11

  We are going to assume the following.

  Statement

  # k-SAT

  We are going to show that the k-SAT problem is NP-Complete for $k \geq 3$.

  k-SAT

  To do this we will show 3-SAT is NP-complete which as 3-SAT is a subproblem to k-SAT for $k \geq 3$ this will prove all we need to.

• Week 10 - Query Execution
  Last edited: 2026-07-07

  In this lecture we cover how to make Query Execution generic. We will do this by making query logic modular so we can compose them to make larger queries. This provides the following benefits:

  • Modularity: Each module encapsulates a specific manipulation.

  • Isolation: With a defined interface we don’t need to consider how changes to the logic of one component affects others.

  • Flexibility: Enables us to choose different ways to execute the same query, meaning we can pick the best approach at run time.

  • Week 10 - Register Allocation
    Last edited: 2026-05-27

    So far the front end has converted the input code into a format that assumes infinite registers - the three-address code. However, real machines are limited by the number of registers they have available. Ideally we would keep all numbers we need to use in registers and only use memory when we need it. These may also be for different purposes such as function inputs, for floats or ints, or be restricted for the stack pointer. We need to factor all this in when we go from our IR to assembly code. Therefore, this process has two different stages:

  • Week 10 - Synchronization Constructs
    Last edited: 2025-03-26

    # Additional reading

    • The Performance of Spin Lock Alternatives for Shared-Memory Multiprocessors

    # Synchronization

    Synchronization

    Previously we discussed mutexes and condition variables . However these had a couple of downsides:

  • Week 10 - Video applications
    Last edited: 2026-02-05

    # Additional reading

    # Important Readings

    VoIP: A comprehensive survey on a promising technology https://www.sciencedirect.com/science/article/abs/pii/S1389128609001200Links to an external site.

    MPEG: A Video Compression Standard for Multimedia Application https://dl.acm.org/doi/pdf/10.1145/103085.103090Links to an external site.

    The JPEG Compression standard https://ieeexplore.ieee.org/document/125072Links to an external site.

  • Week 11 - CDNs and overlay networks
    Last edited: 2026-02-05

    # Reading

    # Important Readings

    The Akamai Network: A Platform for High-Performance Internet Applications https://dl.acm.org/doi/10.1145/1842733.1842736Links to an external site.

    Open Connect Everywhere: A Glimpse at the Internet Ecosystem through the Lens of the Netflix CDN https://arxiv.org/pdf/1606.05519.pdf Links to an external site.

  • Week 11 - Code optimizations
    Last edited: 2026-03-20

    In the middle of the compiler we look at making the code more optimal in terms of runtime, resource usage, and code size whilst keeping the same functionality. There are multiple ways we can do this:

    • Discover and propagate some constant values,

    • Move a computation to a less frequently executed place (eliminate repeated steps in loops),

    • Specialize some computation based on context (e.g. compile time operations on constants and saving them as constants),

    • Week 11 - Distributed memory sorting
      Last edited: 2026-05-27

      In this lecture, we will see different approaches to sorting on a distributed memory system.

      # Bitonic Sort

      As a reminder on Bitonic sort review Comparison based sorting .

      # Bitonic Merge

      Bitonic sort is essentially iterative stages of performing a Bitonic merge on incrementally larger input sequences, therefore we first look at the bitonic merge. Throughout suppose we have $n$ and $p$ both powers of 2 where $p \vert n$. Therefore each node will start with $n/p$ elements of the list.

    • Week 11 - IO management
      Last edited: 2025-04-09

      # Model of a IO device

      Whilst an IO device can come in many forms we model them similarly.

      

      These have 3 registers:

      • Status: Some indicate the state of the device.
      • Command: Used by the CPU to control the device.
      • Data: Used to transfer data in and out of the device.

      Then what happens internally is controlled by the micro controller on the device.

    • Week 11 - Linear Programming
      Last edited: 2026-06-18

      In broad terms a linear programme is an optimisation problem of a linear function where there are linear bounds on the variables.

      Max flow problem

      We are given a directed graph $G = (V,E)$ with capacities $c: E \rightarrow \mathbb{R}_{>0}$ and source $s \in V$ and sink $t \in V$.

    • Week 11 - Markov Decision Processes
      Last edited: 2024-04-03

      Markov decision process

      Find home

      Suppose we have a world with 12 states defined by a 2d grid $S = \{(x,y) \vert 1 \leq x \leq 4, 1 \leq y \leq 3\}$. Where state $(2,2)$ is can’t be entered, $(4,3)$ is home, $(4,2)$ is a pit of death, and $(1,1)$ is where we start.

    • Week 11 - Neural Machine Translation
      Last edited: 2026-07-01

      In this lecture we will look at the application of NLP to machine translation. This can be hard due to multiple factors:

      • Sentences are ambiguous like ‘I saw her duck’ or ‘The professor said on Monday we would have an exam’ both could be understood to mean multiple things. So context is important.

      • Different languages have different grammatical structure and words that don’t exist in other languages.

      • Translation might not be one-to-one instead one to many or many to one.

      • Week 11 - Operator Framework
        Last edited: 2026-07-14

        In this lecture, we extend the Query framework.

        # Logical Predicates

        In the previous lecture we saw support for simple predicates such as comparisons. However, this did not support logical operations like AND and OR. Here we extend the Predicates to do exactly that. First we implement a predicate interface.

        class IPredicate {
        public:
          virtual ~IPredicate() {}
          virtual bool check(const std::vector<std::unique_ptr<Field>> &tupleFields) const = 0;
        };
        

        Our previous Predicate class implements this interface with the only important interface being the check method. Though we extend this further with the ComplexPredicate class that supports logical operators.

      • Week 11 - Security
        Last edited: 2026-01-28

        # Principles of information security

        Information security is a large part of the developer industry. This field has whole masters courses dedicated to its study. However, lots of the modern terminology was invented by visionaries in the early years of computer history.

        The notes in this section are based on the following paper:

        Protection and the Control of Information in Computer Systems

      • Week 12 - Distributed BFS
        Last edited: 2026-04-07

        In this lecture, we will look at how we can distribute a BFS algorithm among multiple processors. This relies on the idea of representing a graph as an adjacency matrix .

        # Calculating distances

        Take the BFS algorithm to calculate the distance each node is away from a given node. This has been covered before but can be expressed as below.

      • Week 12 - Future of the Internet
        Last edited: 2026-02-05

        # Reading

        # Optional Readings

        Machine Learning and Networking Applications

        Routing or Computing? The Paradigm Shift Towards Intelligent Computer Network Packet Transmission Based on Deep Learning https://ieeexplore.ieee.org/document/7935536

        CherryPick: Adaptively Unearthing the Best Cloud Configurations for Big Data Analytics https://www.usenix.org/system/files/conference/nsdi17/nsdi17-alipourfard.pdf

      • Week 12 - Generative Models
        Last edited: 2026-07-21

        Previously, we have investigated supervised learning where we want to estimate $\mathbb{P}(y \vert x)$ i.e. the probability of a label given some input. Next we will look at unsupervised learning where instead we just want to look at $\mathbb{P}(x)$ i.e. the distribution of inputs. This is a complex way to say - instead of labeling some data we want to generate a sample from it. For example, given lots of pictures of cats — can you generate a new picture of a cat? This is actually a hard task to do.

      • Week 12 - Halting problem
        Last edited: 2023-11-13

        Statement

        We want to show that that this problem is computationally impossible or in other words it is undecidable .

        undecidable

        The Halting problem is undecidable

      • Week 12 - Instruction Selection
        Last edited: 2026-05-27

        In this lecture, we will learn how to map from the IR to the target instruction set.

        Instruction Set Architecture (ISA)

        The ISA is the set of instructions that a processor can execute. These cover 4 major categories:

      • Week 12 - Knapsack complexity
        Last edited: 2023-11-13

        We are going to prove that the Knapsack-search is NP-complete . We will do this using the 3-SAT but first going through the Subset-sum problem .

        # Subset-sum problem

        Statement

        This can be solves using Dynamic Programming in a similar way to the Knapsack problem in $O(nt)$. However, similar to the Knapsack problem this is not a polynomial time algorithm in the length of the input as that is $n\log_2(t)$. Therefore it is Pseudo-polynomial .

      • Week 12 - Max-SAT approximation algorithm
        Last edited: 2023-11-19

        In this lecture we consider the a similar problem to the SAT problem .

        Max-SAT

        This is NP-hard .

        Max-SAT is NP-hard

        Therefore it is unlikely to find any algorithm that will solve the problem quickly. However we will look at using linear programming to approximate a solution.

        # Approximate algorithms

        Let $f$ be a boolean function in CNF with $m$ clauses. Let $m^{\ast}$ denote the solution to the max-SAT problem for $f$.

      • Week 12 - Query Compilation
        Last edited: 2026-07-14

        In this lecture we go from a text based query to something we can run.

        # Query parsing

        In real databases we will use a parser to convert a text query into an AST. This then can be turned into a pipeline of operators based on the input.

        However, for buzzdb we use a simpler approach using regex and a struct to carry query components.

      • Week 12 - Reinforcement learning
        Last edited: 2024-04-06

        Transitions (MDP)

        Reinforcement learning

        There are 4 kinds of process we think about:

        • Planning:
          • Input: Model (such as Markov decision process )
          • Output: Policy
          • E.g. Value iteration (MDP) or Policy Iteration (MDP)
        • Learning:
          • Input: Transitions
          • Output: Policy
          • E.g. Reinforcement learning
        • Modelling:
          • Input: Transitions
          • Output: Model
        • Simulation:
          • Input: Model
          • Output: transitions

        We can compose these strategies in two major ways.

      • Week 12 - Virtualization
        Last edited: 2025-04-12

        # Additional reading

        • “Formal Requirements for Virtualizable Third Generation Architectures”

        # Virtualization

        Virtualization

        Virtual machine monitor (VMM)

        Benefits for virtualization:

        • Consolidation: Allows you to split one machine into many, allowing you to consolidate different applications that need different environments to run.
        • Migration: Makes it easy to move applications from one machine to another.
        • Security: Isolates applications from one another.
        • Debugging: Makes it easy to spin up similar instances of crashed programs to debug.
        • Support for legacy OS: Easy to host an application that needs a legacy operating system to run.
        • Support for OS research: Makes it easy to change an operating system and observe the effects of that.

        There are two main methods of virtualization:

      • Week 13 - Embeddings
        Last edited: 2026-07-21

        When we have large quantities of data it can be useful to understand it in relation to one another. By embedding this data into a high dimensional vector space so that the relative distances preserve some meaning, we can speed up asking questions about our data. The most common example is embedding words into a vector space using the word2vec algorithm - which using vector distances can tell us how pairs of words relate to one another.

      • Week 13 - Game theory
        Last edited: 2026-02-05

        Game theory

        # 2-player zero-sum finite game of perfect information

        This is a lot of words but these games are like tick tack toe or noughts and crosses. Whilst these are fun they all boil down to a payoff matrix for the different strategies you take. Like the following

        $$ \begin{array}{c|ccc} \ 1 & a & b & c\\ \hline x & 1 & 0 & -1 \\ y & -1 & 0 & 1 \\ \end{array} $$

        to read this table, if the first player at the top picks action $a$ and the second player on the rows picks $x$ then player one gets 1 point whereas player two gets -1 point. This is the zero-sum aspect to the game. (Note the game could be non-deterministic but we just take expectation to find the values in the grid.)

      • Week 13 - Graph partitioning
        Last edited: 2026-05-27

        In some distributed algorithms we need to partition a graph into subgraphs to break the computation across processes - for example breadth first search. When partitioning this graph any edge that crosses a partition boundary represents some information that will need to pass between two processes. Therefore, it would be good to partition the graph in a way to minimise the number of edges crossing between the partitions whilst being roughly equal.

      • Week 13 - Known NP-complete problems
        Last edited: 2026-06-18

        # Week 13 - NP-complete problems

        The following problems are known to be NP-complete :

        • Lectures
          • SAT problem - SAT is NP-complete
          • k-SAT - k-SAT is NP-complete for k greater than or equal to 3
          • Independent set of a given size - Independent set of a given size is NP-complete
          • Clique of a given size problem - Clique of a given size problem is NP-complete
          • Vertex cover of a given size - Vertex cover of a given size is NP-complete
          • k-colourings problem (graphs) - The k-colourings problem is NP-complete
          • Knapsack-search - Knapsack-search is NP-complete
          • Subset-sum problem - Subset-sum problem is NP-complete
        • Book
          • Traveling salesman problem (search) - ???
          • Rudrata cycle problem - ???
          • Balanced cut problem - ???

      • Week 13 - Procedure Abstraction
        Last edited: 2026-05-27

        In this lecture we cover how a compiler handles function calls. These function calls could be to functions defined within the same code, or outside libraries that the compiler will need to ’link’ to.

        # Variable scopes

        When we deal with function calls, where variables are defined becomes increasingly important. We should choose which variables a function has access to carefully. First a reminder of where variables could be stored within a virtual address space as below.

      • Week 13 - Query Optimisation
        Last edited: 2026-07-14

        In this lecture we look at three optimisations for queries: row vs column storage, compression, and vectorised execution.

        # Row vs Column Storage

        In our current implementation we store tuples in pages. This means that each row of data is stored together. Whilst this is conceptually simple this means that we have to store mixed data types together on the same page. This has a number of implications:

      • Week 13 - Remote Procedure Calls
        Last edited: 2025-04-12

        # Additional reading

        • Implementing Remote Procedure Calls

        # Remote procedure calls (RPC)

        Remote procedure calls (RPC)

        To achieve this RPC has some requirements:

        • Offers a client and server interface.
        • Implements a procedure call Interface.
          • When RPC was invented procedural languages were big, this is synchronous and when it is called remote procedure call.
        • Type checking.
          • This offers error handling, and
          • packet bytes interpretation.
        • Cross-machine conversations.
        • Higher-level protocol.
          • Access control, fault tolerance, and
          • Can support different transport protocols.

        Below is an example flow of an RPC call:

      • Week 14 - Distributed file systems
        Last edited: 2026-02-05

        # Additional reading

        “Caching in the Sprite Network File System”

        # Distributed file system

        Distributed file system (DFS)

        There are different models for distributing files:

        • Client/server model: A client with the file system talks to a single server who has all the files.
        • Client/server-cluster: A client contacts a cluster of servers who all have files the client can get files from. This can take different forms
          • Replicated: Each server has all the files.
          • Partitioned: each server serves part of the file system.
          • Both: Files are replicated and partitioned between machines (this is functionally how most large providers operate).
        • Peer-to-peer: A cluster of computers act as peer backups for one another. (This will be covered in more detail next lecture.)

        # Implementation

        There are different models for a Distributed file system (DFS) in the client server model.

      • Week 15 - Distributed shared memory
        Last edited: 2025-04-13

        # Additional reading

        • Distributed Shared Memory: Concepts and Systems

        # Distributed shared memory

        Distributed shared memory is similar to a distributed file system however all clients are also clients to others. They share the state mutually.

      • Week 15 - Markov Chains
        Last edited: 2026-02-05

        To talk about Markov chain it is good to recap what a probability matrix is:

        Stochastic matrix

        Now we can define a Markov chain .

        Markov chain

        Simple Markov chain

        Suppose we have 4 states with the following probabilities to go between them. This is commonly represented as a edge weighted directed graph . In terms of a probability matrix it would be represented as

      • Week 16 - Datacenter technologies
        Last edited: 2026-02-05

        # Week 16 - Data-center technologies

        # Internet services

        An internet service is simply one offered over a web interface. These normally consist of 3 layers:

        • Presentation: Static content.
        • Business logic: Dynamic content.
        • Database tier: Data storage.

        Whilst these layers are separated here they may be implemented on the same machine. Middleware can be offered to integrate the different layers together.

      • Week 2 - Cache-Oblivious Algorithms
        Last edited: 2026-01-23
        Optional reading

        This lecture is optional reading in my course and will not be examinable.

      • Week 2 - Chain Matrix Multiply
        Last edited: 2023-12-03

        The goal is this problem is, given a number of matrices what is the most efficient way to multiply them together?

        Lets say we have matrices $A$, $B$, $C$ and $D$ and they have different sizes such that we can multiply $A B C D$. Whilst matrix multiplication might be associative there might be a more efficient way to multiply them together!

      • Week 2 - I/O Avoiding Algorithms
        Last edited: 2026-05-27

        In this lecture, we will examine different classical algorithms and try to calculate their number of transfers in the Von Neumann model introduced in the previous lecture.

        # Merge sort

        Merge sort divides the array into small chunks. Then merges each of those chunks into one another to produce a sorted array. This runs in $O(n \log n)$ time. So there are two steps to this:

      • Week 2 - Neural networks
        Last edited: 2026-02-05

        The basis of all neural networks is a simplified model of a neuron in the human body.

        Perceptron (neural network)

        Where we define an activation function as.

        Activation function

        First we will just take the function to be Binary step which introduces an extra parameter $\theta$.

        Binary step

      • Week 2 - Neural Networks
        Last edited: 2026-06-01

        # Neural Networks

        To move beyond the linear classifier from the previous layer we develop a neural network. A ’neuron’ has a single value derived from a linear combination of other neurons that can be modified by a non-linear ‘activation function’ such as a sigmoid function. These are normally arranged in ’layers’ where between layers there is a complete set of connections. Each layer will have the same activation function - meaning this can functionally be modeled as $y_{n+1} = A(W y_{n})$. Here $A$ is the activation function and $W$ is a matrix of weights. The ‘deep’ in deep learning refers to the number of layers. The first layer is the input layer and the last layer is the output layer. Layers in between are called hidden layers. We refer to these networks as $n$-layer neural networks - normally we discount the input layer here so a 2 layer neural network will have 1 hidden layer.

      • Week 2 - OS Structure Overview
        Last edited: 2025-08-29

        The OS structure is the way OS is organised with respect to the applications it serves and the underlying hardware it manages.

        Some desirable traits for this to have are:

        • Protection: Defending the user from the OS’s activities but also the OS from anything run by the user. Similarly each user from one another.
        • Performance: The time taken to run the services the OS offers.
        • Flexibility: The ability to adapt the services the OS offers for different use cases.
        • Scalability: The performance of the OS increases as the resources provided increases.
        • Agility: Adapting to changes in application needs or resource availability.
        • Responsiveness: The ability to respond to events in a timely manner.

        # Different OS Structures

        # Monolithic OS

        In a monolithic OS, all OS services run in a separate address space than user applications. This means all access to the underlying hardware requires a context switch to kernel space.

      • Week 2 - Processes and Process Management
        Last edited: 2026-02-05

        Process

        # Aside

        Heap (OS)

        Stack (OS)

        address space

        # Metaphor

        A process is like an order of toys:

        • State of execution:
          • Completed,
          • waiting, or
          • In progress.
        • Parts and temporary holding area
          • Pieces used to make the toy, or
          • Containers to put the pieces.
        • May require special hardware:
          • Sewing machine or
          • glue gun.

        This is an analogy to an OS where a process has:

      • Week 2 - Regression and classification
        Last edited: 2024-01-17

        Regression history

        Regression problems

        The name comes from regression to the mean , this was the technique they used to first talk about it - then the word regression for the technique stuck.

        Polynomial Regression

        Polynomial regression

        Once we have an objective function we can use training data to fit the parameters $c_{p}$.

      • Week 2 - Regular expressions and DFA
        Last edited: 2026-01-28

        In the lexical analysis phase of the compiler we need to convert a sequence of characters into tokens. First, let’s define formally what a token is.

        Token

        A token is a tuple consisting of:

      • Week 2 - Reinforcement Learning Basics
        Last edited: 2025-05-14

        When evaluating different learners we normally evaluate them by the policy they produce. However, different methods of learning can create policies in different ways - therefore we may need to also consider:

        • Computation complexity: The time it takes for that learner to come up with that policy.
        • Sample complexity: The amount of interactions with its environment it needs to come up with that policy.

        We don’t normally think about space complexity unlike other subjects - since that is not normally a limiting factor.

      • Week 2 - Shortest Paths
        Last edited: 2026-06-18
        Shortest path problem

        Given a directed graph $(V, E)$ with edge weights $w: E \rightarrow \mathbb{R}$ and a start vertex $s \in V$ - the shortest path problem is to find the shortest distance between $s \in V$ and $z \in V$ for every $z$. This is called $\mbox{dist}(z)$ with the formal definition

      • Week 2 - Storage Management
        Last edited: 2026-05-27

        In database applications we use primarily two types of storage:

        • DRAM (dynamic random access memory): To speed up queries and access.

        • Disk: For permanent storage.

        The interplay between these plays an important role in making a database both fast and reliable.

        # Expanding Tuple

        In the previous lecture we defined a tuple to have two integer values key and value. However, in a proper database we want to support a dynamic table schema that is specified by the user. Therefore, we add a polymorphic container for values of our rows called Field. This uses an enum to specify its type and unique_ptr to support the value.

      • Week 2 - Temporal Difference Learning
        Last edited: 2025-05-20

        Within reinforcement learning there are broadly 3 types of algorithms:

        1. Model-based: These algorithms first aim to understand the environment by building or learning an explicit model of it. This model describes how the environment behaves (e.g., transition probabilities and rewards).
           1. Model Learning/Update: Run through an example (an interaction with the environment) to collect data and update the parameters of a MDP model. This typically involves estimating state transition probabilities and reward functions.
           2. Planning/Solving: Use the learned MDP model (e.g., using algorithms like Value iteration (MDP) or Policy Iteration (MDP) ) to generate an optimal (or near-optimal) value function .
           3. Policy Derivation: Use the calculated value function and the learned model to derive an optimal policy . This policy dictates the best action to take in each state, often by choosing the action that maximizes the expected future reward (e.g., using argmax over the Q-values derived from the value function and model).
        2. Value-function based (model-free): These algorithms bypass the need to build an explicit model of the environment. Instead, they directly learn a value function (or action-value function) that estimates the goodness of states or state-action pairs.
           1. Value Function Update: Run through an example (an interaction with the environment) and use the observed outcomes (rewards and next states) to directly update the value function . This might be a state-value function V(s) or, more commonly, an action-value function Q(s,a), which estimates the expected return of being in state s and taking action a.
           2. Policy Extraction: Implicitly or explicitly derive a policy for each state by evaluating the actions that lead to the highest estimated value. For Q-functions, this often means choosing the action a that maximizes Q(s,a) for a given state s.
        3. Policy Search (or Policy Optimization): This approach directly searches for an optimal policy without necessarily learning a value function or a model. The goal is to find a policy that directly maps states to actions and maximizes the cumulative reward.
           1. Policy Evaluation and Update: Run through an example using the current policy . Based on the observed outcomes (rewards and trajectories), directly update the parameters of the policy to improve its performance. This often involves gradient-based methods where the policy parameters are adjusted in the direction that increases the expected return.

        The different approaches have varying trade-offs. Generally, model-based approaches are often more computationally intensive for the planning step but can be more sample efficient (requiring fewer interactions with the environment) because they can “plan” internally without needing new real-world data for every decision. Conversely, model-free approaches (including value-function based and policy search) are typically less computationally intensive per update (as they don’t involve a full planning step) but are often more sample intensive, requiring many interactions with the environment to learn effectively. Policy search methods, in particular, can be good for continuous action spaces and may sometimes converge faster than value-based methods in certain complex scenarios, but they can also be more prone to local optima.

      • Week 2 - Transport and application layer
        Last edited: 2024-05-24

        # Important Readings

        CUBIC: A New TCP-Friendly High-Speed TCP Variant https://www.cs.princeton.edu/courses/archive/fall16/cos561/papers/Cubic08.pdfLinks to an external site.

        # Book References

        Kurose-Ross (Edition 6): Sections 3.1.1, 3.2, 3.3, 3.4, 3.5.5, 3.6

        Peterson Section 6.3

        # Optional Readings

        Congestion Avoidance and Control https://ee.lbl.gov/papers/congavoid.pdfLinks to an external site.

      • Week 3 - Ensemble Bagging and Boosting
        Last edited: 2024-01-24

        Ensemble learning

        The idea of Ensemble learning is to look at a subset of data and try to model that well. If we do that to enough small patches we hope we can combine this to give us a good overall understanding of the data.

        This is a powerful idea when the function we are trying to map doesn’t globally generalise but instead locally generalises like when people try to filter out spam from your inbox.

      • Week 3 - Fast Integer Multiplication
        Last edited: 2026-06-18
        Multiplying $n$-bit integers problem

        Given $n$-bit integers $x$ and $y$ what is $z = xy$?

      • Week 3 - Instance Based Learning
        Last edited: 2025-12-05

        Instance-based learning

        # K-nearest neighbour

        k-nearest neighbour

        # Run times

        Instance-based learning is often called “lazy” learning because you delay computation until query time. As you can see in the table below, we assume $A = B = \mathbb{R}$ and that the input training data is sorted.

      • Week 3 - Intradomain routing
        Last edited: 2024-05-29

        # Important Readings

        Experience in Black-box OSPF Measurements http://conferences.sigcomm.org/imc/2001/imw2001-papers/82.pdfLinks to an external site.

        # Book References

        If you have access to the Kurose-Ross book and the Peterson book, you can find the list of chapters discussed in this lecture. As mentioned in the course schedule, purchasing the books is not required.

      • Week 3 - Linear-Time Median
        Last edited: 2026-06-18
        Median list problem

        Given an unsorted list $A = [a_1, \ldots, a_n]$ of $n$ numbers - you want to find the median ($\lceil \frac{n}{2} \rceil$) element.

      • Week 3 - Optimization of Deep Neural Networks
        Last edited: 2026-06-16

        Through backpropagation we get a learning method that is generalisable to a lot of structures. However, picking the best structure requires a lot of knowledge and intuition. For example:

        • Sometimes adding an additional layer can dramatically reduce the size of earlier layers.

        • There are structures like CNNs which model real processing of photos.

        • Theoretical experiments show that ‘gentle’ dimension reduction can lead to better performance.

        The decisions we need to make are:

      • Week 3 - Regular expressions and NFA
        Last edited: 2026-01-19

        This lecture focuses on how to construct a DFA from a given RegEx algorithmically. To do this we will:

        1. Introduce an easier object to work with called a Non-deterministic Finite Automaton (NFA).

        2. Show that operations in RegEx can be converted into ways to combine NFAs together.

        3. We will prove that an NFA can be converted into a DFA.

        4. We will try to minimise this representation.

        This will give us the algorithm to go from RegEx to a minimal DFA.

      • Week 3 - Slotted Pages
        Last edited: 2026-05-27

        In the previous lecture we introduced the Page for Tuples. In this lecture we develop the ideas to abstract away the management of data in memory vs on disk.

        # Slotted Page

        Previously we used a Page to collect Tuples into a single object. However, we lazily placed these into a vector to store them within the page. Each time we delete a Tuple from this Page, the page has to reshuffle all the data in the vector to remove the gap. Also, this means the index into the vector is not a stable identifier for any Tuple, thus making it hard to form indexes on top of it. Therefore, we introduce the concept of a Slotted page.

      • Week 3 - Solving Recurrences
        Last edited: 2026-06-18

        # $T(n) = 4T\left (\frac{n}{2}\right ) + O(n)$

        First step is to replace the Big-O notation . Let $c > 0$ such that

        $$T(n) \leq 4 T\left ( \frac{n}{2} \right ) + cn, \mbox{ and } T(1) \leq c.$$

        Lets keep reapplying this inequality

        $$\begin{aligned} T(n) \leq & cn + 4T\left ( \frac{n}{2} \right )\\ \leq & cn + 4\left [ 4T\left ( \frac{n}{2^2} \right ) + \frac{cn}{2} \right ]\\ \leq & cn (1 + \frac{4}{2}) + 4^2T\left ( \frac{n}{2^2} \right )\\ \leq & cn (1 + \frac{4}{2}) + 4^2\left[ 4T\left ( \frac{n}{2^3} \right ) + \frac{cn}{2^2} \right ]\\ \leq & cn \left (1 + \frac{4}{2} + \left ( \frac{4}{2} \right )^2 \right) + 4^3T\left ( \frac{n}{2^3} \right )\\ \leq & cn \left ( \sum_{i=0}^{k-1} \left ( \frac{4}{2} \right )^i \right ) + 4^kT\left ( \frac{n}{2^k} \right ) \end{aligned}$$

        Now lets run this till $k = \log_2(n)$ then $\frac{n}{2^k} = 1$.

      • Week 3 - Supplementary planning methods
        Last edited: 2025-05-22

        # Return

        In Reinforcement learning some people interpret the goal to be maximizing the rewards. However, with rewards sometimes distant from the current action - functionally most algorithms try to maximize the return.

        Return (RL)

        # Value function

        value function

      • Week 3 - Threading and concurrency
        Last edited: 2026-02-05

        “An Introduction to Programming with Threads”  by Birrell

        Thread

        # Visual metaphor

        Threads are like workers in a toy shop:

        • A thread is an active entity
          • Executing unit of toy order
        • Works simultaneously with others
          • many workers completing toy orders
        • requires coordination
          • sharing tools, parts, workstations

        In comparison to a thread:

      • Week 3 - Virtualization
        Last edited: 2025-09-04

        As a refresher please read:

        Week 12 - Virtualization

        # Memory Virtualisation

        # Address Translation

        When hosting guest operating systems on top of a hypervisor we need to make memory appear as it would to a normal OS. For the CPU cache which is physically tagged, there is no special operations we need to perform. However, for virtual memory we need to be able to map it to ‘machine memory’ correctly.

      • Week 3 - What Goes Around Comes Around... And Around...
        Last edited: 2026-06-18

        Paper: What Goes Around Comes Around… And Around… — Stonebraker & Pavlo, SIGMOD Record 2024.

        A retrospective on 20 years of data modelling and DBMS architecture since the original 2005 “What Goes Around Comes Around.” The central argument: every non-relational data model since 2005 has either died, become a permanent niche, or gradually converged toward SQL and the relational model. SQL absorbs the best ideas from challengers and keeps winning.

      • Week 3 - Work-Span model
        Last edited: 2026-01-25

        In this lecture we explore a method of parallelisation called the work-span model. This uses DAGs to represent a computation. Where each node is a computation that needs to be run and arrows between nodes represent dependencies. We will assume this is connected, and has a start/stop vertex.

        

        We will run these on a PRAM machine. This is a machine with multiple processors attached to some memory. Here we get ‘parallelism’ by running multiple operations on different processors. These can only be run once their dependencies have all been run already. How to assign the vertices to the processors is called a ‘scheduling problem’.

      • Week 4 - AS relationships and interdomain routing
        Last edited: 2026-02-05

        Interdomain routing

        # Additional reading

        # Important Readings

        Interdomain Internet Routing https://web.mit.edu/6.829/www/currentsemester/papers/AS-bgp-notes.pdfLinks to an external site.

        BGP routing policies in ISP networks https://www.cs.princeton.edu/~jrex/papers/policies.pdfLinks to an external site.

        On the importance of Internet eXchange Points for today’s Internet ecosystem https://cryptome.wikileaks.org/2013/07/ixp-importance.pdfLinks to an external site.

      • Week 4 - Buffer Management
        Last edited: 2026-06-01

        In the previous lectures we created the idea of the Slotted page. This allows us to group together Tuples into blocks. The pages then can be written onto the disk or into the memory directly. However, we need something to decide which pages to keep in memory and which ones to write to the disk. This is where the Buffer Manager comes in.

        There are two things that are important here:

      • Week 4 - Comparison-based Sorting
        Last edited: 2026-05-27

        Comparison-based sorting is done using a ‘comparator network’ which looks like a circuit with two types of symmetric connections.

        Comparison gate

        Positive gates look as below.

      • Week 4 - Convolution and Pooling Layers
        Last edited: 2026-06-16

        Convolution and pooling layers make up Convolutional Neural Networks (CNNs). These have been shown to have significant improvements for tasks such as image recognition but also wider use outside of it.

        # Convolution layers

        One of the main drivers for not using fully connected layers in image processing is the size of that input. They usually consist of 3 channels; red, green, and blue. With each of these layers being height x width large - which can get very large: $3 \cdot H \cdot W$. Therefore, we want to perform dimension reduction on it but preserving ‘features’ of the image.

      • Week 4 - Fast Fourier Transforms
        Last edited: 2026-06-18
        Polynomial multiplication problem

        Given polynomials

      • Week 4 - Parallel Systems
        Last edited: 2025-12-05

        # Week 4 - Parallel Systems

        In modern computing, nearly all processors are multi-core. This presents an interesting problem - how to share memory between them?

        # Shared Memory Architectures

        Here we detail 3 different approaches to shared memory architectures:

        # 1. Dance Hall Architecture

        In this architecture, CPUs and distributed memory sit on either side of an interconnection network. All memory is accessible to all CPUs.

      • Week 4 - Parsing context free grammars
        Last edited: 2026-01-28

        In this lecture, we will cover the parser - in particular the rules for parsing token input. This has two major responsibilities:

        • Syntax analysis: Checking the program is using the correct grammar for the programming language.

        • Breaking the input into expressions: Parsing the input into a sequence of expressions.

        # Derivation tree

        Derivation tree

        A derivation tree is a tree representation of the process of parsing a program. The root is the starting symbol and the internal nodes represent sub-symbols.

      • Week 4 - PThreads
        Last edited: 2026-02-05

        # Additional reading

        • “An Introduction to Programming with Threads”
        • PThreads Programming Resource

        # Background

        POSIX

        PThreads

        # Thread interface

        The core data structure in the PThreads library is pthread_t which represents a thread. This can be created through:

      • Week 4 - Support Vector Machines
        Last edited: 2024-01-29

        # Linearly separable

        We are going to revisit the idea of linearly separable points in the plane.

        Linearly separable

        Suppose we have training data $(x^t, y^t) \in \mathbb{R}^n \times \{1,-1\}$ for $t \in T$ such that $X_1 = \{x^t \vert y^t = 1\}$ and $X_2 = \{x^t \vert y^t = -1\}$ are linearly separable. This means that there exists some $w \in \mathbb{R}^n$ and $b \in \mathbb{R}$ such that

      • Week 5 - Beyond Multiprocessing ... Multithreading and the SunOS Kernel
        Last edited: 2026-02-05

        Ref: Beyond Multiprocessing … Multithreading the SunOS Kernel

        # Notes

        # Architecture

        In this paper they introduce the concept of a Light Weight Process (LWP) that sits as an intermediary between kernel level threads and user level threads. Each LWP is mapped to a kernel thread but not all kernel threads need to be mapped to a LWP.

      • Week 5 - Computational Learning Theory
        Last edited: 2025-12-05

        # Week 5 - Learning Theory

        Computational learning theory is fundamentally about 3 things:

        • defining learning problems,
        • showing algorithms work, and
        • showing problems are easy or hard.

        When considering problems it is useful to think about:

        1. The probability of successful training.
           1. The probability the process works $1 - \delta$
        2. Number of examples you need to train on.
           1. The size of the training set $m$.
        3. Complexity of the hypothesis class.
           1. How complex is the representation - modelling paradigm
        4. Accuracy to which the target concept is approximated.
           1. Within some $\epsilon$.
        5. Manner in which the examples are presented.
           1. Batch or online.
        6. Manner in which the training data is collected.
           1. Learner requests examples.
           2. Teacher gives examples.
           3. Fix distribution.
           4. Examples are picked poorly.

        # 20 Questions

        20 Questions is a game where there is a set of possible answers $A$ and a correct answer $c \in A$. There is a player (questioner) who wants to find $c \in A$ and a questionee who knows $c \in A$. The player then asks questions boolean questions to questionee who answers True or false about item $c \in A$.

      • Week 5 - Convolutional Neural Networks
        Last edited: 2026-06-16

        In this week, we will focus on how to calculate the backward pass for convolutional neural networks and then talk about how they are practically used.

        # Backward pass

        Remember that the definition of a CNN for a kernel $K$ of size $K_1 \times K_2$ going from input $i$ to output $O$ is:

        $$ O(x,y) = K \ast I(x,y) = \sum_{i=0}^{K_1 - 1} \sum_{j=0}^{K_2 - 1} I(x + i,y + j)K(i,j) $$

        Then let’s calculate

      • Week 5 - Distributed Systems
        Last edited: 2025-10-01

        The definition of what a distributed system is varies but in this course we use the following 3 properties:

        1. Nodes on the network are connected via some LAN or WAN.
        2. Nodes do not share memory.
        3. The computational event time is significantly smaller than the communication time.

        Definition 3 is used a fair bit and within this you can consider a cluster of machines even within the same rack in a data center - distributed computing.

      • Week 5 - Implementing Lightweight Threads (paper)
        Last edited: 2026-02-05

        Ref: Implementing Lightweight threads

        # Notes

        This paper describes an implementation of light weight threads in the SunOS architecture. This is laid out in Week 5 - Beyond Multiprocessing … Multithreading and the SunOS Kernel .

        • If one thread calls exit on the process then all threads will exit.
        • Threads have their own signal mask.
        • Signals to the process are sent to one of the threads which have that signal unmasked.
          • If all threads have it masked it is left pending on the process until a thread unmasks it.
        • Signals can be sent to a particular thread.
        • All threads within a process share signal handlers.

      • Week 5 - Infinite hypothesis spaces
        Last edited: 2024-02-16

        In Week 5 - Computational Learning Theory we developed a method to build a PAC learner on a finite dimensional hypothesis space. However this breaks down in infinite dimensions. We need to get around this.

        # Lets just cheat

        Whilst the hypothesis space might be infinite theoretically, the actual number of distinct hypothesises could be finite. Then we can fall back on the previous work.

      • Week 5 - Multi-threading
        Last edited: 2026-06-01

        Within database applications to speed up query performance we will use multi-threading. Though we need to pay attention to race-conditions and dead-locks between threads for this. To handle this we will use locks.

        The level of granularity of the locks will affect your program’s complexity and performance. For example, you could have database lock, table lock, or even down to the row level locks. Each come with a payoff for performance gains vs complexity and overhead costs.

      • Week 5 - Operating System Support for Database Management
        Last edited: 2026-06-18

        Paper: Operating System Support for Database Management — Michael Stonebraker, CACM July 1981.

        Stonebraker examines four core OS services — buffer management, the file system, scheduling and IPC, and consistency control — and makes the same finding in every single case: the OS gets it wrong, and DBMSs end up reimplementing the service themselves in user space. The paper’s conclusion is essentially that a DBMS would be better served by a minimal real-time OS than by a general-purpose one, and that OS designers have things backwards: DBMS-level storage abstractions should be the primitive, with character arrays built on top.

      • Week 5 - Recursive Descent Parsing
        Last edited: 2026-02-05

        In this lecture we are focusing on parsers. We can classify parsers into two types:

        • LR Bottom up parsers:
          • L: Scan left to right.
          • R: Traces rightmost derivation of the input string - starts from the end of the sentence.
          • This is bottom up as we start from the sentence and work our way back to the start symbol.
        • LL Top down parsers:
          • L: Scan left to right.
          • L: Traces leftmost derivation of the input string - starts from the beginning of the sentence.
          • This is top down as we start from the start symbol and work our way forward to the sentence.

        Within both types of parsers there is a dimension which reflects their efficiency. This is the maximum number of tokens it needs to ’look ahead’ to decide what rule to apply. This is referred to by $k$ and appended to the end of the type like $LL(k)$ for a top down parser that looks ahead $k$ tokens. Functionally we want to keep $k$ as low as possible to make compiling code as fast as possible.

      • Week 5 - Router design and algorithms
        Last edited: 2026-02-05

        Part 1

        # Additional reading

        # Important Readings

        Survey and Taxonomy of IP Address Lookup Algorithms https://pdfs.semanticscholar.org/71d9/018e900f99ff60653b3769160131e775873f.pdfLinks to an external site.

        # Book References

        Kurose-Ross, 6th Edition, Section 4.3

      • Week 5 - Scans and list ranking
        Last edited: 2026-05-27

        In this lecture we will look at how to parallelise algorithms that use linked lists. They are notoriously hard to parallelise as we just have a single linked list with the head pointer.

        # Scan

        Given a operation like sum, product, max a scan takes a sequence and returns a new one where that operation is performed on the entries up to that value.

      • Week 5 - Thread design considerations
        Last edited: 2026-02-05

        # Additional reading

        • Beyond Multiprocessing … Multithreading the SunOS Kernel
        • Implementing Lightweight threads

        # Thread level

        We will be revisiting the thread level from Thread level .

        

      • Week 5 - Top down parsing
        Last edited: 2026-02-05

        In the previous lecture we described a LL(1) parser that required humans to still write the functions for each expression. In this lecture we will produce an LL(1) parser that can be automatically generated from the grammar itself.

        # General overview

        This algorithm will have two stacks:

        • The input stack of tokens.

        • The working stack of symbols it is using to build up the expression.

        • Week 6 - 2-Satisfiability
          Last edited: 2025-12-05

          This week we will look at

          Statement

          Notation

          We use the following logical operators

        • Week 6 - Bayesian Inference
          Last edited: 2026-02-05

          # Joint distributions

          We can use the definition of conditional probability to help calculate joint probabilities.

          $$\mathbb{P}]A \cap B] = \mathbb{P}[A, B] = \mathbb{P}[A \vert B] \mathbb{P}[B].$$

          If probabilities are independent this simplifies to

          $$\mathbb{P}[A, B] = \mathbb{P}[A] \ \mathbb{P}[B].$$

          We say simplifies as to keep track of $\mathbb{P}[A, B]$ if $A$ has domain of size $n$ and $B$ of size $m$ we only need to keep track of $n + m - 2$ values whereas in the first case we need to keep track of $nm - 1$ values.

        • Week 6 - Bayesian learning
          Last edited: 2024-02-19

          # Bayes rule

          To start this lecture lets remind ourselves of the definition of conditional probability .

          Conditional probability

          As a simple corollary we get Bayes rule .

          Bayes rule

          Question

          Suppose there is a illness effects $0.8\%$ of the population $\mathbb{P}[I] = 0.008$. We have a test that has a true positive chance of $98\%$ (i.e. $\mathbb{P}[+ve | I] = 0.98$) and a true negative result of $97\%$ (i.e. $\mathbb{P}[-ve \vert \lnot I] = 0.97$). Given you have a positive test result are you more likely to have the illness or not?

        • Week 6 - Distributed objects and middleware
          Last edited: 2025-10-23

          # Week 6 - Distributed objects and middleware

          # Spring OS

          When innovating as a company in the OS space you have two options:

          1. Build a new OS from scratch.

          2. Build a better implementation of an existing OS.

          This decision is normally constrained by your customer base. At Sun Microsystems, they chose to keep the Unix interface but aimed for better ‘under the hood’ implementations. This is similar to CPUs, which are said to be ‘Intel inside’ but have different implementations. In this case it was ‘Unix inside’ but they changed the implementation.

        • Week 6 - Exam prep
          Last edited: 2024-06-15

          # Lesson 1: Introduction, History, and Internet Architecture

          • What are the advantages and disadvantages of a layered architecture?

          • What are the differences and similarities between the OSI model and the five-layered Internet model?

          • What are sockets?

          • Describe each layer of the OSI model.

          • Provide examples of popular protocols at each layer of the five-layered Internet model.

          • What is encapsulation, and how is it used in a layered model?

          • Week 6 - Graph algorithms - strongly connected components
            Last edited: 2026-06-18

            # DFS - not the sofa seller!

            Recall the definition of Depth-first search (DFS) in the note. We used it there to find the connected components of a graph.

            DFS to find connected components in an undirected graph

            # Find paths in undirected graph via DFS

            First for undirected graphs we just keep track of the previous vertex and find a spanning sub -forest for the graph . We can use this to find paths between vertices by going back to the root vertices of the trees .

          • Week 6 - Hash Tables
            Last edited: 2026-06-18

            Within our database we will need a way to index data within our tables. Here we go over the standard C++ implementations of a hash table then cover a manual implementation.

            # C++ Implementations

            There are two main implementations of a hash table in C++.

            # std::map

            Map stores items in a balanced binary search tree (red-black tree).

          • Week 6 - Minimum Spanning Tree
            Last edited: 2023-11-11

            Statement

            # Tree properties

            It is useful to remind ourselves of some tree properties:

            1. Tree on $n$ vertices has $n-1$ edges.
            2. In a tree, there is exactly one path between every pair of vertices.
            3. Any connected $G = (V,E)$ with $\vert E \vert = \vert V \vert - 1$ is a tree.

            These are all proved by the equivalent tree definitions .

          • Week 6 - Semantic Analysis
            Last edited: 2026-05-27

            Next we move on to the Semantic analysis stage of the compiler. This answers questions like:

            • Has a variable $x$ been declared?

            • Does $x$ have the correct type?

            • Are there variables that are declared but not used?

            • Do two variables reference the same memory location?

            The answers to these question are beyond the scope of what a CFG can check. These questions rely on information such as:

            • The value of a variable.

            • Week 6 - Thread Performance Considerations
              Last edited: 2026-02-05

              # Additional reading

              • Flash: an efficient portable web-server

              # Choosing a threading model

              

              When choosing a model for threading it is important to pick the metric you care about before deciding on implementation. In the example above the server would prefer the pipeline as it is cheaper in terms of CPU time whereas for clients they would prefer the boss-worker model as it reduces average order time completion.

            • Week 6 - Tree computations
              Last edited: 2026-05-27

              In this lecture, we will look at how to speed up algorithms run on trees through the use of parallel algorithms.

              # Root finder

              It is useful to express a tree as an array - which I for one find counter intuitive! (Mainly because lots of times to speed up array operations like binary search - it is useful to think of the array as a tree!). Suppose we have a tree $T$ if we label the vertices of the tree $0 \ldots n-1$ then we can define an array $A$ of length $n$ by $A[i]$ to be $i$’s parent with it being empty if there is no parent.

            • Week 6 - Visualisations
              Last edited: 2026-06-16

              When working with visual data you can visualise how the network is making decisions. This allows insight into why it makes decisions. There are different ways to do this:

              • Weights: For simple linear classifiers, you can plot the weights for different class outcomes and reshape them into an image. This gives you a mask you can visualise to see how it views the object. For convolutional neural networks you can do the same for the kernels to see what features they are picking out.

              • Week 7 - Advanced Computer Vision Architectures
                Last edited: 2026-06-16

                Up to now we have been doing image classification. However, there are lots of other tasks that we can do with images:

                • Semantic segmentation: Associate a class distribution per pixel.

                • Instance segmentation: Class distribution per pixel where we differentiate different objects, i.e. associate a unique ID.

                • Object detection: Create a list of bounding boxes for objects in the picture with a class distribution per box.

                # Segmentation

                In the previous lectures we studied CNNs. These normally involve multiple convolutional and pooling layers that reduce the image into a feature vector. This in turn was fed into fully connected layers to output class probabilities.

              • Week 7 - Distributed subsystems
                Last edited: 2025-10-26

                # Week 7 - Distributed subsystems

                In this lesson we look at 3 different distributed subsystems. Whilst the subsystems themselves might not be used, the ideas that go into creating them are good takeaway messages.

                # Global Memory System (GMS)

                The idea of the GMS was introduced in a paper called “Implementing Global Memory Management in a Workstation Cluster”. When referring to a paper throughout, we are talking about this paper. The key idea in GMS is to use the spare memory within a LAN network as another level of cache before going to disk. At the time of the paper being written (1995) sequential access to the disk took 3.6 ms whereas random access took 14.3 ms. In contrast, you could get a round trip to another machine in 2.1 ms, providing a significant speed-up.

              • Week 7 - Edmonds-Karp algorithm
                Last edited: 2023-11-11

                This algorithm is essentially the same as Ford-Fulkerson Algorithm but we use BFS instead of DFS to find the augmenting path in the residual network .

                Edmonds-Karp algorithm

              • Week 7 - Ford-Fulkerson Algorithm
                Last edited: 2023-11-11

                This lecture will focus on the Max flow problem . To define this we need some other definitions.

                Flow network

                Flow

                Statement

                # Assume we have no parallel edges

                If we are in the case where there are parallel edges, we can split one edge into two by putting a vertex in the middle of it.

              • Week 7 - Image Segmentation
                Last edited: 2026-02-05

                Given an image, we would like to separate it into its distinct components. Such as the subject and background.

                # Formulation

                Suppose we have picture $P$ which is a grid of different pixels. Define a undirected graph $G = (V, E)$ where $V$ is the set of pixels and $E$ is neighbouring pixels. Suppose in addition we are provided:

              • Week 7 - Information Theory
                Last edited: 2024-02-24

                # Information

                We want to measure the amount of information we need to transmit to send a message. However, the underlying facts about the message we will receive effect the length of that message.

                For example, if we have a fair coin and I need to tell you about 10 flips of this coin - I will need to transmit a message of 10 bits . There are $2^{10}$ potential outcomes which are evenly weighted so we can do no better than a message of size 10.

              • Week 7 - IR code generation
                Last edited: 2026-05-27

                Currently, we have checked the submitted code is valid and have an abstract syntax tree. Next we will generate an intermediate representation (IR) of the program. In fact, the AST is already a high level IR of the code.

                # Intermediate Representation (IR)

                An IR is a representation between the target and source languages. A good IR maximises the goal of achieving a retargatable compiler. One reason to use an IR is to perform machine independent optimizations.

              • Week 7 - Max-flow Generalizations
                Last edited: 2026-02-05
                Max flow

                with demands Let $(G=(V,E), c, s, t)$ be a flow network and assume we are provided with demands $d(e) \geq 0$ for $e \in E$. A flow $f$ is called feasible if

              • Week 7 - Max-Flow Min-Cut
                Last edited: 2023-11-11

                # Week 6 - Homework 4 (assessed)

                # Week 7 - Max-Flow Min-Cut

                This lecture we want to show correctness of Ford-Fulkerson Algorithm .

                To do this we will prove the following Theorem. Statement To do this lets first look at cuts of this graph in particular st-cuts . st-cut There is a related problem to Max flow problem called the Min st-cut problem . Statement

              • Week 7 - Randomized Optimization
                Last edited: 2024-02-24

                We are now moving onto to Unsupervised learning .

                Unsupervised learning

                The difference from supervised learning is we don’t get given labels - so how we actually learn the function is beyond me!

                # Optimisation problem

                Optimisation problem

                There are lots of examples of this.

              • Week 7 - Scheduling
                Last edited: 2026-02-05

                # Additional reading

                • Chip Multithreading Systems Need a New Operating System Scheduler

                # CPU scheduling

                In the following section we use the term ’task’ to refer to either a Process or a Thread from the point of view of the scheduler, these are the same.

              • Week 7 - Shared memory parallel BFS
                Last edited: 2026-05-27

                In this lecture we will look at speeding up Breadth-first search . In this lecture we will use BFS to find the distance of each vertex away from a root. The code for this algorithm might look like below:

                BFS(G = (V,E), root):
                  D : V -> Int
                  D[v] = 0 if v = root else infinity
                  F = { root }
                  while F is not empty:
                    v = F.pop()
                    for all edges (v,w) in E:
                      if D[w] = infinity:
                        D[w] = D[v] + 1
                        F = F union {w}
                  return D
                

                This has $W(G) = O(\vert V \vert + \vert E \vert)$ but is not very parallel with $D(G) = O(\vert V \vert)$. This algorithm is blocked from being parallelised by the set $F$ and function $D$ as it is edited on each pass through.

              • Week 7 - Software defined networks
                Last edited: 2026-02-05

                Software defined networks (SDN)

                # Additional reading

                # Important Readings

                The Road to SDN: An Intellectual History of Programmable Networks https://www.sigcomm.org/sites/default/files/ccr/papers/2014/April/0000000-0000012.pdfLinks to an external site.

                # Book References

                Kurose-Ross, 7th Edition. Section 4.1.1

              • Week 7 - Thread-safe hash tables
                Last edited: 2026-06-18

                In the previous lecture we discussed a hash table. However, in production we will have multiple threads consistently accessing this. Therefore we need it to be thread safe to enable concurrent reads and writes.

                # Single mutex

                The first most trivial way to enable concurrent access is to add a mutex to access the hash table at all. This means that all operations involving the hash table are serialized. However, functionally this will make the use of the hash table unbelievably slow.

              • Week 7 - Umbra: A Disk-Based System with In-Memory Performance
                Last edited: 2026-06-17

                Paper: Umbra: A Disk-Based System with In-Memory Performance — Neumann & Freitag, CIDR 2020.

                Umbra is an evolution of the pure in-memory database HyPer towards a system that uses SSDs as a backing store, achieving in-memory performance for the cached working set while scaling transparently beyond RAM.

                # Background: The Hardware Trend Problem

                Pure in-memory databases (like HyPer) store all data in RAM and never page to disk. This gives excellent performance but has two problems:

              • Week 8 - B+tree
                Last edited: 2026-06-19

                With a database there are two kinds of queries.

                • Point queries - ‘Get me person named Alex’

                • Range queries - ‘Get me all the children between 10 and 18 years old’

                Hash tables for indexes work great for point queries. The execute in $\Theta(1)$ time as we just look for the key Alex. However, they struggle at ‘range queries’. Here, there is nothing we can really do other than iterate through the keys. The solution to this is to use an ordered index - which in this course we implement as a B+ tree.

              • Week 8 - Bloom Filters
                Last edited: 2023-11-11

                # Week 7 - Homework 5 (unassessed)

                # Week 8 - Bloom Filters

                This week we will be focusing on hash functions . First we will look at a probability question.

                # Balls in bins problem

                If you randomly throw $n$ identical balls in $n$ identical bins $B_i$ for $1 \leq i \leq n$ where each throw is independent of on another. Define $load(i) =$ number of balls in bin $B_i$. How large is the max load = $\max_i load(i)$?

              • Week 8 - Control flow graphs
                Last edited: 2026-05-27

                A control flow graph dictates how the flow of the code works in an IR of the program. This is a graph whos nodes are ‘basic blocks’ and edges are potential changes of control.

                # Basic blocks

                Basic block

                A basic block is a sequence of consecutive IR statements in which flow of control can only enter at the beginning and leave at the end.

              • Week 8 - Distributed memory model
                Last edited: 2026-05-27

                In this lecture, we are going to look at computations that involve so much memory that they cannot fit on a single computer and instead need to use a distributed set of computers or would take years to compute alone. In the distributed setting each computer has its own memory and can only communicate with others via message passing.

                # Distributed memory model

                In our model we have a set of ‘machines’ which involve:

              • Week 8 - Internet Computing
                Last edited: 2026-01-28

                Normally web-based issues are called ’embarrassingly parallel'.

                Embarrassingly parallel

                These problems can be broken down into easy to do parallel operations, such as accessing email, doing a web search, or downloading files. No two clients rely on each other so all computation can be broken down on the per user level.

              • Week 8 - Memory management
                Last edited: 2026-02-05

                # Overview

                The operating system supports the abstraction of virtual memory for processes so it needs to:

                • Map virtual memory onto physical memory .
                • Manage what should be in physical memory .
                • Validate memory access of processes.

                When we speak about memory there are two main abstractions OS can use for memory:

              • Week 8 - Modular Arithmetic
                Last edited: 2026-02-05

                First lets remind ourselves of the definition of modular arithmetic .

                Modular arithmetic

                Within a computers architecture as numbers are stored in binary calculating mod $2^k$ is simple as taking the $k$ least significant bits. Therefore it is quite cheap. However, when the value is not $2^k$ it can get harder.

                # Exponent problem

                Statement

              • Week 8 - RSA
                Last edited: 2023-11-11

                To talk about the RSA algorithm we first need a little more theory.

                Fermat’s little theorem

                In fact we need a generalisation of Fermat’s little theorem called Euler’s theorem (modular arithmetic) .

                Euler’s theorem (modular arithmetic)

                Where we define Euler’s totient function as follows.

                Euler’s totient function

              • Week 8 - Security
                Last edited: 2026-02-05

                The Internet was not designed or built with security in mind. Security came as an afterthought after adversaries started misusing or abusing Internet services, resources and infrastructure.

                An attack on a system aims to compromise properties of a secure communication.

                # Additional reading

                # Important Readings

                Measuring and Detecting Fast-Flux Service Networks https://www.sec.tu-bs.de/pubs/2008-ndss.pdfLinks to an external site.

              • Week 8 - Structured Representations
                Last edited: 2026-06-29

                So far in the course we have covered fully connected layers and CNNs. The fully connected layer is ambiguous about the structure it represents - whereas with the CNN we put some architectural bias in how the data should behave. I.e. there should be similar small patterns that could appear anywhere in our data. However, sometimes we want to represent structured data like in an image we want to pull out the relationships in the image—e.g., ‘man riding horse’, ‘horse in front of mountain’. We will talk about 3 network architectures that can help us with this:

              • Week 9 - Advanced Indexing Data Structures
                Last edited: 2026-07-06

                In this lesson we will cover alternatives to hash-tables and B+ tree’s for indexing.

                # Trie

                For queries that need a pre-fix string matching we use a datastructure built for this. This is called a Trie.

                Trie?

                The word “trie” comes from Re’trie’val.

              • Week 9 - Algorithms for the exam
                Last edited: 2026-02-05

                algorithm	problem	runtime	Notes
                DFS to find path in a directed graph	Find path in a directed graph	$O(\vert V \vert + \vert E \vert)$	Not shortest
                DFS to find path in an undirected graph	Find path in undirected graph	$O(\vert V \vert + \vert E \vert)$	Not shortest
                DFS to find connected components in an undirected graph	Find connected components in a undirected graph	$O(\vert V \vert + \vert E \vert)$
                BFS	Find path in undirected graph /Find path in a directed graph	$O(\vert V \vert + \vert E \vert)$	Shortest unweighted
                Dijkstra’s algorithm	Find path in undirected graph /Find path in a directed graph	$O((\vert V \vert + \vert E \vert) \log(\vert V \vert))$	shortest weighted, positive weights only, from source
                Bellman-Ford algorithm	Find path in undirected graph /Find path in a directed graph	$O(\vert V \vert \vert E \vert)$	shortest weighted, from source, detects negative cycles
                Floyd-Warshall algorithm	Find path in undirected graph /Find path in a directed graph	$O(\vert V \vert^3)$	shortest weighted, all nodes, detects negative cycles
                DFS for finding strongly connected components	Find strongly connected components for an undirected graph	$O(\vert V \vert + \vert E \vert)$	Outputs them with topologically sort
                Kruskal’s algorithm	MST	$O(\vert E \vert \log(\vert V \vert))$
                Prim’s algorithm	MST	$O(\vert E \vert \log(\vert V \vert))$
                Ford-Fulkerson Algorithm	max flow	$O(C \vert E \vert)$ $C$ being the max flow	Integer weights
                Edmonds-Karp algorithm	max flow	$O(\vert V \vert \vert E \vert^2)$
                2-SAT algorithm using SCC	2-SAT	$O(\vert V \vert + \vert E \vert)$

              • Week 9 - Censorship
                Last edited: 2026-02-05

                # Additional reading

                # Important Readings

                Towards a Comprehensive Picture of the Great Firewall’s DNS Censorship https://www.usenix.org/system/files/conference/foci14/foci14-anonymous.pdfLinks to an external site.

                Ignoring the Great Firewall of China https://www.cl.cam.ac.uk/~rnc1/ignoring.pdfLinks to an external site.

                Global Measurement of DNS Manipulation https://www.cc.gatech.edu/~pearce/papers/dns_usenix_2017.pdfLinks to an external site.

              • Week 9 - Clustering
                Last edited: 2024-03-09

                # Unsupervised learning

                Unsupervised learning

                Clustering problem

                Two trivial solutions to clustering problems are:

                • Set $B = A$ the $f(a) = a$, for all $a \in A$ or
                • Set $B = \{1\}$ then $f(a) = 1$ for all $a \in A$.

                # Single Linkage Clustering

                Single linkage clustering

              • Week 9 - Inter-process communication
                Last edited: 2026-02-05

                Inter-process communication (IPC)

                # Message based IPC

                Message based IPC opens two ports (not necessarily in the networking sense) one in each process. Then the kernel is used to move the messages between the two ports. Examples of this are:

                • Pipes: A stream of bytes between the process - no structured messages. This is used when connecting stdin to stdout of a process when you pipe them in a terminal.
                • Message queues: A queue of structured messages that the processes can pop one at a time. In linux there are two APIs for this: SystemV and POSIX .
                • Network sockets: Uses the same interface as connecting to a network port. Normally the operating system optimizes this process by skipping some overhead of the network protocols. Message based IPC is simple to use as the kernel handles the synchronization but comes with overhead as the message has to be copied between processes and involves context switches to communicate with the kernel.

                # Shared Memory IPC

                This form of IPC maps a bit of memory into both processes. After it is mapped in neither processes need to go through the kernel to communicate. However that means both processes need synchronization to ensure they don’t over-write one another. They also need to establish a shared protocol on how to communicate.

              • Week 9 - Language models
                Last edited: 2026-06-30

                The general problem of language models is to predict the probability of a sentence of words. For example:

                $$ \mathbb{P}(\text{The dog barked at the cat}) $$

                We do this generally by breaking the sentence down into words and using conditional probability:

                $$ \mathbb{P}(w_1 w_2 \ldots w_n) = \prod_{i=1}^{n} \mathbb{P}(w_i \vert w_{i-1}, w_{i-2}, \ldots w_1 ) $$

                This has lots of applications, such as:

                1. Text completion: Given the current sentence what is the next most likely word.

                2. Week 9 - Liveness Analysis
                   Last edited: 2026-04-29

                   In this lecture, we move from the front end (whose task it was to check the code for user errors and generate the IR) to the middle-end and back-end. The middle-end optimises the IR in a machine-independent way, while the back-end converts it into machine code for the target architecture. The first part of this builds on the control flow graph in the previous lecture. We need to study ’liveness analysis’ the study of what variables are used where. This will enable us to optimise for register allocation.

                3. Week 9 - RT and Multimedia
                   Last edited: 2026-01-28

                   # Week 9 - RT and Multimedia

                   # Time sensitive Linux (TS-Linux)

                   Historically, OS systems have been optimised to handle ’throughput orientated’ tasks such as databases and scientific applications. Though in modern OSs we have to prioritise ’latency orientated’ tasks such as playing games and synchronous audio players. These tasks need guarantees that events can happen at a given time.

                4. Week 9 - Topology
                   Last edited: 2026-05-27

                   In the distributed machine model we said the algorithm running time depended on the underlying network. However, in that lecture we mainly used a linear network to develop algorithms. At the start of HPC the design of these networks were an important area of study - however as computers got faster it dropped in importance.

                   # Network properties

                   A network $N = (V, E)$ is a graph where each node can contain a processor (but does not have to in the case of routers). More complex networks may have a bandwidth associated to each edge $b: E \rightarrow \mathbb{R}$. There are multiple properties we care about: