This website houses notes from my studies at the University of Liverpool. If you see any errors or issues, please do open an issue on this site's GitHub.
A binary tree is a tree where the degree is at most two. The two sub-trees are called left sub-tree and the right sub-tree (may be empty). Traversing There are three common ways to traverse a binary tree: Pre-order traversal (VLR) Vertex, left sub-tree, right sub-tree. In-order traversal (LVR) Left...
Trees are linked lists with branches. Definition A tree $T=(V,E)$ consists of a set of vertices $V$ and a set of edges $E$ such that for any pair of vertices $u,v\in V$ there is exactly one path between $u$ and $v$: graph TD u((u)) --> y((y)) u --> v((v)) u...
Disk Hardware Disks are based around the concept of blocks: Disks are split into block of a certain size. Files fill up one or more blocks. Only one file can fill each block, so some wasted space if a file is smaller than the block. Operating system determines the block...
UML diagrams including abstract classes and interfaces can be drawn in the following way: classDiagram Degreeable <|.. Dog Emailable <|.. ResearchCouncil Billable <|.. ResearchCouncil Degreeable <|.. Student Billable <|.. Student Emailable <|.. Person Person <|-- Lecturer Payable <|.. Lecturer Person <|-- Student Lecturer <|-- Professor class Person{ <<Abstract>> -name String...
Random Variables & Measures A random variable is just a real valued function over a population: \[r:\Omega\rightarrow\Bbb R\] Using a probability distribution: \[P:\Omega\rightarrow [0,1]\] we can find the expected value $E[X]$ of a random variable. This is also sometimes called the average value or the mean value. This is calculated...
Interfaces allow you to abstract the workings of your code and provide simple interfaces to the user: Lamp Example public interface Switchable { public void switchOn(); public void switchOff(); } This defines the interface type that someone can call. Switchable l = new Lamp(); l.switchOn(); l.switchOff(); This is the use...
We can stop instantiations of certain superclasses by making them abstract: classDiagram class Shape <<abstract>> Shape Shape : +colour String Shape <|-- Circle class Circle{ +radius double +area() double } The name of this class should be in italics. If it is abstract. I have used an annotation here which...
Experimental proof makes justifications more clear and accessible. Methodology Suppose we have some algorithm which we suspect runs efficiently most of the time. We can test this using the following experimental method: Run the algorithm a number of times on different data. Determine the average time taken. This raises the...
Preemptive algorithm that gives a set CPU time to all active processes. Similar to FCFS, but allows for preemption by switching between processes. Ready queue is treated as circular. The CPU allocates each process a time-slice. Time Quantum - A small unit of time, varying anywhere between 10 and 100...