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.
Installation Refer to the installation notes for full install details. In summary, install the gradle package: $ yay -S gradle Setting up a Java Gradle Project This will be following the documentation for setting up a new java project. Create a new project directory: $ mkdir demo $ cd demo...
Dealing with Deadlock Prevention Build systems where deadlock couldn’t possibly occur. Avoidance Make decisions dynamically as to which resource requests can be granted. Detection and Recovery Allow deadlock to occur, then cure it. Ignore the Problem Deadlock Prevention There are several techniques to prevent deadlock: Force processes to claim all...
A set of processes is deadlocked if each process in the set is waiting for an event only another process in the set can case. These events usually relate to resource allocation. Creating Deadlock Deadlock will occur in the following simple situation: Process $A$ is granted resource $X$ and then...
Bipartite Graphs Graphs which are bipartite may have the nodes split into two sets with no two nodes in the same set being linked by an edge. They have a spectrum which is symmetric: \[(\lambda_1,\lambda_2,\lambda_3,\ldots,-\lambda_3,-\lambda_2,-\lambda_1)\]
Solving Recurrence for Fibonacci Numbers Suppose $n$ is even: \[\begin{aligned} T(n) &= \mathbf{T(n-1)} + T(n-2) + 1\\ &= \mathbf{(T(n-2)+T(n-3)+1)} + T(n-2) + 1\\ &> 2\times T(n-2)\\ &> 2\times (\mathbf{2\times T(n-4)}) = 2^2 \times T(n-4)\\ &> 2^2\times (2\times T(n-6)) = 2^3 \times T(n-6)\\ &> 2^3\times (2\times T(n-8)) = 2^4 \times T(n-2\times...
The formula for Fibonacci numbers is as follows: \[F(n)=\begin{cases} 1 & \text{if } n=0 \text{ or } 1\\ F(n-1) + F(n-2) & \text{if } n> 1 \end{cases}\] Pseudo Code This is a recursive implementation: Algorithm F(n) if n == 0 OR n == 1 then return 1 else return F(n-1)...
Code Philosopher Thread public void run() { while (alive) { think(); stick[i].get(); stick[(i + 1) % 5].get(); eat(); stick[i].put_down(); stick[(i + 1) % 5].put_down(); } } Chopstick Class class Chopstick { private volatile boolean in_use = false; public synchronized get() { while(in_use) { try { wait(); } catch { ...;...
Method Divide the sequence of $n$ numbers into two halves. Recursively sort the two halves. Merge the two sorted halves into a single sorted sequence. It is easier to merge two sequences that are already sorted, compared to two non-sorted sequences. How to Merge To merge two sorted sequences we...
The idea of divide and conquer is to divide a problem into several smaller instances of ideally the same size. The smaller instances are solved, typically recursively. The solutions for the smaller instances are combined to get a solution to the large instance. Sum Example Find the sum of all...
The producer-consumer problem models a synchronisation environment in which processes with distinct roles have to coordinate access to a shared facility. The dining philosophers problem models an environment in which all processes have identical roles. Again coordinated access to shared facilities must be arranged. Premise $n$ philosophers spend their time...