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.
Collections are containers to store objects: They are parameterised by a base type. They can be dynamically resized. They can store and access content in different ways. Example - List of Strings import java.util.*; List<String> customers; customers = new ArrayList<String>(); customers.add("Ms. X"); customers.add("Mr. Y"); customers.add("Mx. Z"); int count = customers.size();...
There are two main traversal algorithms: BFS and DFS. These have been covered in the following COMP111 lectures: COMP111 - Breadth First Search COMP111 - Depth First Search COMP111 - Properties of Searches BFS with a Queue/Linked List Example Suppose $a$ is the starting vertex: graph LR a((a)) --- b((b))...
Paths A number of nodes from one point to another. Circuits If the start and end of the path is the same then it is a circuit. Euler Circuits A circuit that visits every edge once. Vertexes can be repeated. Not all graphs have an Euler circuit. Conditions The graph...
Representation of Undirected Graphs An undirected graph ca be represented by an adjacency matrix, adjacency list, incidence matrix or incidence list. Adjacency Matrix/List The relationship between vertex adjacency (vertex vs vertex). Incidence Matrix/List The relationship between edge incidence (vertex vs edge). Adjacency Matrix/List Adjacency matrix $M$ for a simple undirected...
Undirected Graphs An undirected graph $G=(V,E)$ consists of a set of vertices $V$ and a set of edges $E$. Each edge is an unordered pair of vertices. Unordered means that $\{b,c\}$ and $\{c,b\}$ refer to the same edge. graph LR a((a)) --- b((b)) a --- e((e)) a --- c((c)) a...
I/O requests need to be scheduled to execute in an efficient order. A good ordering can improve system performance, ensure devices are shared fairly amongst processes and reduce average I/O completion wait time. Scheduling done via wait queues for each device: I/O scheduler may rearrange the order of the queue...
Devices Peripheral devices connect to ports on the computer. Data and commands to/from the devices may travel along a shared set of wires called a bus: flowchart TB CPU <--> Bus 1[Device] <--> Bus 2[Device] <--> Bus 3[Device] <--> Bus Devices ignore messages not intended for them. Problem of bus...
Contiguous Allocation Each file is allocated a contiguous set of blocks. graph TD subgraph Filestore eeny meeny miny mo end Location of information consists simply of: Start Block Number of blocks. Advantages Fast for both sequential and direct access. Problems Fragmentation May need regular compaction. Number of blocks to allocate....
This is the method that we use to draw trends from experimental data. This is better than a table as it makes the data clearer. Example How to we best fit a line to this graph: $x$ 1.5 2.4 3.6 4.2 4.8 5.7 6.3 7.9 $y$ 1.2 1.5 1.9 2.0...
Binary Search Tree For a vertex with value $X$: Left child has value $\leq X$. Right child has value $> X$. graph TD 60 --- 40 60 --- 90 40 --- 20 40 --- 50 20 --- 10 20 --- 30 90 --- 80 90 --- 110 80 --- 70...