Introduction
This book is a collection of all my notes from my degree (computer systems engineering).
It exists for a few purposes:
 To consolidate knowledge
 To aid revision
 To act as a reference during exams
Contributing
If you wish to contribute to this, either to make any additions or just to fix any mistakes I've made, feel free.
The sources are all available on my Github.
CS118
This section is mainly just a reference of some of the more detailed bits of the module. It assumes a pretty strong prior knowledge of object oriented programming so doesn't aim to be comprehensive, it just specifies some details to remember for the exam.
The version of Java on DCS systems at the time of writing is 11. This is also the version these notes refer to.
Useful Resources
 https://en.wikipedia.org/wiki/Singleprecision_floatingpoint_format
 The Oracle documentation for specifics on how Java implements stuff
IEEE 754
IEEE 754 is a standardised way of storing floating point numbers with three components
 A sign bit
 A biased exponent
 A normalised mantissa
Type  Sign  Exponent  Mantissa  Bias 

Single Precision (32 bit)  1 (bit 31)  8 (bit 30  23)  23 (bit 22 0)  127 
Double Precision (64 bit)  1 (bit 63)  11 (bit 62  52)  52 (51  0)  1023 
The examples below all refer to 32 bit numbers, but the principles apply to 64 bit.
 The exponent is an 8 bit unsigned number in biased form
 To get the true exponent, subtract 127 from the binary value
 The mantissa is a binary fraction, with the first bit representing $1/2$, second bit $1/4$, etc.
 The mantissa has an implicit $1.$, so 1 must always be added to the mantissa
Formula
$−1_{sign}×2_{E−127}×(1+i=1∑23 b_{23−i}2_{−i})$
Decimal to Float
The number is converted to a binary fractional format, then adjusted to fit into the form we need. Take 12.375 for example:
 Integer part $(12)_{10}=(1100)_{2}$
 Fraction part $(0.375)_{10}=(0.011)_{2}$
Combining the two parts yields $1100.011$. However, the standard requires that the mantissa have an implicit 1, so it must be shifted to the right until the number is normalised (ie has only 1 as an integer part). This yields $(1.100011)_{2}$. As this has been shifted, it is actually $(1.100011)_{2}×2_{3}$. The three $(10)$ is therefore the exponent, but this has to be normalised (+127) to yield 130 $(10000010)$. The number is positive (sign bit zero) so this yields:
Sign  Biased Exponent  Normalised Mantissa 

0  1000 0010  100011 
$01000001010001100000000000000000$
Float to Decimal
Starting with the value 0x41C80000 = 01000001110010000000000000000000:
Sign  Biased Exponent  Normalised Mantissa 

0  1000 0011  1001 
 The exponent is 131, biasing (127) gives 4
 The mantissa is 0.5625, adding 1 (normalising) gives 1.5625
 $2_{4}×1.5625$ gives 25
Special Values
 Zero
 When both exponent and mantissa are zero, the number is zero
 Can have both positive and negative zero
 Infinity
 Exponent is all 1s, mantissa is zero
 Can be either positive or negative
 Denormalised
 If the exponent is all zeros but the mantissa is nonzero, then the value is a denormalised number
 The mantissa does not have an assumed leading one
 NaN (Not a Number)
 Exponent is all 1s, mantissa is nonzero
 Represents error values
Exponent  Mantissa  Value 

0  0  $±0$ 
255  0  $±∞$ 
0  not 0  denormalised 
255  not 0  NaN 
OOP Principles
Constructors
All Java classes have a constructor, which is the method called upon object instantiation.
 An object can have multiple overloaded constructors
 A constructor can have any access modifier
 Constructors can call other constructors through the
this()
method.  If no constructor is specified, a default constructor is generated which takes no arguments and does nothing.
 The first call in any constructor is to the superclass constructor.
 This can be elided, and the default constructor is called
 If there is no default constructor, a constructor must be called explicitly
 Can call explicitly with
super()
 This can be elided, and the default constructor is called
Access Modifiers
Access modifiers apply to methods and member variables.
private
: only the members of the class can seepublic
: anyone can seeprotected
: only class and subclasses can see Default: packageprivate, only members of the same package can see
Inheritance
 To avoid the diamond/multiple inheritance problem, Java only allows for single inheritance
 This is done using the
extends
keyword in the class definition  Inherits all public and protected methods and members
 Can, however, implement multiple interfaces
Example:
public class Car extends Vehicle implements Drivable, Crashable{
// insert class body here
}
The Car
class extends the Vehicle
base class (can be abstract or concrete) and implements the behaviours defined by the interfaces Drivable
and Crashable
.
static
The static keyword defines a method, a field, or a block of code that belongs to the class instead of the object.
 Static fields share a mutable state accross all instances of the class
 Static methods are called from the class instead of from the object
 Static blocks are executed once, the first time the class is loaded into memory
Polymorphism
Polymorphism: of many forms. A broad term describing a few things in java.
Dynamic Polymorphism
An object is defined as polymorphic if it passes more than one instanceof
checks. An object can be referred to as the type of any one of it's superclasses. Say for example there is a Tiger
class, which subclasses Cat
, which subclasses Animal
, giving an inheritance chain of Animal
< Cat
< Tiger
, then the following is valid:
Animal a = new Tiger();
Cat c = new Tiger();
Tiger t = new Tiger();
When referencing an object through one of it's superclass types, you can only call objects that the reference type implements. For example, if there was two methods, Cat::meow
and Tiger::roar
, then:
c.meow() //valid
t.meow() //valid
a.meow() //not valid  animal has no method meow
t.roar() //valid
c.roar() // not valid  cat has no method roar
Even though all these variables are of the same runtime type, they are being called from a reference of another type.
When calling a method of an object, the actual method run is the one that is furthest down the inheritance chain. This is dynamic/runtime dispatch.
public class Animal{
public speak(){return "...";}
}
public class Dog extends Animal{
public speak(){return "woof";}
}
public class Cat extends Animal{
public speak(){return "meow";}
}
Animal a = new Animal();
Animal d = new Dog();
Animal c = new Cat();
a.speak() // "..."
d.speak() // "woof"
c.speak() // "meow"
Even though the reference was of type Animal
, the actual method called was the overridden subclass method.
Static Polymorphism (Method Overloading)
Note: different to overridding
 Multiple methods with the same name can be written, as long as they have different parameter lists
 The method that is called depends upon the number of and type of the arguments passed
Example:
public class Addition{
private int add(int x, int y){return x+y;}
private float add(float x, float y){return x+y;}
public static void main(String[] args){
add(1,2); //calls first method
add(3.14,2.72); //calls second method
add(15,1.5); //calls second method
}
}
Abstraction
Abstraction is the process of removing irrelevant details from the user, while exposing the relevant details. For example, you don't need to know how a function works, it's inner workings are abstracted away, leaving only the function's interface and details of what it does.
In the example below, the workings of the sine function are abstracted away, but we still know what it does and how to use it.
float sin(float x){
//dont care really
}
sin(90); // 1.0
Encapsulation
Encapsulation is wrapping the data and the code that acts on it into a single unit. The process is also known as data hiding, because the data is often hidden (declared private
) behind the methods that retrieve them (getters/setters).
Reference Variables
There is no such thing as an object variable in Java. Only primitives (int
,char
,float
...), and references. All objects are heapallocated (new
), and a reference to them stored. Methods are all pass by value: either the value of the primitive, or the value of the reference. Java is not pass by reference . Objects are never copied/cloned/duplicated implicitly.
If a reference type is required (ie Integer
), but a primitive is given ((int) 1
), then the primitive will be autoboxed into it's equivalent object type.
Abstract Classes and Interfaces
 Abstract classes are classes that contain one or more
abstract
methods. A class must be declared
abstract
 Abstract methods have no body, ie are unimplemented.
 The idea of them is to generalise behaviour, and leave it up to subclasses to implement
 Abstract classes cannot be instantiated directly, though can still have constructors for subclasses to call
 A class must be declared
 Interfaces are a special kind of class that contain only abstract methods (and fields declared
public static final
) Used to define behaviour
 Technically can contain methods, but they're default implementations
 This raises all sorts of issues so is best avoided
 Don't have to declare methods abstract, it's implicit
The diagram shows the inheritance hierarchy of the java collections framework, containing interfaces, abstract classes, and concrete classes.
Exceptions
Exceptions
Exceptions are events that occur within the normal flow of program execution that disrupt the normal flow of control.
Throwing Exceptions
Exceptions can occur when raised by other code we call, but an exception can also be raised manually using a throw
statement. Any object that inherits, either directly or indirectly, from the Throwable
class, can be raised as an exception.
//pop from a stack
public E pop(){
if(this.size == 0)
throw new EmptyStackException();
//pop the item
}
Exception Handling
 Exceptions can be caught using a
try
catch
block  If any code within the
try
block raises an exception, thecatch
block will be executedcatch
blocks must specify the type of exception to catch Can have multiple catch blocks for different exceptions
 Only 1 catch block will be executed
 A
finally
block can be included to add any code to execute after the trycatch, regardless of if an exception is raised or not.  The exception object can be queried through the variable
e
try{
//try to do something
} catch (ExceptionA e){
//if an exception of type ExceptionA is thrown, this is executed
} catch (ExceptionB e){
//if an exception of type ExceptionB is thrown, this is executed
} finally{
//this is always executed
}
Exception Heirachy
 The
Throwable
class is the parent class of all errors and exceptions in Java  There are two subclasses of
Throwable
Error
, which defines hard errors within the JVM that aren't really recoverableException
, which defines errors that may occur within the code There are two kinds of exception, checked and unchecked
Checked and Unchecked Exceptions
 Checked exceptions must be either caught or rethrown
IOException
is a good example
 When a method that may throw a checked exception is required, there are two options
 Wrap the possibly exceptionraising code in a
try
catch
 Use the
throws
keyword in the method definition to indicate that the method may throw a checked exception
 Wrap the possibly exceptionraising code in a
public static void ReadFile() throws FileNotFoundException{
File f = new File("nonexistantfile.txt")
FileInputStream stream = new FileInputStream(f);
}
// OR
public static void ReadFile(){
File f = new File("nonexistantfile.txt")
try{
FileInputStream stream = new FileInputStream(f);
} catch (FileNotFoundException){
e.printStackTrace();
return;
}
}
 Unchecked Exceptions all subclass
RunTimeException
 ie
NullPointerException
andArrayIndexOutOfBoundsException
 ie
 Can be thrown at any point and will cause program to exit if not caught
Custom Exceptions
 Custom exception classes can be created
 Should subclass
Throwable
 Ideally the most specific subclass possible
 Subclassing
Exception
gives a new checked exception  Subclassing
RunTimeException
gives a new unchecked exception
 All methods such as
printStackTrace
andgetMessage
inherited from superclass  Should provide at least one constructor that overrides a superclass constructor
public class IncorrectFileExtensionException
extends RuntimeException {
public IncorrectFileExtensionException(String errorMessage, Throwable err) {
super(errorMessage, err);
}
}
Generics
Generics allow for classes to be parametrised over some type or types, to provide additional compile time static type checking. A simple box class parametrised over some type E
, for example:
public class Box<E>{
E item;
public Box(E item){
this.item = item;
}
public E get(){
return item;
}
public E set(E item){
this.item = item;
}
}
Generic Methods
Methods can be generic too, introducing their own type parameters. The parameters introduced in methods are local to that method, not the whole class. As an example, the static method below compares two Pair<K,V>
classes to see if they are equal.
public static <K, V> boolean compare(Pair<K, V> p1, Pair<K, V> p2) {
return p1.getKey().equals(p2.getKey()) &&
p1.getValue().equals(p2.getValue());
}
Type erasure
Type information in generic classes and methods is erased at runtime, with the compiler replacing all instances of the type variable with Object
. Object
is also what appears in the compiled bytecode. This means that at runtime, any type casting of generic types is unchecked, and can cause runtime exceptions.
CS126
The book Data Structures and Algorithms in Java by Goodrich, Tamassia and Goldwasser is a good resource as it aligns closely with the material. It can be found online fairly easily.
Arrays & Linked Lists
Arrays
Arrays are the most common data structure and are very versatile
 A sequenced collection of variables of the same type (homogenous)
 Each cell in the array has an index $0...(n−1)$
 Arrays are of fixed length and so have a max capacity
 Can store primitives, or references to objects
 When inserting an element into the array, all to the right must be shifted up by one
 The same applies in reverse for removal to prevent null/0 gaps being left
Sorting Arrays
 The sorting problem:
 Consider an array of unordered elements
 We want to put them in a defined order
 For example
[3, 6, 2, 7, 8, 10, 22, 9]
needs to become[2, 3, 6, 7, 8, 9, 10, 22]
 One possible solution: insertion sort:
 Go over the entire array, inserting each element at it's proper location by shifting elements along
public static void insertionSort(int[] data){
int n = data.length;
for(int k = 1; k < n; k++){ //start with second element
int cur = data[k]; //insert data[k]
int j = k; //get correct index j for cur
while(j < 0 && data[j1] > cur){ //data[j1] must go after cur
data[j] = data[j1]; // slide data[j1] to the right
j; //consider previous j for cur
}
data[j] = cur; //cur is in the right place
}
}
 Insertion sort sucks
 Has worst case quadratic complexity, as k comparisons are required for k iterations.
 When the list is in reverse order (worst case), $2n(n−1) $ comparisons are made
 Can do much better with alternative algorithms
Singly Linked Lists
 Linked lists is a concrete data structure consisting of a chain of nodes which point to each other
 Each node stores the element, and the location of the next node
 The data structure stores the head element and traverses the list by following the chain
 Operations on the head of the list (ie, prepending) are efficient, as the head node can be accessed via its pointer
 Operations on the tail require first traversing the entire list, so are slow
 Useful when data needs to always be accessed sequentially
 Generally, linked lists suck for literally every other reason
Doubly Linked Lists
 In a doubly linked list, each node stores a pointer to the node in front of and behind it
 This allows the list to be traversed in both directions, and for nodes to be easily inserted midsequence
 Sometimes, special header and trailer "sentinel" nodes are added to maintain a reference to the head an tail of the list
 Also removes edge cases when inserting/deleting nodes as there is always nodes before/after head and tail
Analysis of Algorithms
This topic is key to literally every other one, and also seems to make up 90% of the exam questions (despite there being only 1 lecture on it) so it's very important.
 Need some way to characterise how good a data structure or algorithm is
 Most algorithms take input and generate output
 The run time of an algorithm typically grows with input size
 Average case is often difficult to determine
 Focus on the worst case
 Runtime analysis and benchmarks can be used to determine the performance of an algorithm, but this is often not possible
 Results will also vary from machine to machine
 Theoretical analysis is preferred as it gives a more highlevel analysis
 Characterises runtime as a function of input size $n$
Pseudocode
 Pseudocode is a high level description of an algorithm
 Primitive perations are assumed to take unit time
 For example
 Evaluating an expression
 Assigning to a variable
 Indexing into an array
 Calling a method
Looking at an algorithm, can count the number of operations in each step to analyse its runtime
public static double arrayMax(double[] data){
int n = data.length; //2 ops
double max = data[0]; //2 ops
for (int j=1; j < n;j++) //2n ops
if(data[j] > max) //2n2 ops
max = data[j]; //0 to 2n2 ops
return max; //1 op
}
 In the best case, there are $4n+3$ primitive operations
 In the worst case, $6n+1$
 The runtime $T(n)$ is therefore $a(4n+3)≤T(n)≤a(6n+1)$
 $a$ is the time to execute a primitive operation
Functions
There are 7 important functions $f(n)$that appear often when analysing algorithms
 Constant  $1$
 $f(n)=c$
 A fixed constant
 Could be any number but 1 is the most fundamental constant
 Sometimes denoted $f(n)=c×g(n)$ where $g(n)=1$
 Logarithmic  $gn$
 For some constant $b>1$, $f(n)=g_{b}(n)$
 Logarithm is the inverse of the power function
 $x=g_{b}n⇔b_{x}=n$
 Usually, $b=2$ because we are computer scientists and everything is base 2
 Linear  $n$
 $f(n)=cn$
 $c$ is a fixed constant
 $f(n)=cn$
 nlogn  $ngn$
 $f(n)=n×gn$
 Commonly appears with sorting algorithms
 Quadratic  $n_{2}$
 $f(n)=n_{2}$
 Commonly appears where there are nested loops
 Cubic  $n_{3}$
 $f(n)=n_{3}$
 Less common, also appears where there are 3 nested loops
 Can be generalised to other polynomial functions
 Exponential  $2_{n}$
 $f(n)=b_{n}$
 $b$ is some arbitrary base, $n$ is the exponent
 $f(n)=b_{n}$
The growth rate of these functions is not affected by changing the hardware/software environment. Growth rate is also not affected by lowerorder terms.
 Insertion sort takes time $21 n_{2}$
 Characterised as taking $n_{2}$ time
 Merge sort takes $2ngn$
 Characterised as $ngn$
 The
arrayMax
example from earlier took $a(4n+3)≤T(n)≤a(6n+1)$ time Characterised as $n$
 A polynomial $f(n)$ of degree $d$, is of order $n_{d}$
BigO Notation
 BigO notation is used to formalise the growth rate of functions, and hence describe the runtime of algorithms.
 Gives an upper bound on the growth rate of a function as $n→∞$
 The statement "$f(n)$ is $O(g(n))$" means that the growth rate of $f(n)$ is no more than the growth rate of $g(n)$
 If $f(n)$ is a polynomial of degree $d$, then $f(n)$ is $O(n_{d})$
 Drop lower order terms
 Drop constant factors
 Always use the smallest possible class of functions
 $2n$ is $O(n)$, not $O(n_{2})$
 Always use the simplest expression
 $3n+5$ is $O(n)$, not $O(3n)$
Formally, given functions $f(n)$ and $g(n)$, we say that $f(n)$ is $O(g(n))$ if there is a positive constant $c$ and a positive integer constant $n_{0}$, such that
$f(n)≤cg(n)forn≥n_{0}$
where $c>0$, and $n_{0}≥1$
Examples
$2n+10$ is $O(n)$:
$f(n)=2n+10,g(n)=n$ $2n+10≤cn$ $(c−2)n≥10$ $n≥c−210 $ $c=3,n_{0}=10$
The function $n_{2}$ is not $O(n)$ $f(n)=n_{2},g(n)=n$ $n_{2}≤cn$ $n≤c$ The inequality does not hold, since $c$ must be constant.
BigO of $7n−2$: $f(n)=7n−10,g(n)=n$ $7n−2≤cn$ $(c−7)n≥2$ $n≥c−72 $ $c=7,c_{0}=1$
BigO of $3n_{3}+20n_{2}+5$: $f(n)=3n_{3}+20n_{2}+5,g(n)=n_{3}$ $3n_{3}+20n_{2}+5≤cn_{3}forn≥n_{0}$ $c=4,n_{0}=21$
$3gn+5$ is $O(gn)$ $f(n)=3gn+5,g(n)=gn$ $3gn+5≤cgnforn≥n_{0}$ $gn≥c−35 $ $c=8,n_{0}=2$
Asymptotic Analysis
 The asymptotic analysis of an algorithm determines the running time bigO notation
 To perform asymptotic analysis:
 Find the worstcase number of primitive operations in the function
 Express the function with bigO notation
 Since constant factors and lowerorder terms are dropped, can disregard them when counting primitive operations
Example
The $i$th prefix average of an array $X$ is the average of the first $i+1$ elements of $X$. Two algorithms shown below are used to calculate the prefix average of an array.
Quadratic time
//returns an array where a[i] is the average of x[0]...x[i]
public static double[] prefixAverage(double[] x){
int n = x.length;
double[] a = new double[n];
for(int j = 0; j < n; j++){
double total = 0;
for(int i = 0; i <= j; i++)
total += x[i];
a[j] = total / (j+1);
}
return a;
}
The runtime of this function is $O(1+2+...+n)+O(n)$. The sum of the first $n$ integers is $2n_{2}+n $, so this algorithm runs in quadratic $O(n_{2})$ time. This can easily be seen by the nested loops in the function too.
Linear time
//returns an array where a[i] is the average of x[0]...x[i]
public static double[] prefixAverage(double[] x){
int n = x.length;
double[] a = new double[n];
double total = 0;
for(int i = 0; i <= n; i++){
total += x[i];
a[i] = total / (i+1);
}
return a;
}
This algorithm uses a running average to compute the same array in linear time, by calculating a running sum.
BigOmega and BigTheta
BigOmega is used to describe the best case runtime for an algorithm. Formally, $f(n)$ is $Ω(g(n))$ if there is a constant $c>0$ and an integer constant $n_{0}geq1$ such that $f(n)≥c⋅g(n)forn≥n_{0}$
BigTheta describes the average case of the runtime. $f(n)$ is $Θ(g(n))$ if there are constants $c_{′}>0$ and $c_{′′}>0$, and an integer constant $n_{0}≥1$ such that $c_{′}g(n)≤f(n)≤c_{′′}g(n)forn≥n_{0}$
The three notations compare as follows:
 BigO
 $f(n)$ is $O(g(n))$ if $f(n)$ is asymptotically less than or equal to $g(n)$
 Big$Ω$
 $f(n)$ is $Ω(g(n))$ if $f(n)$ is asymptotically greater than or equal to $g(n)$
 Big$Θ$
 $f(n)$ is $O(g(n))$ if $f(n)$ is asymptotically equal to $g(n)$
Recursive Algorithms
Recursion allows a problem to be broken down into subproblems, defining a problem in terms of itself. Recursive methods work by calling themselves. As an example, take the factorial function:
$n!={1n×(n−1)! ifn=0otherwise $
In java, this can be written:
public static int factorial(int n){
if(n == 0) return 1;
return n * factorial(n1);
}
Recursive algorithms have:
 A base case
 This is the case where the method doesn't call itself, and the stack begins to unwind
 Every possible chain of recursive calls must reach a base case
 If not the method will recurse infinitely and cause an error
 A recursive case
 Calls the current method again
 Should always eventually end up on a base case
Binary Search
Binary search is a recursively defined searching algorithm, which works by splitting an array in half at each step. Note that for binary search, the array must already be ordered.
Three cases:
 If the target equals
data[midpoint]
then the target has been found This is the base case
 If the target is less than
data[midpoint]
then we binary search everything to the left of the midpoint  If the target is greater than
data[midpoint]
then we binary search everything to the right of the midpoint
public static boolean binarySearch(int[] data, int target, int left, int right){
if (left > right)
return false;
int mid = (left + right) / 2;
if(target == data[mid])
return true;
else if (target < data[mid])
return binarySearch(data,target,low,mid1);
else
return binarySearch(data,target,mid+1,high);
}
Binary search has $O(gn)$, as the size of the data being processed halves at each recursive call. After the $i_{th}$ call, the size of the data is at most $n/2_{i}$.
Linear Recursion
 The method only makes one recursive call
 There may be multiple possible recursive calls, but only one should ever be made (ie binary search)
 For example, a method used in computing powers by repeated squaring:
$pow(x,n)=⎩⎨⎧ 1x(pow(x,2n−1 ))_{2}(pow(x,2n ))_{2} ifn=0nis oddnis even $
public static int pow(int x, int n){
if (n == 0) return 1;
if (n % 2 == 0){
y = pow(x,n/2);
return x * y * y;
}
y = pow(x,(n1)/2);
return y * y;
}
Note how despite multiple cases, pow
only ever calls itself once.
Binary Recursion
Binary recursive methods call themselves twice recursively. Fibonacci numbers are defined using binary recursion:
 $F_{0}$ = 0
 $F_{1}=1$
 $F_{i}=F_{i−1}+F_{i−2}$
public static int fib(int n){
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n1) + fib(n2);
}
This method calls itself twice, which isn't very efficient. It can end up having to compute the same result many many times. A better alternative is shown below, which uses linear recursion, and is therefore much much more efficient.
public static Pair<Integer,Integer> linearFib(int n){
if(k = 1) return new Pair(n,0);
Pair result = linearFib(n1);
return new Pair(result.snd+1, result.fst);
}
Multiple Recursion
Multiple recursive algorithms call themselves recursively more than twice. These are generally very inefficient and should be avoided.
Stacks & Queues
Abstract Data Types (ADTs)
 An ADT is an abstraction of a data structure
 Specifies the operations performed on the data
 Focus is on what the operation does, not how it does it
 Expressed in java with an interface
Stacks
 A stack is a last in, first out data structure (LIFO)
 Items can be pushed to or popped from the top
 Example uses include:
 Undo sequence in a text editor
 Chain of method calls in the JVM (method stack)
 As auxillary storage in multiple algorithms
The Stack ADT
The main operations are push()
and pop()
, but others are included for usefulness
public interface Stack<E>{
int size();
boolean isEmpty();
E peek(); //returns the top element without popping it
void push(E elem); //adds elem to the top of the stack
E pop(); //removes the top stack item and returns it
}
Example Implementation
The implementation below uses an array to implement the interface above. Only the important methods are included, the rest are omitted for brevity.
public class ArrayStack<E> implements Stack<E>{
private E[] elems;
private int top = 1;
public ArrayStack(int capacity){
elems = (E[]) new Object[capacity];
}
public E pop(){
if (isEmpty()) return null;
E t = elems[top];
top = top1;
return t;
}
public E push(){
if (top == elems.length1) throw new FullStackException; //cant push to full stack
top++;
return elems[top];
}
}
 Advantages
 Performant, uses an array so directly indexes each element
 $O(n)$ space and each operation runs in $O(1)$ time
 Disadvantages
 Limited by array max size
 Trying to push to full stack throws an exception
Queues
 Queues are a first in, first out (FIFO) data structure
 Insertions are to the rear and removals are from the front
 In contrast to stacks which are LIFO
 Example uses:
 Waiting list
 Control access to shared resources (printer queue)
 Round Robin Scheduling
 A CPU has limited resources for running processes simultaneously
 Allows for sharing of resources
 Programs wait in the queue to take turns to execute
 When done, move to the back of the queue again
The Queue ADT
public interface Queue<E>{
int size();
boolean isEmpty();
E peek();
void enqueue(E elem); //add to rear of queue
E dequeue(); // pop from front of queue
}
Lists
The list ADT provides general support for adding and removing elements at arbitrary positions
The List ADT
public interface List<E>{
int size();
boolean isEmpty();
E get(int i); //get the item from the index i
E set(int i, E e); //set the index i to the element e, returning what used to be at that index
E add(int i, E e); //insert an element in the list at index i
void remove(int i); //remove the element from index i
}
Array Based Implementation (ArrayList
)
Array lists are growable implementations of the List ADT that use arrays as the backing data structure. The idea is that as more elements are added, the array resizes itself to be bigger, as needed. Using an array makes implementing get()
and set()
easy, as they can both just be thin wrappers around array[]
syntax.
 When inserting, room must be made for new elements by shifting other elements forward
 Worst case (inserting to the head) $O(n)$ runtime
 When removing, need to shift elements backward to fill the hole
 Same worst case as insertion, $O(n)$
When the array is full, we need to replace it with a larger one and copy over all the elements. When growing the array list, there are two possible strategies:
 Incremental
 Increase the size by a constant $c$
 Doubling
 Double the size each time
These two can be compared by analysing the amortised runtime of the push operation, ie the average time required $T(n)/n$ for a $n$ pushes taking a total time $T(n)$.
With incremental growth, over $n$ push operations, the array is replaced $k=n/c$ times, where $c$ is the constant amount the array size is increased by. The total time $T(n)$ of $n$ push operations is proportional to: $c+2c+3c+...+kc=c(1+2+..+k)=2ck(k+1) $
Since $c$ is a constant, $T(n)$ is $Ω(k_{2})$, meaning the amortised time of a push operation is $Ω(n)$.
With doubling growth, the array is replaced $k=g_{2}n$ times. The total time $T(n)$ of $n$ pushes is proportional to:
$1+2+4+8+...+2_{k}=2_{k+1}−1=2n−1$
Thus, $T(n)$ is $O(n)$, meaning the amortised time $T(n)/n$ is $O(1)$
Positional Lists
 Positional lists are a general abstraction of a sequence of elements without indices
 A position acts as a token or marker within the broader positional list
 A position
p
is unaffected by changes elsewhere in a list It only becomes invalid if explicitly deleted
 A position instance is an object (ie there is some
Position
class) ie
p.getElement()
returns the element stored at positionp
 ie
 A very natural way to implement a positional list is with a doubly linked list, where each node represents a position.
 Where a pointer to a node exists, access to the previous and next node is fast ($O(1)$)
ADT
public interface PositionalList<E>{
int size();
boolean isEmpty();
Position<E> first(); //return postition of first element
Position<E> last(); //return position of last element
Position<E> before(Position<E> p); //return position of element before position p
Position<E> after(Posittion<E> p); //return position of element after position p
void addFirst(E e); //add a new element to the front of the list
void addLast(E e); // add a new element to the back of the list
void addBefore(Position<E> p, E e); // add a new element just before position p
void addAfter(Position<E> p, E e); // add a new element just after position p
void set(Position<E> p, E e); // replaces the element at position p with element e
E remove(p); //removes and returns the element at position p, invalidating the position
}
Iterators
Iterators are a software design pattern that abstract the process of scanning through a sequence one element at a time. A collection is Iterable
if it has an iterator()
method, which returns an instance of a class which implements the Iterator
interface. Each call to iterator()
returns a new object. The iterable interface is shown below.
public interface Iterator<E>{
boolean hasNext(); //returns true if there is at least one additional element in the sequence
E next(); //returns the next element in the sequence, advances the iterator by 1 position.
}
// example usage
public static void iteratorOver(Iterable<E> collection){
Iterator<E> iter = collection.iterator();
while(iter.hasNext()){
E var = iter.next();
System.out.println(var);
}
}
Maps
 Maps are a searchable collection of keyvalue entries
 Lookup the value using the key
 Keys are unique
The Map ADT
public interface Map<K,V>{
int size();
boolean isEmpty();
V get(K key); //return the value associated with key in the map, or null if it doesn't exist
void put(K key, V value); //associate the value with the key in the map
void remove(K key); //remove the key and it's value from the map
Collection<E> entrySet(); //return an iterable collection of the values in the map
Collection<E> keySet(); //return an iterable collection of the keys in the map
Iterator<E> values(); //return an iterator over the map's values
}
ListBased Map
A basic map can be implemented using an unsorted list.
get(k)
 Does a simple linear search of the list looking for the key,value pair
 Returns null if search reaches end of list and is unsuccessful
put(k,v)
 Does linear search of the list to see if key already exists
 If so, replace value
 If not, just add new entry to end
 Does linear search of the list to see if key already exists
remove(k)
 Does a linear search of the list to find the entry and removes it
 All operations take $O(n)$ time so this is not very efficient
Hash Tables
 Recall the map ADT
 Intuitively, a map
M
supports the abstraction of using keys as indices such asM[k]
 A map with n keys that are known to be integers in a fixed range is just an array
 A hash function can map general keys (ie not integers) to corresponding indices in a table/array
Hash Functions
A hash function $h$ maps keys of a given type to integers in a fixed interval $[0,N−1]$.

A very simple hash function is the mod function: $h(x)=xmodN$
 Works for integer keys
 The integer $h(x)$ is the hash value of the key $x$

The goal of a hash function is to store an entry $(k,v)$ at index $i=h(k)$

Function usually has two components:
 Hash code $h_{1}$
 keys > integers
 Compression function $h_{2}$
 integers > integers in range $[0,N−1]$
 Hash code applied first, then compression  $h(x)=h_{2}(h_{1}(x))$ Some example hash functions:
 Hash code $h_{1}$

Memory address
 Use the memory address of the object as it's hash code

Integer cast
 Interpret the bits of the key as an integer
 Only suitable with $≤$ 64 bits

Component sum
 Partition they key into bitwise components of fixed length and sum the components

Polynomial accumulation
 Partition the bits of the key into a sequence of components of fixed length $a_{0}$, $a_{1}$, ... , $a_{n−1}$
 Evaluate the polynomial $P(z)=a_{0}+a_{1}z+a_{2}z_{2}+...+a_{n−1}z_{n−1}$ for some fixed value $z$
 Especially suitable for strings
 Polynomial can be evaluated in $O(n)$ time as $p_{i}(z)=a_{n−i−1}+zp_{i−1}(z)$
Some example compression functions:
 Division
 $h_{2}(y)=ymodN$
 The size $N$ is usually chosen to be a prime to increase performance
 Multiply, Add, and Divide (MAD)
 $h_{2}(y)=(ay+b)modN$
 $a$ and $b$ are nonnegative integers such that $amodN=0$
Collision Handling
Collisions occur when different keys hash to the same cell. There are several strategies for resolving collisions.
Separate Chaining
With separate chaining, each cell in the map points to another map containing all the entries for that cell.
Linear Probing
 Open addressing
 The colliding item is placed in a different cell of the table
 Linear probing handles collisions by placing the colliding item at the next available table cell
 Each table cell inspected is referred to as a "probe"
 Colliding items can lump together, causing future collisions to cause a longer sequence of probes
Consider a hash table $A$ that uses linear probing.
get(k)
 Start at cell $h(k)$
 Prove consecutive locations until either
 Key is found
 Empty cell is found
 All cells have been unsuccessfully probed
 To handle insertions and deletions, need to introduce a special marker object
defunct
which replaces deleted elements remove(k)
 Search for an entry with key
k
 If an entry
(k, v)
is found, replace it withdefunct
and returnv
 Else, return
null
 Search for an entry with key
Double Hashing
 Double hashing uses two hash functions
h()
andf()
 If cell
h(k)
already occupied, tries sequentially the cell $(h(k)+i⋅f(k))modN$ for $i=1,2,3...$ f(k)
cannot return zero Table size $N$ must be a prime to allow probing of all cells
 Common choice of second hash func is $f(k)=q−kmodq$ where q is a prime
 if $f(k)=1$ then we have linear probing
Performance
 In the worst case, operations on hash tables take $O(n)$ time when the table is full and all keys collide into a single cell
 The load factor $α=n/N$ affects the performance of a hash table
 $n$ = number of entries
 $N$ = number of cells
 When $α$ is large, collision is likely
 Assuming hash values are true random numbers, the "expected number" of probes for an insertion with open addressing is $1−α1 $
 However, in practice, hashing is very fast and operations have $O(1)$ performance, provided $α$ is not close to 1
Sets
A set is an unordered collection of unique elements, typically with support for efficient membership tests
 Like keys of a map, but with no associated value
Set ADT
Sets also provide for traditional mathematical set operations: Union, Intersection, and Subtraction/Difference.
public interface Set<E>{
void add(E e); //add element e to set if not already present
void remove(E e); //remove element e from set if present
boolean contains(E e); //test if element e is in set
Iterator<E> iterator(); //returns an iterator over the elements
//updates the set to include all elements of set T
// union
void addAll(Set<E> T);
//updates the set to include only the elements of the set that are also in T
//intersection
void retainAll(Set<E> T);
//updates the set to remove any elements that are also in T
//difference
void removeAll(Set<E> T);
}
Generic Merging
Generic merge is a generalised merge of two sorted lists A
and B
to implement set operations. Uses a template method merge
and 3 auxillary methods that describe what happens in each case:
aIsLess
 Called when the element of
A
is less than the element ofB
 Called when the element of
bIsLess
 Called when the element of
B
is less than the element ofA
 Called when the element of
bothEqual
 Called when the element of
A
is equal to the element ofB
 Called when the element of
public static Set<E> merge(Set<E> A, Set<E> B){
Set<E> S = new Set<>();
while (!A.isEmpty() && !B.isEmpty()){
a = A.firstElement();
b = B.firstElement();
if(a < b){
aIsLess(a,S);
A.remove(a);
}
else if (b < a){
bIsLess(b,S);
B.remove(b);
}
else{ //b == a
bothEqual(a,b,S);
A.remove(a);
B.remove(b);
}
while(!A.isEmpty()){
aIsLess(a,S);
A.remove(a);
}
while(!B.isEmpty()){
bIsLess(b,S);
B.remove(b);
}
}
return S;
}
 Any set operation can be implemented using generic merge
 Union
aIsLess
adds a into SbIsLess
adds b into SbothEqual
adds a (or b) into S
 Intersection
aIsLess
andbIsLess
do nothingbothEqual
adds a (or b) into S
 Difference
aIsLess
adds a into SbIsLess
andbothEqual
do nothing
 Runs in linear time, $O(N_{A}+N_{B})$, provided the auxillary methods are $O(1)$
Trees
 A tree is an abstract model of a heirarchical structure
 A tree consists of nodes with a parentchild relationship
 A parent has one or more children
 Each child has only one parent
 The root is the top node in the tree, the only node without a parent
 An internal node has at least one child
 An external node (or leaf) is a mode with no children
 Nodes have ancestors (ie, the parent node of a parent)
 The depth of a node is its number of ancestors
 The height of a tree is its maximum depth
Tree ADT
Tree ADTs are defined using a similar concept to positional lists, as they don't have a natural ordering/indexing in the same way arrays do.
public interface Tree<E>{
int size();
boolean isEmpty();
Node<E> root(); //returns root node
Node<E> parent(Node<E> n); //returns parent of Node n
Iterable<Node<E>> children(Node<E> n); //collection of all the children of Node n
int numChildren(Node<E> n);
Iterator<E> iterator(); //an iterator over the trees elements
Iterator<Node<E>> nodes(); //collection of all the nodes
boolean isInternal(Node<E> n); //does the node have at least one child
boolean isExternal(Node<E> n); //does the node have no children
boolean isRoot(Node<E> n); //is the node the root
}
Tree Traversal
Trees can be traversed in 3 different orders. As trees are recursive data structures, all 3 traversals are defined recursively. The tree below is used as an example in all 3 cases.
Preorder
 Visit the root
 Pre order traverse the left subtree
 Pre order traverse the right subtree
Preorder traversal of the tree gives: F B A D C E G I H
Inorder
 In order traverse the left subtree
 Visit the root
 In order traverse the right subtree
Inorder traversal of the tree gives: A B C D E F G H I
Postorder
 Post order traverse the left subtree
 Post order traverse the right subtree
 Visit the root
Postorder traversal of the tree gives: A C E D B H I G F
Binary Trees
A binary tree is a special case of a tree:
 Each node has at most two children (either 0, 1 or 2)
 The children of the node are an ordered pair (the left node is less than the right node)
A binary tree will always fulfil the following properties:
 $e=i+1$
 $n=2e−1$
 $h≤i$
 $h≤(n−1)/2$
 $e≤2_{h}$
 $h≥g_{2}e$
 $h≥g_{2}(n+1)−1$
Where:
 $n$ is the number of nodes in the tree
 $e$ is the number of external nodes
 $i$ is the number of internal nodes
 $h$ is the height/max depth of the tree
Binary Tree ADT
The binary tree ADT is an extension of the normal tree ADT with extra accessor methods.
public interface BinaryTree<E> extends Tree<E>{
Node<E> left(Node<E> n); //returns the left child of n
Node<E> right(Node<E> n); //returns the right child of n
Node<E> sibling(Node<E> n); //returns the sibling of n
}
Arithmetic Expression Trees
Binary trees can be used to represent arithmetic expressions, with internal nodes as operators and external nodes as operands. The tree below shows the expression $(2×(a−1))+(3×b)$. Traversing the tree inorder will can be used to print the expression infix, and postorder evaluating each node with it's children as the operand will return the value of the expression.
Implementations
 Binary trees can be represented in a linked structure, similar to a linked list
 Node objects are positions in a tree, the same as positions in a positional list
 Each node is represented by an object that stores
 The element
 A pointer to the parent node
 A pointer to the left child node
 A pointer to the right child node
 Alternatively, the tree can be stored in an array
A
A[root]
is 0 If p is the left child of q,
A[p] = 2 * A[q] + 1
 If p is the right child of q,
A[p] = 2 * A[q] + 2
 In the worst, case the array will have size $2_{n}−1$
Binary Search Trees
 Binary trees can be used to implement a sorted map
 Items are stored in order by their keys
 For a node $p$ with key $K_{p}$, every key in the left subtree is less than $K_{p}$, and every node in the right subtree is greater than $K_{p}$
 This allows for support of nearestneighbour queries, so can fetch the key above or below another key
 Binary search can perform nearest neighbour queries on an ordered map to find a key in $O(gn)$ time
 A search table is an ordered map implemented using a sorted sequence
 Searches take $O(gn)time$
 Insertion and removal take $O(n)$ time
 Only effective for maps of small size
Methods
Binary trees are recursively defined, so all the methods operating on them are easily defined recursively also.
 Search
 To search for a key $K$
 Compare it with the key at $K_{root}$
 If $K_{root}=K$, the value has been found
 If $K_{root}<K$, search the right subtree
 If $K_{root}>K$, search the left subtree
 Insertion
 Search for the key being inserted $K$
 Insert $K$ at the leaf reached by the search
 Deletion
 Find the internal node that is follows the key being inserted in an in order traversal (the in order successor)
 Copy key into the in order successor node
 Remove the node copied out of
Performance
 Consider a binary search tree with $n$ items and height $h$
 The space used is $O(n)$
 The methods get, put, remove take $O(h)$ time
 The height h is $O(gn)$ in the best case, when the tree is perfectly balanced
 In the worst case, when the tree is basically just a linked list, this decays to $O(n)$
AVL Trees
 AVL trees are balanced binary trees
 For every internal node $v$ of the tree, the heights of the subtrees of $v$ can differ by at most 1
 The height of an AVL tree storing $n$ keys is $O(gn)$
 Balance is maintained by rotating nodes every time a new one is inserted/removed
Performance
 The runtime of a single rotation is $O(1)$
 The tree is assured to always have $h=gn$, so the runtime of all methods is $O(gn)$
 This makes AVL trees an efficient implementation of binary trees, as their performance does not decay as the tree becomes unbalanced
Priority Queues
A priority queue is an implementation of a queue where each item stored has a priority. The items with the highest priority are moved to the front of the queue to leave first. A priority queue takes a key along with a value, where the key is used as the priority of the item.
Priority Queue ADT
public interface PriorityQueue<K,V>{
int size();
boolean isEmpty();
void insert(K key, V value); //inserts a value into the queue with key as its priority
V removeMin(); //removes the entry with the lowest key (at the front of the queue)
V min(); //returns but not removes the smallest key entry (peek)
}
Entry Objects
 To store a keyvalue pair, a tuple/pairlike object is needed
 An
Entry<K,V>
object is used to store each queue itemKey
is what is used to defined the priority of the item in the queueValue
is the queue item
 This pattern is similar to what is used in maps
public class Entry<K,V>{
private K key;
private V value;
public Entry(K key, V value){
this.key = key;
this.value = value;
}
public K getKey(){
return key;
}
public V getValue(){
return value;
}
}
Total Order Relations
 Keys may be arbitrary values, so they must have some order defined on them
 Two entries may also have the same key
 A total order relation is a mathematical concept which formalises ordering on a set of objects where any 2 are comparable.
 A total ordering satisfies the following properties $∀a,b,c∈X$
 $a≤b$ or $b≤a$
 Comparability property
 If $a≤b$ $b≤c$, then $a≤c$
 Transitive property
 If $a≤b$ and $b≤a$, then $a=b$
 Antisymmetric property
 $a≤a$
 Reflexive property
 $a≤b$ or $b≤a$
Comparators
 A comparator encapsulates the action of comparing two objects with a total order declared on them
 A priority queue uses a comparator object given to it to compare two keys to decide their priority
public class Comparator<E>{
public int compare(E a, E b){
if(a < b)
return 1;
if(a > b)
return 1;
return 0;
}
}
Implementations
Unsorted ListBased Implementation
A simple implementation of a priority queue can use an unsorted list
insert()
just appends theEntry(key,value)
to the list $O(1)$ time
removeMin()
andmin()
linear search the list to find the smallest key (one with highest priority) to return Linear search takes $O(n)$ time
Sorted ListBased Implementation
To improve the speed of removing items, a sorted list can instead be used. These two implementations have a tradeoff between which operations are faster, so the best one for the application is usually chosen.
insert()
finds the correct place to insert theEntry(key,value)
in the list to maintain the ordering Has to find place to insert, takes $O(n)$ time
 As the list is maintained in order, the entry with the lowest key is always at the front, meaning
removeMin()
andmin()
just pop from the front Takes $O(1)$ time
Sorting Using a Priority Queue
The idea of using a priority queue for sorting is that all the elements are inserted into the queue, then removed one at a time such that they are in order
 Selection sort uses an unsorted queue
 Inserting $n$ items in each $O(1)$ time takes $O(n)$ time
 Removing the elements in order
 $O(n)+O(n−1)+O(n−2)+...+O(1)$
 Overall $O(n_{2})$ time
 Insertion sort uses a sorted queue
 Runtimes are the opposite to unsorted
 Adding $n$ elements takes $O(1)+O(2)+O(3)+...+O(n)$ time
 Removing $n$ elements in each $O(1)$ time takes $O(n)$ time
 Overall runtime of $O(n_{2})$ again
Heaps
 A heap is a treebased data structure where the tree is a complete binary tree
 Two kinds of heaps, minheaps and maxheaps
 For a minheap, the heap order specifies that for every internal node $v$ other than the root, $v≥parent(v)$
 In other words, the root of the tree/subtree must be the smallest node
 This property is inverted for max heaps
 Complete binary tree means that every level of the tree, except possibly the last, is filled, and all nodes are as far left as possible.
 More formally, for a heap of height $h$, for $i=0,1,...,h−1$ there are $2_{i}$ nodes of depth $i$
 At depth $h−1$, the internal nodes are to the left of the external nodes
 The last node of a heap is the rightmost node of maximum depth
 Unlike binary search trees, heaps can contain duplicates
 Heaps are also unordered data structures
 Heaps can be used to implement priority queues
 An
Entry(Key,Value)
is stored at each node
 An
Insertion
 To insert a node
z
into a heap, you insert the node after the last node, makingz
the new last node The last node of a heap is the rightmost node of max depth
 The heap property is then restored using the upheap algorithm
 The just inserted node is filtered up the heap to restore the ordering
 Moving up the branches starting from the
z
 While
parent(z) > (z)
 Swap
z
andparent(z)
 Swap
 While
 Since a heap has height $gn$, this runs in $O(gn)$ time
Removal
 To remove a node
z
from the heap, replace the root node with the last nodew
 Remove the last node
w
 Restore the heap order using downheap
 Filter the replacement node back down the tree
 While
w
is greater than either of its children Swap
w
with the smallest of its children
 Swap
 While
 Also runs in $O(gn)$ time
Heap Sort
For a sequence S
of n
elements with a total order relation on them, they can be ordered using a heap.
 Insert all the elements into the heap
 Remove them all from the heap again, they should come out in order
 $n$ calls of insert take $O(ngn)$ time
 $n$ calls to remove take $O(ngn)$ time
 Overall runtime is $O(ngn)$
 Much faster than quadratic sorting algorithms such as insertion and selection sort
Arraybased Implementation
For a heap with n
elements, the element at position p
is stored at cell f(p)
such that
 If
p
is the root,f(p) = 0
 If
p
is the left childq
,f(p) = 2*f(q)+1
 If
p
is the right childq
,f(p) = 2*f(q)+2
Insert corresponds to inserting at the first free cell, and remove corresponds to removing from cell 0
 A heap with
n
keys has length $O(n)$
Skip Lists
 When implementing sets, the idea is to be able to test for membership and update elements efficiently
 A sorted array or list is easy to search, but difficult to maintain in order
 Skip lists consists of multiple lists/sets
 The skip list $S={S_{0},S_{1},S_{2},...,S_{h}}$
 $S_{0}$ contains all the elements, plus $±∞$
 $S_{i}$ is a random subset of $S_{i−1}$, for $i=1,2,...,h−1$
 Each element of $S_{i−1}$ appears in $S_{i}$ with probability 0.5
 $S_{h}$ contains only $±∞$
Search
To search for an element $x$ in the list:
 Start in the first position of the top list
 At the current position $p$, compare $x$ with the next element in the current list $y$
 If $x=y$, return $y$
 If $x>y$, move to the next element in the list
 "Scan forward"
 If $x<y$, drop down to the element below
 "Drop down"
 If the end of the list ($+∞$) is reached, the element does not exist
Insertion
To insert an element $k$ into the list:
 Repeatedly toss a fair coin until tails comes up
 $i$ is the number of times the coin came up heads
 If $i≥h$, add to the skip list new lists $S_{h+1},...,S_{i+1}$
 Each containing only the two end keys $±∞$
 Search for $k$ and find the positions $p_{0},p_{1},...,P_{i}$ of the items with the largest element $>k$ in each list $S_{0},S_{1},...,S_{i}$
 Same as the search algorithm
 For $j=0..i$, insert k into list $S_{j}$ after position $p_{j}$
Deletion
To remove an entry $x$ from a skip list:
 Search for $x$ in the skip list and find the positions of the items $p_{0},p_{1},...,p_{i}$ containing $x$
 Remove those positions from the lists $S_{0},S_{1},...,S_{i}$
 Remove a list if neccessary
Implementation
A skip list can be implemented using quadnodes, where each node stores
 It's item/element
 A pointer to the node above
 A pointer to the node below
 A pointer to the next node
 A pointer to the previous node
Performance
 The space used by a skip list depends on the random number on each invocation of the insertion algorithm
 On average, the expected space usage of a skip list with $n$ items is $O(n)$
 The run time of the insertion is affected by the height $h$ of the skip list
 A skip list with $n$ items has average height $O(gn)$
 The search time in a skip list is proportional to the number of steps taken
 The dropdown steps are bounded by the height of the list
 The scanforward steps are bounded by the length of the list
 Both are $O(gn)$
 Insertion and deletion are also both $O(gn)$
Graphs
A graph is a collection of edges and vertices, a pair $(V,E)$, where
 $V$ is a set of nodes, called vertices
 $E$ is a collection of pairs of vertices, called edges
 Vertices and edges are positions and store elements
Examples of graphs include routes between locations, users of a social network and their friendships, and the internet.
There are a number of different types of edge in a graph, depending upon what the edge represents:
 Directed edge
 Ordered pair of vertices $(u,v)$
 First vertex $u$ is the origin
 Second vertex $v$ is the destination
 For example, a journey between two points
 Undirected edge
 Unordered pair of vertices $(u,v)$
 In a directed graph, all edges are directed
 In an undirected graph, all edged are undirected
Graph Terminology
 Adjacent vertices
 Two vertices $U$ and $V$ are adjacent (ie connected by an edge)
 Edges incident on a vertex
 The edges connect to a vertex
 $a$, $d$, and $b$ are incident on $V$
 End vertices or endpoints of an edge
 The vertices connected to an edge
 $U$ and $V$ are endpoints of $a$
 The degree of a vertex
 The number of edges connected to it
 $X$ has degree 5
 Parallel edges
 Edges that make the same connection
 $h$ and $i$ are parallel
 Selfloop
 An edge that has the same vertex at both ends
 $j$ is a selfloop
 Path
 A sequence of alternating vertices and edges
 Begins and ends with a vertex
 Each edge is preceded and followed by its endpoints
 $P_{1}=(V,b,X,h,Z)$ is a simple path
 Cycle
 A circular sequence of alternating vertices and edges
 A circular path
 A simple cycle is one where all edges and vertices are distinct
 A nonsimple cycle contains an edge or vertex more than once
 A graph without cycles (acyclic) is a tree
 A circular sequence of alternating vertices and edges
 Length
 The number of edges in a path
 The number of edges in a cycle
Graph Properties
Notation:
 $n$ is the number of vertices
 $m$ is the number of edges
 $g(v)$ is the degree of vertex $v$
The sum of the degrees of the vertices of a graph is always an even number. Each edge is counted twice, as it connects to two vertices, so $∑_{v}g(v)=2m$. For example, the graph shown has $n=4$ and $m=6$. $g(v)=3⇒∑_{v}g(v)=2m=12$
In an undirected graph with no self loops and no multiple edges, $m≤n2n−1 $. Each vertex has degree at most $(n−1)$ and $∑_{v}g(v)=2m$. For the graph shown, $m=6≤n2n−1 =6$
The Graph ADT
A graph is a collection of vertices and edges, which are modelled as a combination of 3 data types: Vertex
, Edge
and Graph
.
 A
Vertex
is just a box object storing an element provided by the user  An
Edge
also stores an associated value which can be retrieved
public interface Graph{
int numVertices();
Collection vertices(); //returns all the graph's vertices
int numEdges();
Collection<Edge> edges(); //returns all the graph's edges
Edge getEdge(u,v); //returns the edge between u and v, if on exists
// for an undirected graph getEdge(u,v) == getEdge(v,u)
Pair<Vertex, Vertex> endVertices(e); //returns the endpoint vertices of edge e
Vertex oppsite(v,e); //returns the vertex adjacent to v along edge e
int outDegree(v); //returns the number of edges going out of v
int inDegree(v); //returns the number of edges coming into v
//for an undirected graph, inDegree(v) == outDegree(v)
Collection<Vertex> outgoingEdges(v); //returns all edges that point out of vertex v
Collection<Vertex> incomingEdges(v); //returns all edges that point into vertex v
//for an undirected graph, incomingEdges(v) == outgoingEdges(v)
Vertex insertVertex(x); //creates and returns a new vertex storing element x
Edge insertEdge(u,v,x); //creates and returns a new edge from vertices u to v, storing element x in the edge
void removeVertex(v); //removes vertex v and all incident edges from the graph
void removeEdge(e); //removes edge e from the graph
}
Representations
There are many different ways to represent a graph in memory.
Edge List
An edge list is just a list of edges, where each edge knows which two vertices it points to.
 The
Edge
object stores It's element
 It's origin
Vertex
 It's destination
Vertex
 The edge list stores a sequence of
Edge
objects
Adjacency List
In an adjacency list, each vertex stores an array of the vertices adjacent to it.
 The
Vertex
object stores It's element
 A collection/array of all it's incident edges
 The adjacency list stores all
Vertex
Objects
Adjacency Matrix
An adjacency matrix is an $n×n$ matrix, where $n$ is the number of vertices in the graph. It acts as a lookup table, where each cell corresponds to an edge between two vertices.
 If there is an edge between two vertices $u$ and $v$, the matrix cell $(u,v)$ will contain the edge.
 Undirected graphs are symmetrical along the leading diagonal
Subgraphs
 A subgraph $S$ of a graph $G$ is a graph such that:
 The vertices of $S$ are a subset of the vertices of $G$
 The edges of $S$ are a subset of the edges of $G$
 A spanning subgraph of $G$ is a subgraph that contains all the vertices of $G$
 A graph is connected if there is a path between every pair of vertices
 A tree is an undirected graph $T$ such that
 $T$ is connected
 $T$ has no cycles
 A forest is an undirected graph without cycles
 The connected components of a forest are trees
 A spanning tree of a connected graph is a spanning subgraph that has all vertices covered with a minimum possible number of edges
 A spanning tree is not unique unless the graph is a tree
 Multiple spanning trees exist
 Spanning trees have applications in the design of communication networks
 A spanning forest of a graph is a spanning subgraph that is a forest
 A spanning tree is not unique unless the graph is a tree
Depth First Search
DFS is a general technique for traversing a graph. A DFS traversal of a graph $G$ will:
 Visit all vertices and edges of $G$
 Determine whether $G$ is connected
 Compute the spanning components of $G$
 Compute the spanning forest of $G$
DFS on a graph with $n$ vertices and $m$ edges takes $O(n+m)$ time. The algorithm is:
 For a graph $G$ and a vertex $u$ of $G$
 Mark vertex $u$ as visited
 For each of $u$'s outgoing edges $e=(u,v)$
 If $v$ has not been visited then
 Record $e$ as the discovery edge for vertex $v$
 Recursively call DFS with on $v$
 If $v$ has not been visited then
DFS(G,V)
visits all vertices and edges in the connected component of v
, and the discovery edges labelled by DFS(G,V)
form a spanning tree of the connected component of v
.
DFS can also be extended to path finding, to find a path between two given vertices $u$ and $v$. A stack is used to keep track of the path, and the final state of the stack is the path between the two vertices. As soon as the destination vertex $v$ is encountered, the contents of the stack is returned.
DFS can be used for cycle detection too. A stack is used to keep track of the path between the start vertex and the current vertex. As soon as a back edge $(v,w)$ (an edge we have already been down in the opposite direction) is encountered, we return the cycle as the portion of the stack from the top to the vertex $w$.
To perform DFS on every connected component of a graph, we can loop over every vertex, doing a new DFS from each unvisited one. This will detect all vertices in graphs with multiple connected components.
Breadth First Search
BFS is another algorithm for graph traversal, similar to DFS. It also requires $O(n+m)$ time. The difference between the two is that BFS uses a stack while DFS uses a queue. The algorithm is as follows:
 Mark all vertices and edges as unexplored
 Create a new queue
 Add the starting vertex $s$ to the queue
 Mark $s$ as visited
 While the queue is not empty
 Pop a vertex $v$ from the queue
 For all neighbouts $w$ of $v$
 If $w$ is not visited
 Push $w$ into the queue
 Mark $w$ as visited
 If $w$ is not visited
For a connected component $G_{s}$ of graph $G$ containing $s$:
 BFS visits all vertices and edges of $G_{s}$
 The discovery edges labelled by
BFS(G,s)
form a spanning tree of $G_{s}$  The path of the spanning tree formed by the BFS is the shortest path between the two vertices
BFS can be specialised to solve the following problems in $O(n+m)$ time:
 Compute the connected components of a graph
 Compute a spanning forest of a graph
 Find a simple cycle in G
 Find the shortest path between two vertices
 DFS cannot do this, this property is unique to BFS
Directed Graphs
A digraph (short for directed graph) is a graph whose edges are all directed.
 Each edge goes in only one direction
 Edge $(a,b)$ goes from a to b but not from b to a
 If the graph is simple and has $n$ vertices and $m$ edges, $m≤n2n−1 $
 DFS and BFS can be specialised to traversing directed edges
 A directed DFS starting at a vertex $s$ determines the vertices reachable from $s$
 One vertex is reachable from another if there is a directed path to it
Strong Connectivity
A digraph is said to be strongly connected if each vertex can reach all other vertices. This property can be identified in $O(n+m)$ time with the following algorithm:
 Pick a vertex $v$ in the graph $G$
 Perform a DFS starting from $v$
 If theres a vertex not visited, return false
 Let $G_{′}$ be $G$ with all the edge directions reversed
 Perform a DFS starting from $v$ in $G_{′}$
 If theres a vertex not visited, return false
 Else, return True
Transitive Closure
Given a digraph $G$, the transitive closure of $G$ is the digraph $G∗$ such that:
 $G∗$ has the same vertices as $G$
 If $G$ has a directed path from $u$ to $v$, then G* also has a directed *edge* from $u$ to $v$
 In $G∗$, every pair of vertices with a path between them in $G$ is now adjacent
 The transitive closure provides reachability information about a digraph
The transitive closure can be computed by doing a DFS starting at each vertex. However, this takes $O(n(n+m))$ time. Alternatively, there is the FloydWarshall algorithm:
 For the graph $G$, number the vertices $1,2,...,n$
 Compute the graphs $G_{0},...,G_{n}$
 $G_{0}=G$
 $G_{k}$ has directed edge $(v_{i},v_{j})$ if $G$ has a directed path from $v_{i}$ to $v_{j}$ with intermediate vertices $v_{1},...,v_{k}$
 Digraph $G_{k}$ is computed from $G_{k−1}$
 $G_{n}=G∗$
 Add $(v_{i},v_{j})$ if edges $(v_{i},v_{k})$ and $(v_{k},v_{j})$ appear in $G_{k−1}$
In pseudocode:
for k=1 to n
Gk = Gk_1
for i=1 to n (i != k)
for j=1 to n (j != i, j!=k)
if G_(k1).areAdjacent(vi,vk) && G_(k1).areAdjacent(vk,vj)
if !G_(k1).areAdjacent(vi,vj)
G_k.insertDirectedEdge(vi,vj,k)
return G_n
This algorithm takes $O(n_{3})$ time. Basically, at each iteration a new vertex is introduced, and each vertex is checked to see if a path exists through the newly added vertex. If it does, a directed edge is inserted to transitively close the graph.
Topological Ordering
 A Directed Acyclic Graph (DAG) is digraph that has no directed cycles
 A topological ordering of a digraph is a numbering $v_{1},v_{2},...,v_{n}$ of the vertices such that for every edge $(v_{i},v_{j})$, $i<j$
 The vertex it points to is always greater than it
 A digraph can have a topological ordering if and only if it is a DAG
A topological ordering can be calculated using a DFS:
public static void topDFS(Graph G, Vertex v){
v.visited = true
for(Edge e: v.edges){
w = opposite(v,e)
if(w.visited = false)
topDFS(G,w)
else{
v.label = n
n = n1
}
}
}
The first node encountered in the DFS is assigned $n$, the one after that $n−1$, and so on until all nodes are labelled.
CS132
Note that specifics details of architectures such as the 68k, its specific instruction sets, or the PATP are not examinable. They are included just to serve as examples.
The 68008 datasheet can be found here, as a useful resource.
Digital Logic
Digital logic is about reasoning with systems with two states: on and off (0 and 1 (binary)).
Basic Logic Functions
Some basic logic functions, along with their truth tables.
NOT
$f=Aˉ$
A  f 

0  1 
1  0 
AND
$f=A⋅B$
A  B  f 

0  0  0 
0  1  0 
1  0  0 
1  1  1 
OR
$f=A+B$
A  B  f 

0  0  0 
0  1  1 
1  0  1 
1  1  1 
XOR
$f=A⊕B$
A  B  f 

0  0  0 
0  1  1 
1  0  1 
1  1  0 
NAND
$f=A⋅B$
A  B  f 

0  0  1 
0  1  1 
1  0  1 
1  1  0 
NOR
$f=A+B $
A  B  f 

0  0  1 
0  1  0 
1  0  0 
1  1  0 
XNOR
$f=A⊕B $
A  B  f 

0  0  1 
0  1  0 
1  0  0 
1  1  1 
Logic Gates
Logic gates represent logic functions in a circuit. Each logic gate below represents one of the functions shown above.
Logic Circuits
Logic circuits can be built from logic gates, where outputs are logical functions of their inputs. Simple functions can be used to build up more complex ones. For example, the circuit below implements the XOR function.
$f=Aˉ⋅B+A⋅Bˉ$
Another example, using only NAND gates to build XOR. NAND (or NOR) gates can be used to construct any logic function.
Truth tables can be constructed for logic circuits by considering intermediate signals. The circuit below has 3 inputs and considers 3 intermediate signals to construct a truth table.
$P=A⋅BQ=A⋅BR=A⋅C$
$f=P+Q+R=A⋅B+A⋅B+A⋅C$
A  B  C  P  Q  R  f 

0  0  0  0  0  0  0 
0  0  1  0  0  0  0 
0  1  0  0  0  0  0 
0  1  1  0  1  0  1 
1  0  0  0  0  0  0 
1  0  1  0  0  1  1 
1  1  0  1  0  0  1 
1  1  1  1  1  1  1 
Truth tables of circuits are important as they enumerate all possible outputs, and help to reason about logic circuits and functions.
Boolean Algebra
 Logic expressions, like normal algebraic ones, can be simplified to reduce complexity
 This reduces the number of gates required for their implementation
 The less gates, the more efficient the circuit is
 More gates is also more expensive
 Sometimes, only specific gates are available too and equivalent expressions must be found that use only the available gates
 Two main ways to simplify expressions
 Boolean algebra
 Karnaugh maps
 The truth table for the expression before and after simplifying must be identical, or you've made a mistake
Expressions from Truth Tables
A sum of products form of a function can be obtained from it's truth table directly.
A  B  C  f 

0  0  0  1 
0  0  1  1 
0  1  0  0 
0  1  1  0 
1  0  0  1 
1  0  1  0 
1  1  0  1 
1  1  1  1 
Taking only the rows that have an output of 1:
 The first row of the table: $Aˉ⋅Bˉ⋅Cˉ$
 The second row: $Aˉ⋅Bˉ⋅C$
 Fifth: $A⋅Bˉ⋅Cˉ$
 Seventh: $A⋅B⋅Cˉ$
 Eight: $A⋅B⋅C$
Summing the products yields:
$f=(Aˉ⋅Bˉ⋅Cˉ)+(Aˉ⋅Bˉ⋅C)+(A⋅Bˉ⋅Cˉ)+(A⋅B⋅Cˉ)+(A⋅B⋅C)$
Boolean Algebra Laws
There are several laws of boolean algebra which can be used to simplify logic expressions:
Name  AND form  OR form 

Identity Law  $1A=A$  $0+A=A$ 
Null Law  $0A=0$  $1+A=1$ 
Idempotent Law  $AA=A$  $A+A=A$ 
Inverse Law  $AAˉ=0$  $A+Aˉ=1$ 
Commutative Law  $AB=BA$  $A+B=B+A$ 
Associative Law  $(AB)C=A(BC)=ABC$  $(A+B)+C=A+(B+C)=A+B+C$ 
Distributive Law  $A+BC=(A+B)(A+C)$  $A(B+C)=AB+AC$ 
Absorption Law  $A(A+B)=A$  $A+AB=A$ 
De Morgan's Law  $A⋅B=Aˉ+Bˉ$  $A+B =Aˉ⋅Bˉ$ 
 Can go from AND to OR form (and vice versa) by swapping AND for OR, and 0 for 1
Most are fairly intuitive, but some less so. The important ones to remember are:
 $A+BC=(A+B)(A+C)$
 $A(B+C)=AB+AC$
 $A(A+B)=A$
 $A+AB=A$
De Morgan's Laws
De Morgan's Laws are very important and useful ones, as they allow to easily go from AND to OR. In simple terms:
 Break the negation bar
 Swap the operator
Example 1
When doing questions, all working steps should be annotated.
$f=(X+Y )⋅(Xˉ+Y )$ $f=(Xˉ⋅Yˉ)⋅(Xˉ+Y )De Morgan OR form$ $f=(Xˉ⋅Yˉ)⋅(X⋅Yˉ)De Morgan AND form$ $f=Xˉ⋅Yˉ⋅X⋅YˉRemove brackets (associative law)$ $f=Xˉ⋅X⋅Yˉ⋅YˉReorder (commutative law)$ $f=0⋅YˉInverse and idempotent laws$ $f=0Null law$
Example 2
$f=X+Yˉ+Xˉ⋅Y+(X+Yˉ)⋅Xˉ⋅Y$ $f=X+Yˉ+Xˉ⋅Y+X⋅⋅Xˉ⋅Y+Yˉ⋅Xˉ⋅YDistributive law$ $f=X+Yˉ+Xˉ⋅Y+0+0Inverse AND law$ $f=X+(Yˉ+Xˉ)(Yˉ+Y)Distributive law$ $f=X+(Yˉ+Xˉ)⋅1Inverse law$ $f=X+Yˉ+XˉRemoving 1 and brackets (identity and associative laws)$ $f=Yˉ+1Inverse OR law$ $f=1Null law$
Karnaugh Maps
 Karnaugh Maps (kmaps) are sort of like a 2D truth table
 Expressions can be seen from the location of 1s in the map
A  B  f 

0  0  a 
0  1  b 
1  0  d 
1  1  c 
 Functions of 3 variables can used a 4x2 or 2x4 map (4 variables use a 4x4 map)
 Adjacent squares in a kmap differ by exactly 1 variable
 This makes the map gray coded
 Adjacency also wraps around
The function $f=ABCˉD+ABˉCˉD+AˉBˉCD+AˉBCD$ is shown in the map below.
Grouping
 Karnaugh maps contain groups, which are rectangular clusters of 1s 
 To simplify a logic expression from a kmap, identify groups from it, making them as large and as few as possible
 The number of elements in the group must be a power of 2
 Each group can be described by a singular expression
 The variables in the group are the ones that are constant within the group (ie, define that group)
Sometimes, groups overlap which allow for more than one expression
The function for the map is therefore either $f=AˉBˉCˉ+AˉBD+BCD$ or $f=AˉBˉCˉ+AˉCˉD+BCD$ (both are equivalent)
Sometimes it is not possible to minimise an expression. the map below shows an XOR function $f=(A⊕B)⊕(C⊕D)$
Don't Care Conditions
Sometimes, a certain combination of inputs can't happen, or we dont care about the output if it does. An X
is used to denote these conditions, which can be assumed as either 1 or 0, whichever is more convenient.
Combinatorial Logic Circuits
Some useful circuits can be constructed using logic gates, examples of which are shown below. Combinatorial logic circuits operate as fast as the gates operate, which is theoretically zero time (realistically, there is a nanosecondlevel tiny propagation delay).
1Bit Half Adder
 Performs the addition of 2 bits, outputting the result and a carry bit.
A  B  Sum  Carry 

0  0  0  0 
0  1  1  0 
1  0  1  0 
1  1  0  1 
1Bit Full Adder
 Adds 2 bits plus carry bit, outputting the result and a carry bit.
Carry in  A  B  Sum  Carry out 

0  0  0  0  0 
0  0  1  0  1 
0  1  0  0  1 
0  1  1  1  0 
1  0  0  0  1 
1  0  1  1  0 
1  1  0  1  0 
1  1  1  1  1 
NBit Full Adder
 Combination of a number of full adders
 The carry out from the previous adder feeds into the carry in of the next
NBit Adder/Subtractor
 To convert an adder to an adder/subtractor, we need a control input $Z$ such that:
 $Z=0⇒S=A+B$
 $Z=1⇒S=A−B$
 $−B$ is calculated using two's complement
 Invert the N bit binary number B by doing $Z⊕B$
 Add 1 (make the starting carry in a 1)
Encoders & Decoders
 A decoder has binary input pins, and one output pin per possible input state
 eg 2 inputs has 4 unique states so has 4 outputs
 3 inputs has 8 outputs
 Often used for addressing memory
 The decoder shown below is active low
 Active low means that 0 = active, and 1 = inactive
 Converse to what would usually be expected
 Active low pins sometimes labelled with a bar, ie $enable$
 Active low means that 0 = active, and 1 = inactive
 It is important to be aware of this, as ins and outs must comform to the same standard
$X_{0}$  $X_{1}$  $Y_{0}$  $Y_{1}$  $Y_{2}$  $Y_{3}$ 

0  0  0  1  1  1 
0  1  1  0  1  1 
1  0  1  1  0  1 
1  1  1  1  1  0 
 Encoders are the opposite of decoders, encoding a set of inputs into outputs
 Multiple input pins, only one should be active at a time
 Active low encoder shown below
$Y_{0}$  $Y_{1}$  $Y_{2}$  $Y_{3}$  $X_{0}$  $X_{1}$ 

0  1  1  1  0  0 
1  0  1  1  0  1 
1  1  0  1  1  0 
1  1  1  0  1  1 
Multiplexers & DeMultiplexers
Multiplexers have multiple inputs, and then selector inputs which choose which of the inputs to put on the output.
$S_{0}$  $S_{1}$  Y 

0  0  $X_{0}$ 
0  1  $X_{1}$ 
1  0  $X_{2}$ 
1  1  $X_{3}$ 
$Y=X_{0}Sˉ_{0}Sˉ_{1}+X_{1}Sˉ_{0}S_{1}+X_{2}S_{0}Sˉ_{1}+X_{3}S_{0}S_{1}$
DeMultiplexers are the reverse of multiplexers, taking one input and selector inputs choosing which output it appears on. The one shown below is active low
$S_{0}$  $S_{1}$  $Y_{0}$  $Y_{1}$  $Y_{2}$  $Y_{3}$ 

0  0  A  1  1  1 
0  1  1  A  1  1 
1  0  1  1  A  1 
1  1  1  1  1  A 
$Y_{0}=A+Sˉ_{0}S_{1}+S_{0}Sˉ_{1}+S_{0}S_{1}=A+S_{1}+S_{0}$
Multiplexers and DeMultiplexers are useful in many applications:
 Source selection control
 Share one communication line between multiple senders/receivers
 Parallel to serial conversion
 Parallel input on X, clock signal on S, serial output on Y
Sequential Logic Circuits
A logic circuit whose outputs are logical functions of its inputs and it's current state
FlipFlops
Flipflops are the basic elements of sequential logic circuits. They consist of two nand gates whose outputs are fed back to the inputs to create a bistable circuit, meaning it's output is only stable in two states.
 $Sˉ$ and $Rˉ$ are active low set and reset inputs
 $Q$ is set high when $Sˉ=0$ and $Rˉ=1$
 $Q$ is reset (to zero) when $Rˉ=0$ and $Sˉ=1$
 If $Sˉ=Rˉ=1$ then $Q$ does not change
 If both $Sˉ$ and $Rˉ$ are zero, this is a hazard condition and the output is invalid
$Sˉ$  $Rˉ$  Q  P 

0  0  X  X 
0  1  1  0 
1  0  0  1 
1  1  X  X 
The timing diagram shows the operation of the flip flop
DType Latch
A Dtype latch is a modified flipflop circuit that is essentially a 1bit memory cell.
 Output can only change when the enable line is high
 $D=Q$ when enabled, otherwise $Q$ does not change ($Q=Q$)
 When enabled, data on $D$ goes to $Q$
Enable  $D$  $Q$  $Qˉ $ 

0  0  $Q$  $Qˉ $ 
0  1  $Q$  $Qˉ $ 
1  0  0  1 
1  1  1  0 
Clocked FlipFlop
There are other types of clocked flipflop whose output only changes on the rising edge of the clock input.
 $↑$ means rising edge responding
Nbit Register
 A multibit memory circuit built up from dtype latches
 The number on $A_{N−1}A_{N−2}...A_{1}A_{0}$ is stored in the registers when the clock rises
 The stored number appears on the outputs $Q$
 $Q$ cannot change unless the circuit is clocked
 Parallel input, parallel output
Nbit Shift Register
 A register that stores and shifts bits taking one bit input at a time
 Serial input, parallel output
 When a clock transition occurs, each bit in the register will be shifted one place
 Useful for serial to parallel conversion
Nbit Counter
 The circles on the clock inputs are inverted on all but the first
 Each flipflop is triggerd on a high > low transition of the previous flipflop
 Creates a counter circuit
Output is 0000, 1000, 0100, 1100, 0010, etc...
 The first bit swaps every clock
 2nd bit swaps every other clock
 3rd bit swaps every fourth clock
 etc...
Three State Logic
 Three state logic introduces a third state to logic  unconnected
 A threestate buffer has an enable pin, which when set high, disconnects the output from the input
 Used to prevent connecting outputs to outputs, as this can cause issues (short circuits)
This can be used to allow different sources of data onto a common bus. Consider a 4bit bus, where 2 4bit inputs are connected using 3state buffers. Only one of the buffers should be enabled at any one time.
 When $E1=0$, A will be placed on the bus
 When $E2=0$, B will be placed on the bus
Physical Implementations
Logic gates are physical things with physical properties, and these have to be considered when designing with them. Typical voltage values for TTL (TransistorTransistor Logic):
 5v  max voltage
 2.8v  minimum voltage for a logical 1
 2.80.8v  "forbidden region", ie voltages in this region are undefined
 0.80v  voltage range for a logical 0
Propagation Delay
 Logic gates have a propagation delay, the amount of time it takes for the output to reflect the input
 Typically a few nanoseconds or less
 This limits the speed at which logic circuits can operate
 Delay can be reduced by increasing density of gates on an IC
Integrated Circuits
 Elementary logic gates can be obtained in small ICs
 Programmable deviced allow large circuits to be created inside a single chip
 PAL  Programmable Array Logic
 Onetime programmamble
 PLA  Programmable Logic Array
 Contains an array of AND and OR gates to implement any logic functions
 FPGA  Field Programmable Gate Array
 Contains millions of configurable gates
 More modern
 PAL  Programmable Array Logic
PLA example
A PLA allows for the implementation of any sumofproducts function, as it has an array of AND gates, then OR gates, with fuses that can be broken to implement a specific function.
Assembly
Microprocessor Fundamentals
The CPU
 The CPU controls and performs the execution of instructions
 Does this by continuously doing fetchdecodeexecute cycle
 Very complex, but two key components
 Control Unit (CU)
 Decodes the instructions and handles logistics
 Arithmetic Logic Unit (ALU)
 Does maths
 Control Unit (CU)
FetchDecodeExecute
 Three steps to every cycle
 Fetch instructions from memory
 Decode into operations to be performed
 Execute to change state of CPU
 Takes place over several clock cycles
The components of the CPU that are involved in the cycle:
 ALU
 CU
 Program Counter (PC)
 Tracks the memory address of the next instruction to be executed
 Instruction Register (IR)
 Contains the most recent instruction fetched
 Memory Address Register (MAR)
 Contains address of the memory location to be read/written
 Memory Data/Buffer Register (MDR/MBR)
 Contains data fetched from memory or to be written to memory
The steps of the cycle:
 Fetch
 Instruction fetched from memory location held by PC
 Fetched instruction stored in IR
 PC incremented to point to next instruction
 Decode
 Retrieved instruction decoded
 Establish opcode type
 Execute
 CU signals the necessary CPU components
 May result in changes to data registers, ALU, I/O, etc
The 68008
The 68008 is an example of a CPU. The "programmer's model" is an abstraction that represents the internals of the architecture. The internal registers as shown below are part of the programmer's model.
 Internal registers are 32 bits wide
 Internal data buses are 16 bit wide
 8 bit external data bus
 20 bit external address bus
 D0D7 are 32 bit registers used to store frequently used values
 Can be long (32 bits), word (16 bits), or byte (8 bits)
 Status register (CCR) consists of 2 8bit registers
 Various status bits are set or reset depending upon conditions arising from execution
 A0A6 are pointer registers
 A7 is system stack pointer to hold subroutine return addresses
 Operations on addresses do not alter status register/ CCR
 Only ALU can incur changes in status
 The stack pointer is a pointer to the next free location in the system stack
 Provides temporary storage of state, return address, registers, etc during subroutine calls and interrupts
The diagram shows the internal architecture of the CPU, and how the internal registers are connected via the buses. Note how and which direction data moves in, as indicated by the arrows on the busses.
Register Transfer Language
The fetchdecodeexecute cycle is best described using Register Transfer Language (RLT), a notation used to show how data moves around the internals of a processor and between registers.
 For example
[MAR] < [PC]
denotes the transfer of the contents of the program counter to the memory address register  Computer's main memory is called Main Store (MS), and the contents of memory location
N
is denoted[MS(N)]
 RLT does not account for the pipelining of instructions
 Fetching an instruction in RTL:
RLT  Meaning 

[MAR] < [PC]  Move contents of PC to MAR 
[PC] < [PC] + 1  Increment PC 
[MBR] < [MS([MAR])]  Read address from MAR into MBR. 
[IR] < [MBR]   Load instruction into I 
CU < [IR(opcode)]  Decode the instruction 
Assembly Language
 Assembly is the lowest possible form of code
 High level code (for example C) is compiled to assembly code
 Assembly is then assembled into machine code (binary)
 Assembly instructions map 1:1 to processor operations
 Uses mnemonics for instructions, ie
MOV
orADD
 Languages vary, but format tends to be similar:
LABEL: OPCODE OPERAND(S)  COMMENT
An example program is shown below
ORG $4B0  this program starts at hex 4B0
move.b #5, D0  load D0 with number 5
add.b #$A, D0  add 10 (0x0A) to D0
move.b D0, ANS  move contents of D0 to ANS
ANS: DS.B 1  leave 1 byte of memory empty and name it ANS
#
indicates a literal$
means hexadecimal%
means binary A number without a prefix is a memory address
ANS
is a symbolic nameORG
(Origin) indicates where to load the program in memoryDS
(Define Storage) tells the assembler where to put data
The 68008 Instruction Set
 Instructions are commands that tell the processor what to do
 5 main kinds of instructions
 Logical
 Bitwise operations
AND
,LSL
(Logical Shift Left)
 Branch
 Cause the processor to jump execution to a labelled address
 Condition is specified by testing state of CCR set by previous instruction
BRA
 branch unconditionallyBEQ
 branch if equal
 System Control
 Logical
 Instructions are also specified with their data type,
.b
for byte,.w
for word,.l
for longmove.w
moves 2 bytes
Data Movement
 Similar to RTL
move.b D0, D1  [D1(0:7)] < [D0(0:7)]
move.w D0, D1  [D1(0:15)] < [D0(0:15)]
swap D2  swap lower and upper words
move.l $F20, D3  [D3(24:31)] ← [MS($F20)]
 [D3(16:23)] ← [MS($F21)]
 [D3( 8:15)] ← [MS($F22)]
 [D3( 0:7)] ← [MS($F23)]
 copied 8 bytes at a time in big endian order
Arithmetic
 Maths performed on the ALU
 The 68008, like many older processors, has no FPU, so only integer operations are supported
add.l Di, Dj  [Dj] ← [Di] + [Dj]
addx.w Di, Dj  also add in x bit from CCR
sub.b Di, Dj  [Dj] ← [Dj]  [Di]
subx.b Di, Dj  also subtract x bit from CCR
mulu.w Di, Dj  [Dj(0:31)] ← [Di(0:15)] * [Dj(0:15)]
 unsigned multiplication
muls.w Di, Dj  signed multiplication
Logical
 Perform bitwise operations on data
 Also done by ALU
 AND, OR, etc but also shifts and rotates
 Logical shift (
LSL
/LSR
) adds a 0 when shifting Bit shifted out goes into C and X
 Arithmetic shift preserves sign bit (
ASL
/ASR
)  Normal rotate (
ROL
/ROR
) moves the top of the bit to the bottom bit and also puts the top bit into C and X  Rotate through X (
ROXL
/ROXR
) rotates the value through the X register
AND.B #$7F, D0  [D0] < [D0] . [0x7F]
OR.B D1, D0  [D0] < [D0] + [D1]
LSL D0, 2  [D0] < [D0] << [2]
Branch
 Cause the processor to move execution to a new pointer (jump/GOTO)
 Instruction tests the state of the CCR bits against certain condition
 Bits set by previous instructions
BRA  branch unconditionally
BCC  branch on carry clear
BEQ  branch on equal
System Control
 Certain instructions used to issue other commands to the microprocessor
Subroutines and Stacks
 Subroutines are useful for frequently used sections of code for obvious reasons
 Can jump and return from subroutines in assembly
JSR <label>
 Jump to SubroutineRTS
 Return from Subroutine
 When returning, need to know where to return to
 The stack is used as a LIFO data structure to store return addresses
JSR
pushes the contents of the PC on the stackRTS
pops the return address from the stack to the PC Can nest subroutine calls and stack will keep track
Addressing Modes
 Addressing modes are how we tell the computer where to find the data it needs
 5 Kinds in the 68006, and many other processors have equivalents
 Direct
 Immediate
 Absolute
 Address Register Indirect
 5 variations
 Relative
Direct Addressing
 Probably the simplest
 The address of an operand is specified by either a data or address register
move D3, D2  [D2] < [D3]
move D3, A2  [A2] < [D3]
Immediate Addressing
 The operand forms part of the instruction (is a literal) and remains a constant
 Note the prefix
#
specifying a literal and the prefix specifying the base of the number
move.b #$42, D5  [D5] < $42
Absolute Addressing
 Operand specifies the location in memory
 Does not allow for positionindependent code: will always access the exact address given
move.l D2, $7FFF0  [MS(7FFF0)] < [D2]
Address Register Indirect Addressing
 Uses offsets/increments/indexing to address memory based upon the address registers
 Bad, rarely used
 Not examinable
Relative Addressing
 Specifies an offset relative to the program counter
 Can be used to write position independent code
move 16(PC), D3  [D3] < [MS(PC + 16)]
Memory Systems
The Memory Hierarchy
 Memory systems must facilitate the reading and writing of data
 Many factors influence the choice of memory technology
 Frequency of access
 Access time
 Capacity
 Cost
 Memory wants to be low cost, high capacity, and also fast
 As a tradeoff, we organise memory into a hierarchy
 Allows for some high speed, some high capacity
 Data has to be dragged up the hierarchy
 Memory access is somewhat predictable
 Temporal locality  when a location accessed, likely the same location will be accessed again in the near future
 Spatial locality  when a location accessed, likely that nearby locations will be referenced in the near future
 90% of memory access is within 2Kb of program counter
Semiconductor Memory Types
Memory Type  Category  Erasure  Write Mechanism  Volatility 

Random Access Memory (RAM)  ReadWrite  Electronically, at bytelevel  Electronically written  Volatile 
Read Only Memory (ROM)  Read only  Not possible  Mask Written  Nonvolatile 
Programmable ROM (PROM)  Read only  Not possible  Electronically written  Nonvolatile 
Erasable PROM (EPROM)  Read (mostly)  UV light at chip level  Electronically written  Nonvolatile 
Electrically Erasable PROM (EEPROM)  Read (mostly)  Electronically, at bytelevel  Electronically written  Nonvolatile 
Flash Memory  Read (mostly)  Electronically, at bytelevel  Electronically written  Nonvolatile 
 Particularly interested in random access
 RAM is most common  implements main store
 nb that all types shown here allow random access, name is slightly misleading
 RAM is also volatile, meaning it is erased when de powered
Cache
 If 90% of memory access is within 2Kb, store those 2Kb somewhere fast
 Cache is small, fast memory right next to CPU
 10200 times faster
 If data requested is found in cache, this is a "cache hit" and provides a big speed improvement
 We want things to be in cache
 Cache speed/size is often a bigger bottleneck to performance than clock speed
Moore's Law
 As said by the cofounder of intel, Gordon Moore, the number of transistors on a chip will double roughly every 18 months
 Less true in recent years
 Cost of computer logic and circuitry has fallen dramatically in the last 30 years
 ICs become more densely paced
 CPU clock speed is also increasing at a similar rate
 Memory access speed is improving much more slowly however
Cache Concepts
 Caching readonly data is relatively straightforward
 Don't need to consider the possibility data will change
 Copies everywhere in the memory hierarchy remain consistent
 When caching mutable data, copies can become different between cache/memory
 Two strategies for maintaining parity
 Write through  updates cache and then writes through to update lower levels of hierarchy
 Write back  only update cache, then when memory is replaced copy blocks back from cache
Cache Performance
Cache performance is generally measured by its hit rate. If the processor requests some block of memory and it is already in cache, this is a hit. The hit rate is calculated as
$h=total number of memory accessestotal number of cache hits $
Cache misses can be categorised:
 Compulsory  misses that would occur regardless of cache size, eg the first time a block is accessed, it will not be in cache
 Capacity  misses that occur because cache is not large enough to contain all blocks needed during program execution
 Conflict  misses that occur as a result of the placement strategy for blocks not being fully associative, meaning a block may have to be discarded and retrieved
 Coherency  misses that occur due to cache flushes in multiprocessor systems
Measuring performance solely based upon cache misses is not accurate as it does not take into factor the cost of a cache miss. Average memory access time is measured as hit time + (miss rate $×$ miss penalty).
Cache Levels
Cache has multiple levels to provide a tradeoff between speed and size.
 Level 1 cache is the fastest as it is the closest to the cpu, but is typically smallest
 Sometimes has separate instructions/data cache
 Level 2 cache is further but larger
 Level 3 cache is slowest (but still very fast) but much larger (a few megabytes)
 Some CPUs even have a level 4 cache
Different levels of cache exist as part of the memory hierarchy.
Semiconductors
 RAM memory used to implement main store
 Static RAM (SRAM) uses a flipflop as the storage element for each bit
 Uses a configuration of flipflops and logic gates
 Hold data as long as power is supplied
 Provide faster read/write than DRAM
 Typically used for cache
 More expensive
 Dynamic RAM (DRAM) uses a capacitor, and the presence to denote a bit
 Typically simpler design
 Can be packed much tighter
 Cheaper to produce
 Capacitor charge decays so needs refreshing by periodically supplying charge
 The interface to main memory is a critical performance bottleneck
Memory Organisation
The basic element of memory is a onebit cell with two states, capable of being read and written. Cells are built up into larger banks with combinatorial logic circuits to select which cell to read/write. The diagram shows an example of a 16x8 memory IC (16 words of 8 bytes).
For a 16x8 memory cell:
 4 address inputs
 $g_{2}16$
 8 data lines
 word size
Consider alternatively a 1Kbit device with 1024 cells
 Organised as a 128x8 array
 7 address pins
 8 data pins
 Or, could organise as 1024x1 array
 10 address pins
 1 data pins
 Less pins but very poorly organised
 Best to keep memory cells square to make efficient use of space
Error Correction
Errors often occur within computer systems in the transmission of data dude to noise and interference. This is bad. Digital logic already gives a high degree of immunity to noise, but when noise is at a high enough level, this collapses.
Two common ways in which errors can occur:
 Isolated errors
 Occur at random due to noise
 Usually singular incidences
 Burst errors
 Errors usually occur in bursts
 A short period of time over which multiple errors occur
 For example, a 1ms dropout of a connection can error many bits
Majority Voting
 A simple solution to correcting errors
 Just send every bit multiple times (usually 3)
 The one that occurs the most is taken to be the true value
 Slow & expensive
Parity
 Parity adds an extra parity bit to each byte
 Two types of parity system
 Even parity
 The value of the extra bit is chosen to make the total number of 1s an even number
 Odd parity
 The value of the extra bit is chosen to make the total number of 1s an odd number
 Even parity
 7 bit ascii for
A
is0100 0001
 With even parity 
0100 0001
 Odd parity 
1100 0001
 With even parity 
 Can be easily computed in software
 Can also be computed in hardware using a combination of XOR gates
 Usually faster than in software
 Allows for easy error detection without the need to significantly change the model for communication
 Parity bit is computed and added before data is sent, parity is checked when data is received
 Note that if there is more than one error, the parity bit will be correct still and the error won't be detected
 Inadequate for detecting bursts of error
Error Correcting Codes
 ECCs or checksums are values computed from the entire data
 If any of the data changes, the checksum will also change
 The checksum is calculated and broadcast with the data so it can be checked on reception
 Can use row/column parity to compute an checksum
 Calculate parity of each row and of each column
 Diagram shows how parity bits detect an error in the word "Message"
I/O
Memory Mapped I/O
 With memory mapped I/O, the address bus is used to address both memory and I/O devices
 Memory on I/O devices is mapped to values in the main address space
 When a CPU accesses a memory address, the address may be in physical memory (RAM), or the memory of some I/O device
 Advantages
 Very simple
 CPU requires less internal logic
 Can use general purpose memory instructions for I/O
 Disadvantages
 Have to give up some memory
 Less of a concern on 64bit processors
 Still relevant in smaller 16 bit CPUs
 Have to give up some memory
Polled I/O
 Polling is a technique for synchronising communication between devices.
 Most I/O devices are much slower than the CPU
 Busywait polling involves constantly checking the state of the device
 Usually the device replies with nothing
 Can interleave polls with something else useful
 Advantages
 Still relatively simple
 Disadvantages
 Wastes CPU time and power
 Interleaving can lead to delayed responses from CPU
Synchronisation methods also need some way to transfer the data, so are sometimes used in conjunction with memorymapped I/O. Methods for synchronising devices and methods for reading/writing data are not directly comparable.
Handshaking
Another form of synchronisation
 Computer responds to the printer being ready by placing data on the data bus and signalling
DATA_VALID
 Can do this either in hardware or in software
 Timing diagram shows data exchange
 During periods where both signals are at a logical 0, data is exchanged
Handshaking Hardware
Handshaking is usually done using an external chip, such as the 6522 VIA (Versatile Interface Adapter)
Setting bit values in the PCR (Peripheral Control Register) on the VIA allows to control the function.
 Use PORT B as output
 CB1 control line as
PRINTER_READY
 CB2 control line as
DATA_VALID
 For CB1 and CB2 control, 8 bit register is set to 1000xxxx
 Last 4 bits not used, don't care
Interrupts
 Asynchronous I/O
 Two kinds of interrupts (in 6502 processor)
 Interrupt Request (IRQ)
 Code can disable response
 Sent with a priority
 If priority lower than that of current task, will be ignored
 Can become nonmaskable if ignored for long enough
 NonMaskable Interrupt (NMI)
 Cannot be disabled, must be serviced
 Interrupt Request (IRQ)
 An interrupt forces the CPU to jump to an Interrupt Service Routine (ISR)
 Switches context, uses stack to store state of registers
 ISRs can be nested
 Interrupts usually generated by some external device
 Hard drive can generate an interrupt when data is ready
 A timer can generate an interrupt repeatedly at a fixed interval
 A printer can generate an interrupt when ready to receive data
 Advantages
 Fast response
 No wasted CPU time
 Disadvantages
 All data transfer still CPU controlled
 More complex hardware/software
Direct Memory Access (DMA)
 The CPU is a bottleneck for I/O
 All techniques shown so far are limited by this bottleneck
 DMA is used where large amounts of data must be transferred quickly
 Control of system busses surrendered from CPU to a DMA Controller (DMAC)
 DMAC is a dedicated device optimised for data transfer
 Can be up to 10x faster than CPUdriven I/O
DMA Operation
 DMA transfer is requested by I/O
 DMAC passes request to CPU
 CPU initialises DMAC
 Input or Output?
 Start address is put into DMAC address register
 Number of words is put into DMAC count register
 CPU enables DMAC
 DMAC requests use of system busses
 CPU responds with DMAC ack when ready to surrender busses
 DMAC can operate in different modes
 Cycle stealing
 Uses system busses when they're not being used by CPU
 Burst mode
 Requires busses for extended period of time, locks the CPU out for a fixed time, until transfer complete, or until CPU receives interrupt from device of higher priority
 Cycle stealing
DMA Organisation
There are multiple ways a DMA can be incorporated into a system:
 Single bus, detached DMA
 All modules (DMA, I/O devices, memory, CPU) share system bus
 DMA uses programmed I/O to exchanged data between memory and I/O device
 Straightforward, as DMA can just mimic processor
 Inefficient
 Separate I/O bus
 Only one interface to DMA module
 The bus the DMA shares with processor and memory is only used to transfer data to and from memory
Summary
 **Memorymapped **deviced are accessed in the same way as RAM, at fixed address locations
 Polled I/O is for scheduling input and output, where the CPU repeatedly checks for data
 I/O devices are slow, so handshaking techniques coordinate CPU and device for transfer of data
 Interrupts avoid polled I/O by diverting the CPU to a special I/O routine when necessary
 A DMA controller can be used instead of the CPU to transfer data into and out of memory, faster than the CPU but at additional hardware cost
Microprocessor Architecture
 Computer architecture concerns the structure and properties of a computer system, from the perspective of a software engineer
 Computer organisation concerns the structure and properties of a computer system, from the perspective of a hardware engineer
The PATP
The Pedagogically Advanced Teaching Processor is a very simple microprocessor. The specifics of it are not examinable, but it is used to build an understanding of microprocessor architecture.
Programmer's model
The PATP has 8 instructions. Each instruction is 1 8bit word, with the first 3 bits as the opcode and last 5 as the operand, if applicable.
Opcode  Mnemonic  Macro Operation  Description 

000  CLEAR  [D0] < 0  Set D0 to 0 (and set Z ) 
001  INC  [D0] < [D0] + 1  Increment the value in D0 (and set Z if result is 0) 
010  ADD #v  [D0] < [D0] + v  Add the literal v to D0 (and set Z if result is 0) 
011  DEC  [D0] < [D0]  1  Decrement the value in D0 (and set Z if result is 0) 
100  JMP loc  [PC] < loc  Jump unconditionally to address location loc 
101  BNZ loc  If Z is not 0 then [PC] < loc  Jump to address location loc if Z is not set 
110  LOAD loc  [DO] < [MS(loc)]  Load the 8 bit value from address location loc to D0 
111  STORE loc  [MS(loc)] < [D0]  Write the 8 bit value from D0 to address location loc 
This is not many instructions, but it is technically Turingcomplete. The other specs of the PATP are:
 An address space of 32 bytes (the maximum address is
11111
)  A single 8bit data register/accumulator
D0
 A CCR with only 1 bit (
Z
, set when an arithmetic operation has a result of zero)  A 5bit program counter (only 5 bits needed to address whole memory)
Internal Organisation
There are several building blocks that make up the internals of the PATP:
 The data register
D0
 An 8 bit register constructed from Dtype flipflops
 Has parallel input and output
 Clocked
 The ALU
 Built around an 8bit adder/subtractor
 Has two 8bit inputs
P
andQ
 Capable of
 Increment (+1)
 Decrement (1)
 Addition (+n)
 Two function select inputs
F1
andF2
which choose the operation to perform 00: Zero output
 01: Q + 1
 10: Q + P
 11: Q  1
 An output
F(P, Q)
which outputs the result of the operation  A
Z
output for the CCR
 The main system bus
 Uses 3state buffers to enable communication
 The control unit
 Controls:
 The busses (enables)
 When registers are clocked
 ALU operation
 Memory acccess
 Responsible for decoding instructions and issuing microinstructions
 Inputs
 Opcode
 Clock
Z
register
 Outputs
 Enables
 Main store
 Instruction register
IR
 Program counter
 Data register
D0
 ALU register
 Clocks
 Memory address register
MAR
 Instruction register
IR
 Program counter
 Data register
D0
 ALU register
 Memory address register
F1
andF2
on the ALUR
/W
to control bit for main store
 Enables
 Controls:
All the components come together like so:
Micro and Macro Instructions
There are several steps internally that are required to execute a single instruction. For example, to execute an INC
operation:
 D0 need to be put on the system bus
 CU enables the threestate buffer for D0
[ALU(Q)] < D0
 The correct ALU function must be selected
F1 = 0
,F2 = 1
 Signals asserted by CU
[ALU(F)] < 01
 The output from the ALU must be read into the ALU register
 ALUreg clocked by CU
[ALUreg] < [ALU]
 D0 reads in the ALU output from the ALU register
 CU enables the threestate buffer for ALUreg
 D0 is clocked by CU
Macro instructions are the assembly instructions issued to the processor (to the CU, specifically), but micro instructions provide a low level overview of how data is moved around between internals of the CPU and what signals are asserted internally. The PATP can execute all instructions in 2 cycles. The table below gives an overview of the micro operations required for each macro instruction, along with the macro operations for fetching from main store.
Control Signals
The control unit asserts control signals at each step of execution, and the assertion of these control signals determine how data moves internally. For the PATP:
 Enable signals are leveltriggered
 Clock signals are falling edgetriggered
 An output can be enabled onto the main bus and then clocked elsewhere in a single time step
 ALU timings assume that, if values are enabled at P and Q at the start of a cycle, then the ALU register can be clocked on the falling edge of that cycle
 MS timings assume that if MAR is loaded during one cycle, then R, W and EMS can be used in the next cycle
The diagram below shows the timing for a fetch taking 4 cycles, and which components are signalled when. Notice which things happen in the same cycle, and which must happen sequentially.
cycle  MicroOp  Control Signals 

1  [MAR] < [PC]  Enable PC, Clock MAR 
2  [IR] < [MS(MAR)]  Set read for MAR, Enable MS, Clock IR 
3  [ALU(Q)] < [PC]  Enable PC 
3  [ALU(F) < 01]  F1 = 0, F2 = 1 
3  [ALUreg] < [ALU]  Clock ALUreg 
4  [PC] < [ALUreg]  Enable ALUreg, Clock PC 
Control Unit Design
The task of the control unit is to coordinate the actions of the CPU, namely the FetchDecodeExecute cycle. It generates the fetch control sequence, takes opcode input, and generates the right control sequence based on this. It can be designed to do this in one of two ways:
 Hardwired design (sometimes called "random logic")
 The CU is a combinatorial logic circuit, transforming input directly to output
 Microprogrammed
 Each opcode is turned into a sequence of microinstructions, which form a microprogram
 Microprograms stored in ROM called microprogram memory
Hardwired
 A sequencer is used to sequence the clock cycles
 Has clock input and n outputs
T1 ... Tn
 First clock pulse is output from
T1
 Second is output from
T2
 Clock pulse n output from
Tn
 Pulse n+1 output from
T1
 Has clock input and n outputs
 This aligns the operation of the circuit with the control steps
 Advantages
 Fast
 Disadvantages
 Complex, difficult to design and test
 Inflexible, cant change design to add new instructions
 Takes a long time to design
 This technique is most commonly used in RISC processors and has been since the 80s
 The control signal generator maps each instruction to outputs
 The sequencer sequences the outputs appropriately
 The flipflop is used to regulate control rounds
Microprogrammed
 The microprogram memory stores the required control actions for each opcode
 The CU basically acts as a mini CPU within the CPU
 Microaddress is a location within microprogram memory
 MicroPC is the CU's internal program counter
 MicroIR is the CU's internal microinstruction register
 The microPC can be used in different ways depending upon implementation
 Holds the next microaddress
 Holds the microaddress of microroutine for next opcode
 When powered initially holds microaddress 0
 The fetch microprogram
 Each microinstruction sets the CU outputs to the values dictated the instruction
 As the microprogram executes, the CU generates control signals
 After each microinstruction, the microPC is typically incremented, so microinstructions are stepped through in sequence
 After a fetch, the microPC is not incremented, but is set to the output from the opcode decoding circuit (labelled OTOA in the diagram)
 After a normal opcode microprogram, the microPC is set back to 0 (fetch)
 When executing the microprogram for a conditional branch instruction, the microPC value is generated based upon whether the CU's Z input is set
 Advantages
 Easy to design and implement
 Flexible design
 Simple hardware compared to alternative
 Can be reprogrammed for new instructions
 Disadvantages
 Slower than hardwired
 Most commonly used for CISC processors
RISC and CISC
In the late 70searly 80s, it was shown that certain instructions are used far more than others:
 45% data movement (move, store, load)
 29% control flow (branch, call, return)
 11% arithmetic (add, sub)
The overhead from using a microprogram memory also became more significant as the rest of the processor became faster. This caused a shift towards RISC computing. Right now, ARM is the largest RISC computing platform. Intel serve more for backwards compatibility with a CISC instruction set. In an modern intel processor, simplest instructions are executed by a RISC core, more complex ones are microprogrammed.
 RISC has simple, standard instructions whereas CISC has lots of more complex instructions
 x86 is often criticised as bloated
 RISC allows for simpler, faster, more streamlined design
 RISC instructions aim to be executed in a single cycle
 CISC puts the focus on the hardware doing as much as possible, whereas RISC makes the software do the work
Multicore Systems
 The performance of a processor can be considered as the rate at which it executes instructions: clock speed x IPC (instructions per clock).
 To increase performance, increase clock speed and/or IPC
 An alternative way of increasing performance is parallel execution
 Multithreading separates the instruction stream into threads that can execute in parallel
 A process is an instance of a program running on a computer
 A process has ownership of resources: the program's virtual address space, i/o devices, other data that defines the process
 The process is scheduled by the OS to divide the execution time of the processor between threads
 The processor switches between processes using the stack
CS141
#notacult
Types & Typeclasses
Haskell is a strongly, statically typed programming language, which helps prevent us from writing bad programs.
 Java, C, Rust  strongly typed
 Python, Ruby  dynamically typed
Types have many benefits:
 Describe the value of an expression
 Prevent us from doing silly things
not 7
givesType Error
 Good for documentation
 Type errors occur at compile time
GHC checks types and infers the type of expressions for us. Types are discarded after type checking, and are not available at runtime.
Type notation
We say an expression has a type by writing expression :: type
, read as "expression has type".
 If we can assign a type to an expression, it is "well typed"
 A type approximates and describes the value of an expression.
42 :: Int
True :: Bool
'c' :: Char
"Cake" :: String
0.5 :: Double
4 + 8 :: Int
2 * 9 + 3 :: Int
True && False :: Bool
"AB" ++ "CD" :: String
even 9 :: Bool
Before writing a definition, it is good practice to write its type.
daysPerWeek :: Int
daysperWeek = 7
Function Types
The types of functions are denoted using arrows >
. The not
function is defined as not :: Bool > Bool
, read "not has type bool to bool". It means if you give me a Bool
, I will give you back another Bool
.
The definition of the not
function is shown below.
not :: Bool > Bool
not True = False
not False = True
not True :: Bool
The last line shows how function application eliminates function types, as by applying a function to a value, one of the types from the function definition is removed as it has already been applied.
The xor
function takes two boolean arguments and is defined:
xor :: Bool > Bool > Bool
xor False True = True
xor False False = False
xor True True = False
xor True False = True
Applying one argument to a function that takes two is called partial function application, as it partially applies arguments to a function to return another function. This is because all functions in haskell are curried, meaning all functions actually only take one argument, and functions taking more than one argument are constructed from applying multiple functions with one argument.
xor :: Bool > Bool > Bool
xor True :: Bool > Bool  partially applied function
xor True False :: Bool
Polymorphic Types
What is the type of \x > x
? Could be:
f :: Int > Int
f :: Bool > Bool
f :: Char > Char
These are all permissible types. To save redifining a function, we can use type variables. Anything with a single lowercase character is a type variable (a
in this case).
\x > x :: a > a
\x > x
is the identity function, as it returns its argument unchanged. We can also have functions with more than one type variable, to specify that arguments have different types:
const :: a > b > a
const x y = x
Tuples
Tuples are a useful data structure
(4, 7) :: (Int, Int)
(4, 7.0) :: (Int, Double)
('a', 9, "Hello") :: (Char, Int, String)
can nest tuples
((4, 'g'), False) :: ((Int, Char), Bool)
can also contain functions
(\x > x, 8.15) :: (a>a, Double)
Functions on pairs. These are all in the standard library
fst :: (a,b) > a
snd :: (a,b) > b
swap :: (a,b) > (b,a)
 these functions can also be defined by pattern matching
fst (x,y) = x
snd (x,y) = y
swap (x,y) = (y,x)
Type Classes
Type classes are used for restricting polymorphism and overloading functions.
 The
(+)
operator probably has type(+) :: Int > Int > Int
, This is correct, as this typing is permissible
 What about
1.2 + 3.4
? Will raise an error with this definition of
(+)
 Will raise an error with this definition of
 Can polymorphism help?
(+) :: a > a > a
 This is stupid
 Allows any types
 Won't work
 A type class constraint is needed
 The actual type is
(+) :: Num a => a > a > a
 The
Num a =>
part is the constraint part  Tells the compiler that
a
has to belong to the typeclassNum
 The
 Type class constraints are used to constrain type variables to only types which support the functions or operators specified by the type class
 Type class names start with an uppercase character
Num
is a type class that represents all types which support arithmetic operations
Defining Type Classes
A type class is defined as follows:
class Num a where
(+) :: a > a > a
() :: a > a > a
abs :: a > a
Num
is the name of the type classa
is the type variable representing it in the method typings The type class contains method signatures for all functions that members of the type class must implement
The type class contains type definitions, but no implementations for the functions. To implement them, we need to tell the compiler which types implement the type class and how they implement the functions in the type class. The Show
typeclass tells the compiler that a type can be converted to a string.
 typeclass definition
class Show a where
show :: a > String
 instance of typeclass for bool type
instance Show Bool where
show True = "True"
show False = "False"
The instance
definition tells the compiler that Bool
is a member of Show
, and how it implements the functions that Show
defines.
Prelude Type Classes
Num
for numbersEq
for equality operators==
/=
Ord
for inequality/comparison operators>
<=
etcShow
for converting things to string Many More
The REPL makes extensive use of Show
to print things. There are no show instances for function types, so you get an error if you try to Show
functions. Typing :i
in the REPL gets info on a type class. :i Num
gives:
class Num a where
(+) :: a > a > a
() :: a > a > a
(*) :: a > a > a
negate :: a > a
abs :: a > a
signum :: a > a
fromInteger :: Integer > a
{# MINIMAL (+), (*), abs, signum, fromInteger, (negate  ()) #}
 Defined in ‘GHC.Num’
instance Num Word  Defined in ‘GHC.Num’
instance Num Integer  Defined in ‘GHC.Num’
instance Num Int  Defined in ‘GHC.Num’
instance Num Float  Defined in ‘GHC.Float’
instance Num Double  Defined in ‘GHC.Float’
Types of Polymorphism
In Java, there are two kinds of polymorphism:
 Parametric polymorphism
 (Generics/Templates)
 A class is generic over certain types
 Can put whatever type you like in there to make a concrete class of that type
 Subtype polymorphism
 Can do
class Duck extends Bird
 Can put
Duck
s whereverBird
s are expected
 Can do
Haskell has two kinds of polymorphism also:
 Parametric polymorphism
 Type variables
id :: a > a
 Can accept any type where
a
is
 Adhoc polymorphism
 Uses type classes
double :: Num a => a > a
double x = x * 2
Further Uses of Constraints
An example Show
instance for pairs:
instance (Show a, Show b) => Show (a,b) Show where
show (x,y) = "(" ++ show x ++ ", " ++ show y ++ ")"
The (Show a, Show b) =>
defines a constraint on a
and b
that they must both be instances of show for them to be used with this instance. The instance is actually defined on the type (a,b)
.
Can also define that a typeclass has a superclass, meaning that for a type to be an instance of a typeclass, it must be an instance of some other typeclass first. The Ord
typeclass has a superclass constraint of the Eq
typeclass, meaning something cant be Ord
without it first being Eq
. This makes sense, as you can't have an ordering without first some notion of equality.
class Eq a => Ord a where
(<) :: a > a > Bool
(<=) :: a > a > Bool
Default Implementations
Type classes can provide default method implementations. For example, (<=)
can be defined using the definition of (<)
, so a default one can be provided using (==)
class Eq a => Ord a where
(<) :: a > a > Bool
(<=) :: a > a > Bool
(<=) x y = x < y  x == y
 or defined infix
x <= y = x < y  x == y
Derivable Type Classes
Writing type class instances can be tedious. Can use the deriving
keyword to automatically generate them, which does the same as manually defining type class instances.
data Bool = False  True
deriving Eq
data Module = CS141  CS118  CS126
deriving (Eq, Ord, Show)
Certain other typeclasses can be dervied too, by enabling language extensions within GHC. The extension XDeriveFunctor
allows for types to include a deriving Functor
statement.
Data Types
How do we make our own data types in haskell? Algebraic data types.
Bool
is a type There are two values of type
Bool
True
False
data Bool = True  False
A type definition consists of the type name Bool
and it's data constructors, or values True  False
. A type definition introduces data constructors into scope, which are just functions.
True :: Bool
False :: Bool
We can pattern match on data constructors, and also use them as values. This is true for all types.
not :: Bool > Bool
not True = False
not False = True
More examples:
data Module = CS141  CS256  CS263
data Language = PHP  Java  Haskell  CPP
for this one, the type name and constructor name are separate names in the namespace
data Unit = Unit
 this one has no values
data Void
Parametrised Data Constructors
Parameters can be added to a data constructor by adding their types after the constructor's name. The example below defines a type to represent shapes. Remember that data constructors are just functions, and can be partially applied just like other functions.
data Shape = Rect Double Double  Circle Double
Rect :: Double > Double > Shape
Circle :: Double > Shape
 functions utilising the Shape type
 constructs a square
square x :: Double > Shape
square x = Rect x x
 calculates area of a shape using pattern matching on constructors
area :: Shape > Double
area (Rect w h) = w * h
area (Circle r) = pi * r * r
isLine :: Shape > Bool#
isLine (Rect 1 h) = True
isLine (Rect w 1) = True
isLine _ = False
 examples
area (square 4.0)
=> area (Rect 4.0 4.0)
=> 4.0 * 4.0
=> 16.0
area (Circle 5.0)
=> pi * 5.0 * 5.0
=> pi * 25.0
=> 78.53981...
Parametrised Data Types
The Maybe
type is an example of a data type parametrised over some type variable a
. It exists within the standard library, defined as data Maybe a = Nothing  Just a
. This type is used to show that either there is no result, or some type a
.
A function using the Maybe
type to perform devision safely, returning Nothing
if the divisor is 0, and the result wrapped in a Just
if the division can be done.
data Maybe a = Nothing  Just a
safediv :: Int > Int > Maybe Int
safediv x 0 = Nothing
safediv x y = Just (x `div y)
 safediv 8 0 => Nothing
 safediv 8 4 = Just (8 `div` 4) = Just 2
 this is included in stdlib for extracting the value using pattern matching
fromMaybe :: a > Maybe a > a
fromMaybe x Nothing = x
fromMaybe _ (Just x) = x
Null references were invented in the 1960s ... the guy who invented them called them his "billion dollar mistake". The Maybe
type is a good alternative, which makes it clear that a value may be absent. Similar concepts exist in other procedural languages (Swift, Rust)
Recursive Data Types
In Haskell, data types can be defined in terms of themselves. An example definition of the natural numbers is shown below, where a number is either zero, or one plus another number.
data Nat = Zero  Succ Nat
Zero :: Nat
Succ :: Nat > Nat
one = Succ Zero
two = Succ one
three = Succ two
add :: Nat > Nat > Nat
add Zero m = m
add (Succ n) m = Succ (add n m)
mul :: Nat > Nat > Nat
mul Zero m = Zero
mul (Succ n) m = add m (mul n m)
Another example defining binary trees in terms of themselves. A binary tree consists of subtrees (smaller binary trees). This type is parametrised over some type variable a
also.
Data BinTree a = Leaf a  Node (BinTree a) (BinTree a)
converts a binary tree to a list
flatten :: BinTree a > [a]
flatten (Leaf x) = [x]
flatten (Node l r) = flatten l ++ flatten r
 computes the max depth of the tree
depth :: BinTree a > Int
depth (Leaf _) = 1
depth (Node l r) = 1 + max (depth l) (depth r)
Type Aliases
Types can be aliased. For example, String
has been an alias of [Char]
all along.
type String = [Char]
Another example, defining a Predicate
type
type Predicate a = a > Bool
isEven :: Predicate Int
isEven n = n `mod` 2 == 0
isEven' :: (Eq a, Integral a) => Predicate a
isEven' n = n `mod` 2 == 0
Recursion
Recursion is a way of expressing loops with no mutable state, by defining a function in terms of itself. The classic example, the factorial function. Defined mathematically:
$n!={1n×(n−1)! ifn=0otherwise $
In haskell:
factorial :: Int > Int
factorial 0 = 1
factorial n = n * factorial (n1)
It can be seen how this function reduced when applied to a value:
factorial 2
=> 2 * factorial (21)
=> 2 * factorial 1
=> 2 * 1 * factorial (11)
=> 2 * 1 * factorial 0
=> 2 * 1 * 1
=> 2
Another classic example, the fibonacci function:
fib :: Int > Int
fib 0 = 1
fib 1 = 1
fib n = fib (n1) + fib (n1)
In imperative languages, functions push frames onto the call stack every time a function is called. With no mutable state, this is not required so recursion is efficient and can be infinite.
Haskell automatically optimises recursive functions to make execution more efficient:
fac' :: Int > Int > Int
fac' 0 m = m
fac' n m = fac' (n1) (n*m)
This version of the function prevents haskell from building up large expressions:
fac 500
=> fac' 500 1
=> fac' (5001) (500*1)
=> fac' 499 500
=> fac (4991) (499 * 500)
=> fac' 498 249500
Notice the pattern for all recursive functions, where there is a recursive case, defining the function in terms of itself, and a base case. Without a base case, the function would recurse infinitely. The cases are usually defined as pattern matches.
Recursion on Lists
Recursion is the natural way to operate on lists in haskell. Defining the product function, which returns the product of all the items in the list:
product :: [Int] > Int
product [] = 1
product (n:ns) = n * product ns
Here, the base case is the empty list []
and pattern match is used to "decons" the head off the list and operate on it (n:ns)
. The function reduces as follows:
product [1,2,3,4]
=> 1 * product [2,3,4]
=> 1 * 2 * product [3,4]
=> 1 * 2 * 3 * product [4]
=> 1 * 2 * 3 * 4 * product []
=> 1 * 2 * 3 * 4 * 1
=> 24
let
and where
let
and where
clauses can be used to introduct local bindings within a function, which are useful in defining recursive functions. the splitAt
function, which splits a list into two at a certain index.
splitAt :: Int > [a] > ([a],[a])
splitAt 0 xs = ([],xs)
splitAt n [] = ([],[])
splitAt n (x:xs) = (x:ys, zs)
where (ys,zs) = splitAt (n1) xs
 alternatively
splitAt n xs =
let
ys = take n xs
zs = drop n xs
in (ys,zs)
let
and where
can also define functions locally, as everything in haskell is a function.
Higher Order Functions
Higher order functions are functions which operate on functions.
Associativity of functions
Function expressions associate to the right (one argument is applied at a time)
xor a b = (a  b ) && not (a && b)
 equivalent to
xor = \a > \b > (a  b) && not (a && b)
 equivalent to
xor = \a > (\b > (a  b) && not (a && b))
 All functions in haskell are technically nameless, singleparameter functions
 Currying allows for functions which return other functions
 Functions are expressions
 The body of a function is an expression
 When a function is applied to an argument it reduces to it's body.
Function application associates to the left:
xor True True
=> (xor True) True
=> ((\a > (\b > (a  b) && not (a && b))) True) True
=> (\b > (True  b) && not (True && b)) True
=> (True  True) && not (True && True)
Function types, however, associate to the right:
xor :: Bool > Bool > Bool
xor = \a > \b > (a  b) && not (a && b)
equivalent to
xor :: Bool > (Bool > Bool)
xor = xor = \a > (\b > (a  b) && not (a && b))
The table below shows how functions application and types associate:
Without Parentheses  With Parentheses 

f x y  (f x) y 
\x > \y > ...  \x > (\y > ...) 
Int > Int > Int  Int > (Int > Int) 
Functions as Arguments (map
)
Haskell functions can be taken as arguments to other functions. Functions that take/return functions are called higher order functions. An example, increasing every element of a list by one:
incByOne :: [Int] > [Int]
incByOne xs = [x+1  x < xs]
 or using recursion
incByOne [] = []
incByOne (x:xs) = x+1 : incByOne xs
All this function does is applies the function (+ 1)
to every element. This pattern can be generalised using the map function
: a function that applies a function given as an argument to every element of a list:
map :: (a > b) > [a] > [b]
map f [] = []
map f (x:xs) = f x : map f xs
Note the type signature of the map function is map :: (a > b) > [a] > [b]
, meaning the first argument is a function of type (a > b)
. Using this to implement incByOne
:
incByOne = map (+1)
 tracing it's evaluation:
incByOne [1,2,3]
=> map (+1) [1,2,3]
=> (1+1) : map (+1) [2,3]
=> (1+1) : (1+2) : map (+1) [3]
=> (1+1) : (1+2) : (1+3) : map (+1) []
=> (1+1) : (1+2) : (1+3) : []
=> [2,3,4]
Effectively, map f [x, y, z]
evaluates to [f x, f y, f z]
Sections
Sections are partially applied operators. Operators are functions like any other, and as such can be partially applied, passed as arguments, etc. The addition operator is shown as an example, but the same applies to any binary operator.
(+) :: Num a => a > a > a
(+ 4) :: Num a => a > a
(4 +) :: Num a => a > a
(+) 4 8 = 4 + 8
(+ 4) 8 = 8 + 4
(4 +) 8 = 4 + 8
Filter
Filter is an example of another higher order function, which given a list, returns a new list which contains only the elements satisfying a given predicate.
filter :: (a > Bool) > [a] > [a]
filter p [] = []
filter p (x:xs)
 p x = x : filter p xs
 otherwise = filter p xs
Some examples:
 remove all numbers less than or equal to 42
greaterThan42 :: (Int > Bool) > [Int] > [Int]
greaterThan42 xs = filter (>42) xs
 only keep uppercase letters
uppers :: (Char > Bool) > String > String
uppers xs = filter isUpper xs
Curried vs Uncurried
Tuples can be used to define uncurried functions. A function that takes two arguments can be converted to a function that takes an a tuple of two arguments, and returns a single argument/
uncurriedAdd :: (Int, Int) > Int
uncurriedAdd (x, y) = x + y
There are higherorder functions, curry
and uncurry
, which will do this for us:
curry :: ((a,b) > c) > a > b > c
curry f x y = f (x,y)
uncurry :: (a > b > c) > (a,b) > c
uncurry f (x,y) = f x y
 examples
uncurriedAdd :: (Int, Int) > Int
uncurriedAdd = uncurry (+)
curriedAdd :: Int > Int > Int
curriedAdd = curry uncurriedAdd
addPairs :: [Int]
addPairs = map (uncurry (+)) [(1, 2), (3, 4)]
Folds
foldr
and foldl
"collapse" a list by applying a function f
to each element in the list in turn, where the first argument is an accumulated value, and the second is the starting value passed. There are several functions which follow this pattern, all reducing a list to a single value using recursion:
 and together all bools in the list
and :: [Bool] > Bool
and [] = True
and (b:bs) = ((&&) b) (and bs)
 product of everything in the list
product :: Num a => [a] > a
product [] = 1
product (n:ns) = ((*) n) (product ns)
 length of list
length :: [a] > Int
length [] = 0
length (x:xs) = ((+) 1) (length xs)
All of these functions have a similar structure, and can be redefined using foldr
:
foldr :: (a > b > b) > b > [a] > b
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
 examples
and :: [Bool] > Bool
and = foldr (&&) True
product :: Num a => [a] > a
product = foldr (*) 1
length :: [a] > Int
length = foldr (\x n > n + 1) 0
In essence, foldr f z [1, 2, 3]
is equal to f 1 (f 2 (f 3 z))
. foldr
folds from right (r
) to left, starting by applying the function to the last element of the list first. foldl
, however, works in the opposite direction:
foldl :: (b > a > b) > b > [a] > b
foldl f z [] = z
foldl f z (x:xs) = foldl f (f z x) xs
foldl f z [1, 2, 3]
is equal to f (f (f z 1) 2) 3
. For some functions (commutative ones), there is no difference, but often the choice of which to use is important.
Function Composition
In haskell, functions are composed with the (.)
operator, a higher order function defined as:
(.) :: (b > c) > (a > b) > a > c
(.) f g x = f (g x)
Function composition is used to chain functions, so instead of f (g (h x))
, you can write f.g.h x
. An example, defining a function count
to count the number of occurrences of an element in a list:
count :: Eq a => a => [a] > Int
count _ [] = 0
count y (x:xs)
 y == x = 1 + count y xs
 otherwise = count y xs
alternatively, using a fold
count y = foldr (\x l > if y==x then 1+l else l) 0
 the stdlib can do this
count y x = length (filter (==y) xs)
count y = length . filter (==y)  using composition
Lazy Evaluation
Evaluation Strategies
How are programs evaluated? There are a number of strategies for evaluating a program. For example, the expression (4+8) * (15 + 16)
can be evaluated in different ways:
(4+8) * (15 + 16)
=> 12 * (15+16)
=> 12 * 31
=> 372
 or
(4+8) * (15 + 16)
=> (4 + 8) * 31
=> 12 * 31
=> 372
The final value when reducing an expression (it cannot be reduced further) is the normal form, 372 in this case. No matter how the expression is reduced, the normal form is the same. Haskell's type system prevents us from writing anything that cannot reduce to normal form.
A subexpression (anything partially reduced that can still be reduced further) is called a redex, short for reducible expression. Evaluation strategies only matter when there are multiple redexes, otherwise there is only one route we can take to evaluate an expression.
Strict Evaluation
A programming language is strict if the arguments of the function are evaluated before the function is called.
Evaluating fac 500
using a strict method:
fac :: Int > Int
fac n = fac' n 1
fac' :: Int > Int > Int
fac n m = case n of
0 > m
_ > fac' (n1) (n*m)
fac 500  a redex, function application
=> fac' 500 1  another redex
=> fac' (5001) (500*1)  3 redexes, two multiplications and function application
=> fac' 499 (500*1)  two redexes now as 5001=499 is now in normal form
=> fac' 499 500  now only one redex
=> fac' (4991) (499*500)  back to 3 redexes
...  this goes on for a while
Callbyvalue means that all function arguments are reduced to their normal forms (values), and then passed as such to the function. The callbyvalue strategy is an example of strict evaluation. This is the evaluation strategy used by most programming languages: Java, JS, PHP, C/C++, OCaml, F#, Python, Scala, Swift. Note that some of these are also functional languages.
Haskell, on the other hand, is far superior. It is nonstrict: aka lazy.
Callbyname
A nonstrict evaluation strategy by which expressions given to functions as arguments are not reduced before the function call is made.
Expressions are only reduced when their value is needed. Same example as before:
fac 2
=> fac' 2 1  still a redex here
=> case 2 of
0 > 1
_ > fac' (21) (2*1)  the function call is expanded to its expression
=> fac' (21) (2*1)  left with 3 redexes now
=> case 21 of
0 > 2*1
_ > fac' ((21)1) ((21) * (2*1))  a lot of redexes, but we don't need to know the value of any except the one in the case expression. this one is evaluated but not the others
=> case 1 of
0 > 2*1
_ > fac' ((21)1) ((21) * (2*1))  something actually got evaluated, as we needed it's value. we still have a lot of redexes though
Note how that the same argument ((21)
) is there 3 times, but it is only evaluated when it is needed. This means that it is evaluated possibly more than once, as it may be needed more than once at different points. With callbyvalue (strict), an expression is only reduced once but will only ever be reduced once, but with callbyname (lazy), expressions may end up being evaluated more than once.
Sharing
Sharing avoids duplicate evaluation. Arguments to functions are turned into local definitions, so that when an expression is evaluated, any expressions that are identical are also evaluated. The same example again, using both callbyname and sharing:
fac' :: Int > Int > Int
fac' n m = case n of
0 > m
_ > let x = n1
y = n*m
in fac' x y
 the compiler has replaced the expression arguments with letbound definitions
fac 2
=> fac' 2 1
=> case 2 of
0 > 1
_ > let x0 = 21
y0 = 2*1
in fac' x0 y0 expressions bound to variables
=> let x0 = 21
y0 = 2*1  two redexes
in fac' x0 y0
=> let x0 = 21
y0 = 2*1
in case x0 of
0 > y0
_ > let x1 = x01
y1 = x0 * y0
in fac' x1 y1  even more redexes and bindings
 x0 can be replaced by 1, which evaluates the expresion in all places where x0 is used
Can think of let or where bindings as storing expressions in memory in such a way that we can refer to them from elsewhere using their names.
The combination of callbyname and sharing is known as lazy evaluation, which is the strategy haskell uses. Nothing is evaluated until it is needed, and work is only ever done once. (Strict evaluation is done sometimes if the compiler decides to, so it is technically nonstrict instead of lazy.)
Evaluation in Haskell
An example, using haskell's lazy evaluation strategy:
length (take 2 (map even [1,2,3,4]))
=> length (take 2 (even 1 : map even [2,3,4]))  check argument is nonempty list
=> length (even 1 : take (21) (map even [2,3,4]))  even 1 cons'd to take 1 of map
=> 1 + length (take (21) (map even [2,3,4])) know length is at least 1, take out
=> 1 + length(take 1 (map even [2,3,4]))
=> 1 + length (take 1 (even 2 : map even [3,4])) another map call
=> 1 + (1 + length (take (11) (map even [3,4]))  length again
=> 1 + (1 + length []) take 0 so empty list
=> 1 + 1 + 0  return 0
=> 2  done
Note how half the map wasn't evaluated, because haskell knew we only cared about the first 2 elements. However this trace doesn't show any of the internal bindings haskell makes for sharing expressions. The compiler does this by transforming the expression:
length (take 2 (map even [1,2,3,4]))
 becomes
let
xs = take 2 (map even [1,2,3,4])
in length xs
 becomes
let
ys = map even [1,2,3,4]
xs = take 2 ys
in length xs
 becomes
let
ys = map even (1:(2:(3:(4:[]))))
xs = take 2 ys
in length xs
 finally
let
zs4 = 4:[]
zs3 = 3:zs4
zs2 = 2:zs3
zs = 1:zs2
ys = map even zs
xs = take 2 ys
in length xs
In this representation, everything is let bound it it's own definition, and nothing is applied except to some literal or to another let bound variable. The representation in memory looks something like this:
These things in memory are called closures. A closure is an object in memory that contains:
 A pointer to some code that implements the function it represents (not shown)
 A pointer to all the free variables that are in scope for that definition
 A free variable is any variable in scope that is not a parameter
The closures form a graph, where the closures all point to each other.
Another example, using map
:
map :: (a > b) > [a] > [b]
map _ [] = []
map f (x:xs) = f x : map f xs
 removing all syntactic sugar, done by compiler
map = \f > \arg >
case arg of
[] > []
(x: xs) > let
y = f x
ys = map f xs
in (y:ys)
Using this definition of map
to evaluate the expression from before (length (take 2 (map even [1,2,3,4]))
):
let
zs4 = 4:[]
zs3 = 3:zs4
zs2 = 2:zs3
zs = 1:zs2
xs = map even zs
ys = take 2 xs
in length ys
 new closures allocated by map, using 2nd case of map function
let
zs4 = 4:[]
zs3 = 3:zs4
zs2 = 2:zs3
zs = 1:zs2
y0 = even 1
ys0 = map even zs2  new closures
xs = y0 : ys  updated to be a cons cell
ys = take 2 xs
in length ys
The graph of closures representing this:
Strictness in Haskell
Things can be evaluated strictly in haskell, if you want. This is prefereable in some cases for performance reasons. The \$!
operator forces strict function application. The version of the function below forces the recursive call to be evaluated first.
fac' :: Int > Int > Int
fac' 0 m = m
fac' n m = (fac' \$! (n1)) (n*m)
Infinite Data Structures
Laziness means data structures can be infinite in haskell. This is also facilitated by the lack of call stack, as there is no "max recursion depth" like in strict languages.
from :: Int > [Int]
from n = n : from (n+1)
This function builds an infinite list of a sequence of Int
s, starting with the Int
passed. An example usage, showing how lazy evaluation works with it:
take 3 (from 4)
=> take 3 (4 : from 5)
=> 4 : take 2 (from 5)
=> 4 : take 2 (5 : from 6)
=> 4 : 5 : take 1 (from 6)
=> 4 : 5 : take 1 (6 : from 7)
=> 4 : 5 : 6 : take 0 (from 7)
=> 4 : 5 : 6 : []
=> [4,5,6]
The infinite evaluation is shortcircuited, as the compiler knows it only needs the first 3 elements.
Reasoning About Programs
Haskell can use normal software testing methods to verify correctness, but because haskell is a pure language, we can do better and formally prove properties of our functions and types.
Natural Numbers
Natural numbers can be defined as data Nat = Z  S Nat
in haskell. Alternatively, using mathematical notation, this can be written $0∈N∀n∈N,n+1∈N$. Addition can then be defined recursively:
add :: Nat > Nat > Nat
add Z m = m
add (S n) m = S (add n m)
Addition has certain properties which must hold true:
 Left identity:
∀m :: Nat, add Z m == m
 $0+m=m$
 Right identity:
∀m :: Nat, add m Z == m
 $m+0=m$
 Associativity:
∀x y z :: Nat, add x (add y z) == add (add x y) z
 $x+(y+z)=(x+y)+z$
These can be proven using equational reasoning, which proves that an equality holds in all cases. Generally, either a property can be proved by applying and unapplying either side of an equation, and/or by induction.
To prove the left identity is easy, as it is an exact match of one of our equations for add
:
add Z m
 applying add
= m
The right identity is a little harder, as we can't just directly apply one of our equations. We can instead induct on m
. First, the base case:
add Z Z
 applying add
= Z
Using the induction hypothesis add m Z = m
, we need to show the inductive step holds for S m
(m+1
):
add (S m) Z
 applying add
= S (add m Z)
 applying induction hypothesis
= S m
This proves the right identity. To prove associativity we will again use induction, this time on x
. The base case is add Z (add y z)
:
add Z (add y z)
 applying add
= add y z
 unapplying add
= add (add Z y) z
The proof holds for x = Z
. Here, the proof was approached from either end to meet in the middle, but written as a single list of operations for clarity. Sometimes it is easier to do this and work from either direction, especially when unapplying functions as it is more natural.
The induction hypothesis is add x (add y z) == add (add x y) z
, and can be assumed. We need to prove the inductive step add (S x) (add y z) == add (add (S x) y) z
:
add (S x) (add y z)
 applying add
= S (add x (add y z))
 applying induction hypothesis
= S (add (add x y ) z)
 unapplying add
= add (S (add x y)) z
 unapplying add
= add (add (S x) y) z
This proves associativity.
Induction on Lists
We can induct on any recursive type, including lists: data List a = Empty  Cons a (List a)
. Using this definition, we can prove map fusion. Map fusion states that we can turn multiple consecutive map operations into a single one with composed functions:
map f (map g xs) = map (f.g) xs
∀f :: b > c
∀g :: a > b
∀xs :: [a]
The definitions of map
and .
may be useful:
map :: (a > b) > [a] > [b]
map f [] = []
map f (x:xs) = f x : map f xs
(.) :: (b > c) > (a > b) > a > c
(.) f g x = f (g x)
Map fusion can be proved by induction on xs. The base case is map f (map g []) = map (f.g) []
:
map f (map g [])
 applying map
= map f []
 applying map
= []
 unapplying map
= map (f.g) []
Using the induction hypothesis map f (map g xs) = map (f.g) xs
, we can prove the inductive case map f (map g (x : xs)) = map (f.g) (x : xs)
:
map f (map g (x : xs))
 applying map
= map f (g x : map g xs)
 applying map
= f (g x) : map f (map g xs)
 induction hypothesis
= f (g x) : map (f.g) xs
 unapplying (.)
= (f.g) x : map (f.g) xs
 unapplying map
= map (f.g) (x : xs)
Proving a Compiler
Given a simple expression language:
data Expr = Val Int  Plus Expr Expr
And a simple instruction set:
data Instr = Push Int  Add
type Program = [Instr]
type Stack = [Int]
We can write an exec
function as an interpreter for our instruction set:
exec :: Program > Stack > Stack
exec [] s = s
exec (Push n : p) s = exec p (n : s)
exec (Add : p) (y : x : s) = exec p (x + y : s)
An eval
function to evaluate our expressions:
eval :: Expr > Int
eval (Val n) = n
eval (Plus l r) = eval l + eval r
And a comp
function as a compiler for our Expr
language to our Instr
instruction set:
comp :: Expr > Program
comp (Val n) = [PUSH n]
comp (Plus l r) = comp l ++ comp r ++ [ADD]
Our compiler will be considered correct if for any expression, evaluating it yields the same result as compiling and then executing it:
∀ e :: Expr, s :: Stack . eval e : s == exec (comp e) s
This can be proved by induction on e
. The base case for Expr
is for Val
s, and we want to show that eval (Val n) s == exec (comp (Val n)) s
. This time, we start with the RHS:
exec (comp (Val n)) s
 applying comp
= exec [Push n] s
 applying exec
= exec [] (n : s)
 applying exec
= (n : s)
 unappplying eval
= eval (Val n) s
Our inductive case to be proved is eval (Plus l r) s == exec (comp (Plus l r)) s
. Since the Plus
constructor has two values of type Expr
, there are two induction hypotheses:
 for
l
:eval l : s == exec (comp l) s
 for
r
:eval r : s == exec (comp r) s
exec (comp (Plus l r)) s
 applying comp
= exec (comp l ++ comp r ++ [Add]) s
 distributivity of (++)
= exec (comp l ++ (comp r ++ [Add])) s
 distributivity lemma
= exec (comp r ++ [Add]) (exec (comp l) s)
 distributivity lemma
= exec [Add] (exec (comp r) (exec (comp l) s))
 induction hypothesis
= exec [Add] (exec (comp r) (eval l : s))
 induction hypothesis
= exec [Add] (eval r : (eval l : s))
 applying exec
= exec [] ((eval l + eval r) : s)
 applying exec
= (eval l + eval r) : s
 unapplying exec
= eval (Plus l r) s
The proof holds, but relies on a lemma proving the distributivity of the exec function, which states that executing a program where a list of instructions xs
is followed by a list of instructions ys
is the same as first executing xs
and then executing ys
with the stack that results from executing xs
: ∀ xs ys::Program, s::Stack . exec (xs++ys) s == exec ys (exec xs s)
.
This can be proved by induction on xs
. The base case is the empty list []
: exec ([] ++ ys) s == exec ys (exec [] s)
:
exec ys (exec [] s)
 applying exec
= exec ys s
 unapplying (++)
= exec ([] ++ ys) s
The induction hypothesis is exec (xs++ys) s == exec ys (exec xs s)
. The inductive step is exec ((x : xs) ++ ys) s == exec ys (exec (x : xs) s)
. As x
could be either Push x
or Add
, we perform case analysis on x
, first with the case where x = Push n
:
exec ys (exec (Push n : xs) s)
 applying exec
= exec ys (exec xs (n : ns))
 induction hypothesis
= exec (xs ++ ys) (n : s)
 unapplying exec
= exec (Push n : (xs ++ ys)) s
 unapplying (++)
= exec ((Push n : xs) ++ ys) s
The inductive step holds for the Push n
case. The Add
case:
exec ys (exec (Add : xs) s)
 assuming stack has at least 2 elements
exec ys (exec (Add : xs) (b : a : s'))
 applying exec
exec ys (exec xs (a + b : s'))
 induction hypothesis
exec (xs ++ ys) (a + b : s')
 unapplying exec
exec (Add : (xs ++ ys)) (b : a : s')
 unapplying (++)
exec ((Add : xs) ++ ys) (b : a : s')
 assumption
exec ((Add : xs) ++ ys) s
This proves the inductive case for the Add
instruction, and therefore the proof for the distributivity of exec
lemma, which supported our initial proof of the correctness of our compiler.
Functors & Foldables
The \$
Operator
The \$
operator is an operator for function application. It has signature:
(\$) :: (a > b) > a > b
f \$ x = f x
At first it doesn't look like it does much, but it is actually defined as infixr 0
meaning it is:
 An infix operator with right associativity
 Has the lowest precedence possible.
In contrast, normal function application is left associative and has the highest precedence possible. Practically, this means it can be used where you would otherwise have to use parentheses, to make code a lot cleaner. Some examples:
 elem finds if an item x is contained in the list xs
elem :: Eq a => a > [a] > Bool
elem x xs = not (null (filter (==x) xs))
 rewritten, without parentheses
elem x xs = not \$ null \$ filter (==x) xs
 or using function composition (.)
elem x = not . null . filter (==x)
Another example, shown along with a trace of it's reduction:
map (\$ 4) [even, odd]
=> (even $ 4) : map (\$ 4) [odd]
=> (even \$ 4) : (odd \$ 4) : []
=> True : (odd \$ 4) : []
=> True : False : []
=> [True, False]
Foldables
It has already been shown how many examples of recursive functions can be rewritten with a fold
. fold
ing is a an example of a useful design pattern in functional programming.
A Trip to Michael's Tree Nursery
Binary trees are recursive data structures, that can be recursively operated on (much like lists). The example below shows a simple definition of a binary tree along with some functions to operate on it.
 our binary tree type
data BinTree a = Leaf  Node (BinTree a) a (BinTree a)
deriving Show
 simple recursive functions
 how big is the tree?
size :: BinTree a > Int
size Leaf = 0
size Node (l _ r) = 1 + size l + size r
 is x contained within the tree?
member:: Eq a => a > BinTree a > Bool
member _ Leaf = False
member x (Node l y r) = x == y  member x l  member x r
 what is the sum of all the Nums in the tree
tsum :: Num a => BinTree a > a
tsum Leaf =0
tsum (Node l n r) = n + tsum l + tsum r
These are all recursive functions operating on a tree, and can be generalised by defining our own version of a fold for trees, dubbed toldr
. Note the similarities between foldr
and toldr
.
toldr :: (a > b > b) > b > BinTree a > b
toldr f z Leaf = z
toldr f z (Node l x r) = f x (toldr f (toldr f z r) l)
tsum :: Num a => BinTree a > a
tsum = toldr (+) 0
member :: Eq a => a > BinTree a > Bool
member x = toldr (\y r > x==y  r) False
size :: BinTree a > Int
size = toldr(\_ r > 1 + r) 0
The Foldable
Typeclass
This abstraction does actually exist in the standard libary, as a typeclass. A type can be an instance of Foldable
(like lists), which then allows foldr
to be used on it.
class Foldable t where
foldr :: (a > b > b) > b > t a > b
 for lists
 exists in prelude
instance Foldable [] where
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
 for our bintree
instance Foldable BinTree where
foldr _ z Leaf = z
foldr f z (Node l x r) = f x (foldr f (foldr f z r) l)
This instance of Foldable
for BinTree
can now be used to generalise our functions that operate on it:
sum :: (Foldable t, Num a) => t a > t
sum = foldr (+) 0
elem :: (Foldable t, Eq a) => a > t a > Bool
elem x = foldr (\y r > x==y  r) False
length :: Foldable t => t a > Int
length = foldr (\_ r > 1 + r) 0
These methods are actually part of the Foldable
typeclass, so when defining an instance of Foldable
on some type, you get them for free, and they are polymorphic over all foldable types.
Foldable
is also a derivable typeclass using the language extension XDeriveFoldable
, so all of this can be derived automatically.
Functors
Bringing back our safediv
function from previously:
data Maybe a = Nothing  Just a
safediv :: Int > Int > Maybe Int
safediv _ 0 = Nothing
safediv x y = Just (x `div` y)
divAndAdd :: Int > Int > Maybe Int
divAndAdd x y = 5 + safediv x y  doesn't work, type error
 using a case statement
divAndAdd x y = case safediv x y of
Nothing > Nothing
Just r > Just (5+r)
 bit messy
The pattern of applying a function a value within a Maybe
can be generalise. Defining a function pam
to do this for us:
pam :: (a > b) > Maybe a > Maybe b
pam _ Nothing = Nothing
pam f (Just x) = Just (f x)
 much nicer!
divAndAdd :: Int > Int > Maybe Int
divAndAdd x y = pam (5+) (safediv x y)
It would be nice if there was some way to generalise the pattern of applying a function to element(s) in a container. The Functor
typeclass does this for us. A type is a functor if we can apply a function to it. Lists are functors, as that is what the map
function does. Maybe
and BinTree
s are also functors.
class Functor f where
fmap :: (a > b) > f a > f b
instance Functor [] where
fmap = map
instance Functor Maybe where
fmap f Nothing = Nothing
fmap f (Just x) = Just (f x)
instance Functor BinTree where
fmap f (Leaf x) = Leaf (f x)
fmap f (Node lr ) = Node (fmap f l) (fmap f r)
Functors can be thought of as "boxes", and when given a function, will apply it to the value in the box, and return the result in the same box. Some examples of definitions using functors:
 increases all Ints in the "box" by 5
incByFive :: Functor f => f Int > f Int
incByFive = fmap (+5)
 applies the odd function to all Ints in the box
odds :: Functor f => f Int > f Bool
odds = fmap odd
 redefining using fmap
divAndAdd :: Functor f => Int > Int > Maybe Int
divAndAdd x y = fmap (5+) (safediv x y)
Functor is also another typeclass that can be derived by GHC, using the XDeriveFunctor
extension.
The <\$>
Operator
An operator that is essentially just an infix version of the fmap
function.
infixl 4 <\$>
(<\$>) :: Functor f => (a > b) > f a > f b
(<\$>) = fmap
fmap (replicate 6) (safediv 8 4)
== replicate 6 <\$> safediv 8 4
=> Just [2,2,2,2,2,2]
 redefining using <\$>
divAndAdd :: Functor f => Int > Int > Maybe Int
divAndAdd x y = (5+) <\$> (safediv x y)
Functor Laws
There are certain laws that functors must obey for their properties to hold. A type f
is a functor if there exists a function fmap :: (a> b) > f a > f b
, and the following laws hold for it:
fmap id = id
 If the values in the functor are mapped to themselves, the result will be an unmodified functor
fmap (f.g) = (fmap f) . (fmap g)
 The fusion law
 If two
fmap
s are applied one after the other, the result must be the same as a singlefmap
which applies the two functions in turn
 These laws imply that a data structure's "shape" does not change when
fmap
ped
Applicative Functors
Kinds
 For the compiler to accept a program, it must be well typed
 Kinds are the "types of types"
 Types are denoted with
expression :: type
 eg
True :: Bool
 eg
 Kinds are denoted the same:
type :: kind
Bool :: *
 The compiler infers kinds of types the same way it infers types of expressions
*
is the kind of typesBool :: *
becauseBool
has no type parametersdata Bool = True  False
Maybe
is parametrised over some typea
, so the kind signatureMaybe :: * > *
means that if given a type as an argument to the type constructorJust
, it will give back some other type of kind*
[] :: * > *
[]
is the type constructor for lists
Kinds are important when defining typeclasses. Take Functor
, for example:
class Functor f where
fmap :: (a > b) > f a> f b
This definition shows that the type f
is applied to one argument (f a
), so f :: * > *
 Maybe :: * > *
instance Functor Maybe where
fmap f Nothing = Nothing
fmap f (Just x) = Just (f x)
 invalid
 Maybe a :: *
 As the type is already applied to a
instance Functor (Maybe a) where
fmap f Nothing = Nothing
fmap f (Just x) = Just (f x)
The Either
Type
Either is usually used to represent the result of a computation when it could give one of two results. Right
is used to represent success, and a
is the wanted value. Left
is used to represent error, with e
as some error code/message.
data Either e a = Left e  Right a
Left :: e > Either e a
Right :: a > Either e a
Either
has kind * > * > *
, as it must be applied to two types e
and a
before we get some other type.
Only types of kind * > *
can be functors, so we need to apply Either
to one argument first. The functor instance for Either
applies the function to the Right
value.
instance Functor (Either e) where
fmap :: (a > b) > Either e a > Either e b
fmap f (Left x) = Left x
fmap f (Right y) = Right (f y)
The Unit Type ()
()
is called the unit type() :: ()
()
, the unit value, has type()
()
is the only value of type()
 Can be thought of as defined
data () = ()
 Or an empty tuple
Semigroups and Monoids
A type is a semigroup if it has some associative binary operation defined on it. This operator (<>)
is the "combine" operator.
class Semigroup a where
(<>) :: a > a > a
instance Semigroup [a] where
 (<>) :: [a] > [a] > [a]
(<>) = (++)
instance Semigroup Int where
 (<>) :: Int > Int > Int
(<>) = (+)
A type is a monoid if it is a semigroup that also has some identity value, called mempty
:
class Semigroup a => Monoid a where
mempty ::a
instance Monoid [a] where
 mempty :: [a]
mempty = []
instance Monoid Int where
 mempty :: Int
mempty = 0
Applicatives
Applicative Functors are similar to normal functors, except with a slightly different type definition:
class Functor f => Applicative f where
pure :: a > f a
<*> :: f (a > b) > f a > f b
The typeclass defines two functions:
pure
just lifts the valuea
into the "box"<*>
(the apply operator) takes some function (a > b
) in a boxf
, and applies it to a valuea
in a box, returning the result in the same box. "box" is a rather loose analogy. It is more accurate to say "computational context".
Different contexts for function application:
 vanilla function application
(\$) :: (a > b) > a > b
 Functor's fmap
(<\$>) :: Functor f => (a > b) > f a > f b
 Applicative's apply
(<*>) :: Applicative f => f (a > b) > f a > f b
Maybe
and Either e
are both applicative functors:
instance Applicative Maybe where
pure x = Just x
Nothing <*> _ = Nothing
(Just f) <*> x = f <\$> x
instance Applicative (Either e) where
pure = Right
Left err <*> _ = Left err
Right f <*> x = f <\$> x
The "context" of both of these types is that they represent error. All data flow in haskell has to be explicit due to its purity, so these types allow for the propagation of error.
Another example of an applicative functor is a list:
instance Applicative [] where
pure x = [x]
fs <*> xs = [f x  f < fs, x < xs]
Every function in the left list is applied to every function in the right:
[f, g] <*> [x, y, z]
=> [f x, f y, f z, g x, g y, g z]
g <\$> [x,y] <*> [a,b,c]
=> [g x, g y] <*> [a,b,c]
=> [g x a, g x b, g x c, g y a, g y b, g y c]
The context represented by lists is nondeterminism, ie a function f
given one of the arguments [x, y, z]
could have result [f x, f y, f z]
.
Applicative Laws
Applicative functors, like normal functors, also have to obey certain laws:
pure id <*> x = x
 The identity law
 applying pure id does nothing
pure f <*> pure x = pure (f x)
 Homomorphism
pure
preserves function application
u <*> pure y = pure (\$ y) <*> u
 Interchange
 Applying something to a pure value is the same as applying pure ($ y) to that thing
pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
 Composition
 Function composition with
(.)
works within apure
context.
Left and Right Apply
<*
and *>
are two more operators, both defined automatically when <*>
is defined.
const :: a > b > a
const x y = x
flip :: (a > b > c) > b > a > c
flip f x y = f y x
(<*) :: Applicative f => f a > f b > f a
a0 <* a1 = const <\$> a0 <*> a1
(*>) :: Applicative f => f a > f b > f b
a0 *> a1 = flip const <\$> a0 <*> a1
In simple terms *>
is used for sequencing actions, discarding the result of the first argument. <*
is the same, except discarding the result of the second.
Just 4 <* Just 8
=> const <\$> Just 4 <*> Just 8
=> Just (const 4) <*> Just 8
=> Just (const 4 8)
=> Just 4
Just 4 <* Nothing
=> const <\$> Just 4 <*> Nothing
=> Just (const 4) <*> Nothing
=> Nothing
Just 4 *> Just 8
=> flip const <\$> Just 4 <*> Just 8
=> Just (flip const 4) <*> Just 8
=> Just (flip const 4 8)
=> Just (const 8 4)
=> Just 8
Nothing *> Just 8
=> Nothing
These operators are perhaps easier to understand in terms of monadic actions:
as *> bs = do as
bs
as *> bs = as >> bs
as <* bs = do a < as
bs
pure a
Example: Logging
A good example to illustrate the uses of applicative functors is logging the output of a compiler. If we have a function comp
that takes some Expr
type, representing compiler input, and returns some Program
type, representing output :
comp :: Expr > Program
comp (Val n) = [PUSH n]
comp (Plus l r) = comp l ++ comp r ++ [ADD]
 extending to return a String for a log
comp :: Expr > (Program, [String])
comp (val n) = ([PUSH n],["compiling a value"])
comp (Plus l r) = (pl ++ pr ++ [ADD], "compiling a plus" : (ml ++ mr))
where (pl, ml) = comp l
(pr, mr) = comp r
This is messy and not very clear what is going on. There is a much nicer way to do this, using the Writer
type:
 w is the "log"
 a is the containing type (the type in the "box")
data Writer w a = MkWriter (a,w)
type of MkWriter
MkWriter :: (a,w) > Writer w a
 kind of Writer type
Writer :: * > * > *
instance Functor (Writer w) where
 fmap :: (a > b) > Writer w a > Writer w b
fmap f (MkWriter (x,o)) = MkWriter (f x, o)  applies the function to the x value
 a function to write a log
 generates a new writer with a msg and unit type in it's box
writeLog :: String > Writer [w] ()
writeLog msg = MkWriter((), [msg])
Using this to redefine comp
:
comp :: Expr > Writer [String] Program
comp (Val n) = MkWriter ([PUSH n], m)
where (MkWriter (_, m)) = writeLog "compiling a value"
comp (Plus l r) = MkWriter (pl ++ pr ++ [ADD], m ++ ml ++ mr)
where (MkWriter (pl, ml)) = comp l
(MkWriter (pr, mr)) = comp r
(MkWriter (_, m)) = writeLog
This definition of comp combines the output using Writer
, but is messy as it uses pattern matching to deconstruct the results of the recursive calls and then rebuild them into the result. It would be nice if there was some way to implicitly keep track of the log messages.
We can define an instance of the Applicative
typeclass for Writer
to do this. There is the additional constraint that w
must be an instance of Monoid
, because we need some way to combine the output of the log.
instance Monoid w => Applicative (Writer w) where
pure :: a > Writer w a
pure x = MkWriter (x, mempty)
 <*> Monoid w => Writer w (a > b) > Writer w a > Writer w b
MkWriter (f,o1) <*> MkWriter (x,o2) = MkWriter (f x, o1 <> o2)
 f is applied to x, and o1 and o2 are combined using their monoid instance
Using this definition, the comp
function can be tidied up nicely using <*>
comp :: Expr > Writer [String] Program
comp (Val n) = writeLog "compiling a value" *> pure [PUSH n]
comp (Plus l r) = writeLog "compiling a plus" *>
((\p p' > p ++ p' ++ [ADD]) <\$> comp l <*> comp r)
The first pattern uses *>
. Recall that *>
does not care about the left result, which in this case is the unit type, so only the result of the right Writer
is used, which is the [PUSH n]
put into a Writer
by pure
, with a mempty
, or []
as the logged value.
The second pattern applies the anonymous function (\p p' > p ++ p' ++ [ADD])
to the result of the recursive calls. The lambda defines how the results of the recursive calls are combined together, and the log messages are automatically combined by the definition of <*>
. *>
is used again to add a log message to the program.
Monads
ṱ̴̹͙̗̣̙ͮ͆͑̊̅h̸̢͔͍̘̭͍̞̹̀ͣ̅͢e̖̠ͫ̒ͦ̅̉̓̓́͟͞ ͑ͥ̌̀̉̐̂͏͚̤͜f͚͔͖̠̣͚ͤ͆ͦ͂͆̄ͥ͌o̶̡̡̝͎͎̥͖̰̭̠̊r̗̯͈̀̚b̢͙̺͚̅͝i̸̡̱̯͔̠̲̿dͧ̈ͭ̑҉͎̮d̆̓̂̏̉̏͌͆̚͝͏̺͓̜̪͓e̎ͯͨ͢҉͙̠͕͍͉n͇̼̞̙͕̮̣͈͓ͨ͐͛̽ͣ̏͆́̓ ̵ͧ̏ͤ͋̌̒͘҉̞̞̱̲͓k͔̂ͪͦ́̀͗͘n͇̰͖̓ͦ͂̇̂͌̐ȯ̸̥͔̩͒̋͂̿͌w̞̟͔̙͇̾͋̅̅̔ͅlͧ͏͎̣̲̖̥ẻ̴̢̢͎̻̹̑͂̆̽ͮ̓͋d̴̪͉̜͓̗̈ͭ̓ͥͥ͞g͊̾̋̊͊̓͑҉͏̭͇̝̰̲̤̫̥e͈̝̖̖̾ͬ̍͢͞
Monads are another level of abstraction on top of applicatives, and allow for much more flexible and expressive computation. Functors => Applicatives => Monads form a hierarchy of abstractions.
The Monad
typeclass
class Applicative m => Monad m where
(>>=) :: m a > (a > m b) > m b
return :: a > m a
return = pure
The >>=
operator is called bind, and applies a function that returns a wrapped value, to another wrapped value.
 The left operand is some monad containing a value
a
 the right operand is a function of type
a > m b
, ie it takes somea
and returns a monad containing something of typeb
 The result is a monad of type
b
The operator can essentially be thought of as feeding the wrapped value into the function, to get a new wrapped value. x >>= f
unwraps the value in x
from it, and applies the function to f
to it. Understanding bind is key to understanding monads.
return
is just the same as pure
for applicatives, lifting the value a
into some monadic context.
Some example monad instances:
instance Monad Maybe where
Nothing >>= _ = Nothing
Just x >>= f = f x
instance Monad (Either e) where
Left l >>= _ = Left l
Right r >>= f = f r
pure = Right
instance Monad [] where
xs >>= f = concat (map f xs)
Monads give effects: composing computations sequentially using >>=
has an effect. With the State
Monad this effect is "mutation". With Maybe
and Either
the effect is that we may raise a failure at any step. Effects only happen when we want them, implemented by pure functions.
Monad Laws
For a type to be a monad, it must satisfy the following laws:
return a >>= h = h a
 Left identity
m >>= return = m
 Right identity
(m >>= f) >>= g = m >>= (\x > f x >>= g)
 Associativity
Example: Evaluating an Expression
A type Expr
is shown below that represents a mathematical expression, and an eval
function to evaluate it. Note that it is actually unsafe and could crash at runtime due to a div by 0 error. The safediv
function does this using Maybe
.
data Expr = Val Int  Add Expr Expr  Div Expr Expr
eval :: Expr > Int
eval (Val n) = n
eval (Add l r) = eval l + eval r
eval (Div l r) = eval l `div` eval r
safediv :: Int > Int > Maybe Int
safediv x 0 = Nothing
safediv x y = Just (x `div` y)
If we want to use safediv
with eval
, we need to change it's type signature. The updated eval
is shown below using applicatives to write the function cleanly and propagate any errors:
eval :: Expr > Maybe Int
eval (Val n) = Just n
eval (Add l r) = (+) <\$> eval l <*> eval r
eval (Div l r) = safediv <\$> eval l <*> eval r
If any recursive calls return a Nothing
, the entire expression will evaluate to Nothing
. Otherwise, the <\$>
and <*>
will evaluate the expression within the Maybe
context. However, this is still wrong as the last expression now has type of Maybe (Maybe Int)
. This can be fixed using >>=
. Note the use of lambdas.
eval (Div l r) = eval l >>= \x >
eval r >>= \y >
x `safediv` y
The Expr
type can be extended to include a conditional expression, where If Condition True False`.
data Expr = Val Int
 Add Expr Expr
 Div Expr Expr
 If Expr Expr Expr
eval :: Expr > Maybe Int
eval (Val n) = Just n
eval (Add l r) = eval l >>= \x >
eval r >>= \y >
Just (x+y)
eval (Div l r) = eval l >>= \x >
eval r >>= \y >
x `safediv` y
eval (If c t f) = ifA <\$> eval c <*> eval t <*> eval f
where ifA b x y = if b /= 0 then x else y
With this definition using applicatives, both branches of the conditional branch are evaluated. If there is an error in the false branch, the whole expression will fail. Here, using bind, the semantics are correct.
eval' (If c t f) = eval' c >>= \b >
if b /= 0 then eval t else eval f
<*>
vs >>=
Bind is a much more powerful abstraction than apply:
<*> :: m (a > b) > m a > m b
(>>=) :: m a > (a > m b) > m b
 Apply operates on functions already inside a context
 This function can't determine anything to do with the context
 With a
Maybe
, it can't determine if the overall expression returnsNothing
or not
 Bind takes a function that returns a context, and can therefore can determine more about the result of the overall expression
 It knows if it's going to return
Nothing
 It knows if it's going to return
do
Notation
Notice the pattern of >>=
being used with lambdas a fair amount. This can be tidied up with some nice syntactic sugar, called do
notation. Rewriting the earlier example:
eval :: Expr > Maybe Int
eval (Val n) = return n
eval (Add l r) = do
x < eval l
y < eval r
return (x+y)
eval (Div l r) = do
x < eval l
y < eval r
x `safediv` y
This looks like imperative code, but is actually using monads behind the scenes. The arrows bind the results of the evaluation to some local definition, which can then be referred to further down the block.
 A block must always end with a function call that returns a monad 
 usually
return
, butsafediv
is used too
 usually
 If any of the calls within the
do
block shown returnsNothing
, the entire block will shortcircuit to aNothing
.
Example: The Writer
Monad
The example of Writer
as an applicative instance can be extended to make it a Monad
instance.
data Writer w a = MkWriter (a,w)
instance Functor (Writer w) where
 fmap :: (a > b) > Writer w a > Writer w b
fmap f (MkWriter (x,o)) = MkWriter(f x, o)
instance Monoid w => Applicative (Writer w) where
 pure :: Monoid w => a > Writer w a
pure x = MkWriter (x, mempty)
 <*> :: Monoid w => Writer w (a > b) > Writer w a > Writer w b
MkWriter (f,o1) <*> MkWriter (x,o2) = MkWriter (f x, o1 <> o2)
instance Monoid w => Monad (Writer w) where
 return :: Monoid w => a > Writer w a
return = MkWriter (x, mempty) pure
(Writer (x, o1)) >>= f = MkWriter (y, o2 <> o1)
where (MkWriter (y,o2)) = f x
Bind for Writer
applies the function to the x
value in the writer, then combines the two attached written values, and return the new value from the result of f x
along with the combined values.
Now we have a monad instance for the Writer
monad, we can rewrite our comp
function with do
notation:
comp' :: Expr > Writer [String] Program
comp' (Val n) = do
writeLog "compiling a value"
pure [PUSH n]
comp' (Plus l r) = do writeLog "compiling a plus"
pl < comp l
pr < comp r
pure (pl ++ pr ++ [ADD])
Type Level Programming
Type level programming is about encoding more information in our types, so make them more descriptive. The more descriptive types are, the easier it is to avoid runtime errors, as the type checker can do more at compile time.
The GHC language extensions used here are:
XDataKinds
XGATDs
XKindSignatures
XScopedTypeVariables
XTypeFamilies
Type Promotion
As we already know, types have kinds:
Bool :: *
Maybe :: * > *
[] :: * > *
State :: * > * > *
Also recall that we have to partially apply type constructors with kinds greater than * > *
to use them as monads:
 Maybe :: * > *
instance Monad Maybe where
...
 State :: * > * > *
instance Monad (State s) where
...
 Either :: * > * > *
instance Monad Either where
...  type error
instance Monad (Either e) where
...  works
Type Promotion is used to define our own kinds. The DataKinds extension allows for this. Without DataKinds, data Bool = True  False
gives us two constructors, True
and False
. At the three levels in haskell:
 At the kindlevel:
*
 At the typelevel
Bool
 At the valuelevel:
True
orFalse
With DataKinds, we also get the following two new types, both of kind Bool
:
'True :: Bool
'False :: Bool
The value constructors True
and False
have been promoted to the type level as 'True
and 'False
. A new kind is introduced too, Bool
instead of just *
. We now have booleans at the type level.
DataKinds promotes all value constructors to type constructors, and all type constructors to kinds.
Another example, recursively defined natural numbers. Zero
is 0, and Succ Nat
is Nat + 1
.
data Nat = Zero  Succ Nat
 values :: types
Zero :: Nat
Succ :: Nat > Nat
 types :: kinds
'Zero :: Nat
'Succ :: Nat > Nat
Generalised Algebraic Data Types
GADTs allow for more expressive type definitions. Normal ADT syntax:
data Bool = True  False
 gives two values
True :: Bool
False :: Bool
Usually, we define the type and its values, which yields two value constructors. With a GADT, we explicitly specify the type of each data constructor:
data Bool where
True :: Bool
False :: Bool
data Nat where
Zero :: Nat
Succ :: Nat > Nat
The example below defines a recursively defined Vector
type.
 Normally
data Vector a = Nil  Cons a (Vector a)
 GADT
data Vector a where
Nil :: Vector a
Cons :: a > Vector a > Vector a
Example: A Safe Vector
The vector definition above can use another feature, called KindSignatures, to put more detail into the type of the GADT definition:
data Vector (n :: Nat) a where
Nil :: Vector n a
Cons :: a > Vector n a > Vector n a
This definition includes an n
to encode the size of the vector in the type. n
is a type of kind Nat
, as defined above. The values and types were promoted using DataKinds. The type variable n
can also be replaced with concrete types:
data Vector (n :: Nat) a where
Nil :: Vector `Zero a
Cons :: a > Vector n a > Vector (`Succ n) a
 example
cakemix :: Vector ('Succ ('Succ Zero)) String
cakemix = Cons "FishShaped rhubarb" (Cons "4 large eggs" Nil)
This further constrains the types to make the types more expressive. Now we have the length of the list expressed at type level, we can define a safer version of the head function that rejects zerolength lists at compile time.
vhead :: Vector ('Succ n) a > a
 this case will throw an error at compile time as it doesn't make sense
vhead Nil = undefined
vhead (Cons x xs) = x
Can also define a zip function for the vector type that forces inputs to be of the same length. The type variable n
tells the compiler in the type signature that both vectors should have the same length.
vzip :: Vector n a > Vector n b > Vector n (a,b)
vzip Nil Nil = Nil
vzip (Cons x xs) (Cons y ys) = Cons (x,y) (vzip xs ys)
Singleton types
Singletons are types with a 1:1 correspondence between types and values. Every type has only a single value constructor. The following GADT is a singleton type for natural numbers. The (n :: Nat)
in the type definition annotates the type with it's corresponding value at type level. The type is parametrised over n
, where n
is the value of the type, at type level.
data SNat (n :: Nat) where
SZero :: SNat 'Zero
SSucc :: Snat n > SNat ('Succ n)
 there is only one value of type SNat 'Zero
szero :: SNat 'Zero
szero = SZero
 singleton value for one and it's type
sone :: SNat ('Succ 'Zero)
sone = SSucc SZero
stwo :: SNat ('Succ ('Succ Zero))
sone = SSucc sone
There is only one value of each type. The data is stored at both the value and type level.
This can be used to define a replicate function for the vector:
vreplicate :: SNat n > a > Vector n a
vreplicate SZero x = Nil
vreplicate (SSucc n) x = Cons x (vreplicate n x)
The length of the vector we want is SNat n
at type level, which is a singleton type. This allows us to be sure that the vector we are outputting is the same size as what we told it, making sure this type checks.
Proxy Types & Reification
We are storing data at the type level, which allows us to access the data at compile time and statically check it. If we want to access that data at runtime, for example to find the length of a vector, we need a proxy type. Proxy types allow for turning type level data to values, ie turning a type level natural number (Nat
) into an Int
. Haskell has no types at runtime (due to type erasure), so proxies are a hack around this.
 a type NatProxy parametrised over some type a of kind Nat
data NatProxy (a :: Nat) = MkProxy
 NatProxy :: Nat > *
 MkProxy :: NatProxy a
This proxy type is parametrised over some value of type a
with kind Nat
, but there is never actually any values of type a
involved, the info is at the type level. a
is a phantom type.
zeroProxy :: NatProxy 'Zero
zeroProxy = MkProxy
oneProxy :: NatProxy ('Succ 'Zero)
oneProxy = MkProxy
These two proxies have the same value, but different types. The Nat
type is in the phantom type a
at type level.
We can then define a type class, called FromNat
, that is parametrised over some type n
of kind Nat
:
class FromNat (n :: Nat) where
fromNat :: NatProxy n > Int
The function fromNat
takes a NatProxy
, our proxy type, and converts it to an int. Instances can be defined for the two types of Nat
to allow us to covert the type level Nat
s to Int
s.
 instance for 'Zero
instance FromNat 'Zero where
 fromNat :: NatProxy 'Zero > int
fromNat _ = 0
instance FromNat n => FromNat ('Succ n) where
fromNat _ = 1 + fromNat (MkProxy :: NatProxy n)
The arguments to these functions are irrelevant, as the info is in the types. The variable n
refers to the same type variable as in the instance head, using scoped type variables. This hack allows for passing types to functions using proxies, and the converting them to values using reification.
Type Families
Type families allow for performing computation at the type level. A type family can be defined to allow addition of two typelevel natural numbers:
type family Add (n :: Nat) (m :: Nat) :: Nat where
Add 'Zero m = m
Add ('Succ n) m = 'Succ (Add n m)
 alternatively
type family (n :: Nat) + (m :: Nat) :: Nat where
'Zero + m = m
'Succ n + m = 'Succ (n + m)
The type family for (+)
is whats known as a closed type family: once it's defined it cannot be redfined or added to. This type family can be used to define an append function for our vector:
vappend :: Vector n a > Vector m a > Vector (n+m) a
vappend Nil ys = ys
vappend (Cons x xs) ys = Cons x (vappend xs ys)
Importing GHC.TypeLits
allows for the use of integer literals at type level instead of writing out long recursive type definitions for Nat
. This means we can now do:
data Vector (n :: Nat) a where
Nil :: Vector 0 a
Cons :: a > Vector n a > Vector (n+1) a
vappend Nil Nil :: Vector 0 a
vappend (Cons 4 Nil) Nil :: Vector 1 Int
vappend (Cons 4 Nil) (Cons 8 Nil) :: Vector 2 Int
Associated (Open) Type Families
The definition below defines a typeclass for a general collection of items:
class Collection c where
empty :: c a
insert :: a > c a > c a
member :: a > c a > Bool
instance Collection [] where
empty = []
insert x xs = x : xs
member x xs = x `elem` xs
However, the list instance will throw an error, as elem
has an Eq
constraint on it, while the member
type from the typeclass doesn't. Another example, defining the redblack tree as an instance of Collection
(the tree is defined in one of the lab sheets):
instance Collection Tree where
empty = empty
insert x t = insert t x
member x t = member x t
This will raise two type errors, as both insert
and member
for the tree need Ord
constraints, which Collection
doesn't have.
To fix this, we can attach an associated type family to a type class.
class Collection c where
type family Elem c :: *
empty :: c
insert :: a > c > c
member :: a > c > Bool
For an instance of Collection
for some type c
, we must also define a case for c for a type level function Elem
, this establishing a relation between c
and some type of kind *
.
We can now define instance for list and tree, where Eq
and Ord
constraints are placed in instance definition.
instance Eq a => Collection [a] where
type Elem [a] = a
empty = []
insert x xs = x : xs
member x xs = x `elem` xs
instance Ord a => Collection (L.Tree a) where
type Elem (L.Tree a) = a
empty = L.Leaf
insert x t = L.insert t x
member x t = L.member x t
ES191
A (yet incomplete) collection of notes for ES191 Electrical and Electronic Circuits.
This one aims to be fairly comprehensive, so let me know if you think anything is missing.
If you're looking for notes on digital logic, see CS132
Other Useful Resources
 https://www.khanacademy.org/science/electricalengineering/eecircuitanalysistopic/circuitelements/a/eesignconvention
 https://spinningnumbers.org/
 https://www.electronicstutorials.ws/opamp/opamp_1.html
Circuit Symbols and Conventions
Circuits model electrical systems
 Voltage is work done per unit charge
 Potential difference difference in electrical potential between two points in an electric field
 A force used to move charge between two points in space
$V=qW =dqdW $
 Moving charges produce an electric current
 Moving charges can do electrical work the same way moving objects do mechanical work
$I=dtdq $
 Electrical energy is the capacity to do electrical work
 Electrical power is the rate at which work is done
$P=IV=dtdq ⋅dqdW =dtdW $
Resistance
 Resistance is the opposition to the flow of current
 Ohm's Law:
$R=IV $
 Resistance is also proportional to the Resistivity of the material
 $l$ and $A$ are the length and area of the conductor, respectively.
$R=Aρ⋅l $
Sources and Nodes
Everything in a circuit can be modelled as either a source, or a node.
Voltage Sources
 DC and AC voltage sources
 DC source has positive and negative terminals
 Ideal voltage source has 0 internal resistance (infinite conductance)
 Supplies constant voltage regardless of load
 This is an assumption, is not the case in reality
Current Sources
 Ideal current source has infinite resistance (0 conductance)
 Supplies constant current regardless of load
 Also an assumption
 In reality, will have some internal resistance and therefore a maximum power limit
Dependant sources
 Diamondshaped
 Sources depend on values in other parts of the circuit
 Model real sources more accurately
Nodes
All passive elements: generate no electrical power.
 Resistors provide resistance/impedance in Ohms ($Ω$)
 Inductors provide inductance in Henries ($L$)
 Capacitors provide capacitance in Farads ($F$)
The voltage rise across an impedance conducting current is in opposition to the flow of current in the impedance.
Basic Conventions
Electrical current always flows from high to low potential.
 If the direction of the current in a circuit is such that it leaves the positive terminal of a voltage source and enters the negative terminal, then the voltage is designated as negative
 If the direction of the current is such that it leaves the negative and enters the positive, then the voltage is positive
 The sign of the loop current is the terminal that it flows into
The power absorbed/produced by a source is $P=IV$.
 A voltage source is absorbing power if it is supplying a negative current
 A voltage source is producing power if it is supplying a positive current
The power dissapated in a resistor is $P=I_{2}R$.
Resistors in series and parallel
Resistors in series: $R_{t}=R_{1}+R_{2}$
Resistors in parallel: $R_{t}1 =R_{1}1 +R_{2}1 $
Resistors dissipate electrical power, so there is a drop in voltage accross them, in the direction of current flow. Therefore, the voltage rise is in opposition to the direction of current
Voltage dividers
Using two resistors to divide a voltage
In the general case:
$V_{out}=V_{in}×Z_{1}+Z_{2}Z_{2} $
Current Dividers
Similar deal to voltage divider
$I_{R1}=I_{T}×R_{1}+R_{2}R_{2} $ $I_{R2}=I_{T}×R_{1}+R_{2}R_{1} $
Nodal Analysis
Kirchhoff's Current Law
The sum of currents entering a node is equal to the sum of currents leaving a node.
$−I_{1}−I_{2}+I_{3}+I_{4}+I_{5}=0$ $I_{1}+I_{2}=I_{3}+I_{4}+I_{5}$
 Currents flowing into a node are denoted as negative
 Currents flowing out of a node are denoted positive
 The sum of currents around a node must always be 0
Nodal Analysis
A technique used to analyse circuits to calculate unknown quantities. Allows the voltage at each circuit node to be calculated, using KCL.
An important point to remember is that the bottom of any circuit diagram is ground (0V), by convention.
Steps
 Choose 1 node as the reference node
 Label any remaining voltage nodes $V_{1},V_{2},etc...$
 Substitute any known voltages
 Apply KCL at each unknown node to form a set of simultaneous equations
 Solve simultaneous equations for unknowns
 Calculate any required values (usually currents)
Generally speaking, there will be a nodal equation for each node, formed using KCL, and then these equations will solve simultaneously.
Example
Calculate the voltages at nodes $V_{1}$ and $V_{2}$.
There are 4 currents at $V_{1}$
 Flowing from 15V source to $V_{1}$ accross 2 $Ω$ resistor
 Flowing from $V_{1}$ to ground accross 16 $Ω$ resistor
 Flowing between $V_{1}$ and $V_{2}$ accross 7 $Ω$ resistor
 5A, from current source
Each current is calculated using ohm's law, which gives the following nodal equation:
$2V_{1}−15 +16V_{1} +5+7V_{1}−V_{2} =0$
When the direction of each current is not known it is all assumed to be positive, and the voltage at the node is labelled as postive, with any other voltages being labelled as negative. Similar can be done for node $V_{2}$:
$7V_{2}−V_{1} −8+9V_{2}+30 =0$
We now have two equations with two unknowns, which can easily be solved.
$11.29V_{1}−2.29V_{2}=40$ $−9V_{1}+16V_{2}=294$ $V_{1}=8.2V,V_{2}=23.0V$
Admittance Matrices
The system of equations above can also be represented in matrix form
$(11.29−9 −2.2916 )(V_{1}V_{2} )=(40294 )$
This matrix equation always takes the form $Y×V=I$.
$Y$ is known as the Admittance Matrix.
Calculating Power Dissapated
Sometimes, it is required that the power dissapated by voltage/current sources is calculated. For example, calculate the power supplied by the current sources in the following:
KCL at node $V_{1}$: $2+1V_{1}−V_{2} +2V_{1}−V_{3} =0$
KCL at node $V_{2}$: $−3+4V_{2} +1V_{2}−V_{1} =0$
KCL at node $V_{3}$: $3+3V_{3} +2V_{3}−V_{1} =0$
$ 343 −2−50 −10−5 V_{1}V_{2}V_{3} = −4−1218 ⟹ V_{1}V_{2}V_{3} = −3.5−0.4−5.7 $
From the node voltages, the power dissapated in the sources can be calculated. In the 2A source:
$P=IV=2×(0−V_{1})=2×(0−3.5)=7W$
And in the 3A source:
$P=3×(V_{2}−V_{3})=3×(−0.4+5.7)=15.9W$
Note that the voltage accross the current source is always calculated as the node the current is flowing to, minus the node the current is flowing from, ie (to  from). This makes the sign correct so it is known whether the source is delivering or absorbing power. If the direction of the current source oppose the direction of the voltage rise, it will be absorbing power..
If correct, the total power delivered to the circuit will equal the total dissapated. This calculation can be done to check, if you're bothered.
Dependant Sources
Some circuits contain current/voltage sources which are dependant upon other values in the circuit. In the example below, a current $I$ is assumed between the two nodes where the dependant voltage source is.
Calculate the power dissipated by the 50 $Ω$ resistor, and the power delivered by the current source.
At Node $V_{1}$: $5V_{1}−50 +50V_{1} +I=0$
At Node $V_{2}$: $−I+100V_{2} −4=0$
We have two equations in 3 unknowns, so another equation is needed. Using $I_{a}$:
$I_{a}=5V_{1}−50 ,10I_{a}=V_{2}−V_{1}$ These can be equated about $I_{a}$ to give $V_{2}−V_{1}=2V_{2}−100$
This system of equations solves to give $V_{1}=60V$, and $V_{2}=80V$.
Therefore,
 The power delivered by the current source $P=IV=4×80=320W$
 The power dissapated by the 50 $Ω$ resistor is $P=RV_{2} =5060_{2} =72W$
Mesh Analysis
Achieves a similar thing to nodal analysis, using Kirchhoff's voltage law, and meshes instead of nodes.
Kirchhoff's Voltage Law
The sum of voltages around a closed loop always equals zero
$−V_{1}+V_{2}−V_{3}−V_{4}=0$
Sign convention
 If voltage rise and current in a voltage source are in the same direction, the voltage is denoted as negative
 If voltage rise and current are in opposite direction, voltage is positive
 In a resistor, current opposes voltage rise
Steps
 Identify meshes (loops) (always clockwise) and assign currents $I_{1},I_{2},$ etc to those loops
 Apply KVL to each mesh to generate system of equations
 Solve equations
Where there are elements that are part of multiple meshes, subtract the currents of the other meshes from the mesh currently being considered to consider the total current through that circuit element.
Example
There are three meshes in this circuit, labelled $I_{1}$, $I_{2}$, $I_{3}$.
For $I_{1}$: $−50+70I_{1}+20(I_{1}−I_{2})+30(I_{1}−I_{3})+40I_{1}=0$
For $I_{2}$: $20(I_{2}−I_{1})+100I_{2}+80I_{2}+10(I_{2}−I_{3})=0$
For $I_{3}$: $30(I_{3}−I_{1})+10(I_{3}−I_{2})+60I_{3}+90I_{3}=0$
This forms a system of equations:
$160I_{1}−20I_{2}−30I_{3}=50−20I_{1}+210I_{2}−10I_{3}=0−30I_{1}−10I_{2}+190I_{3}=0$
Solving yields $I_{1}=325mA$, $I_{2}=34mA$, and $I_{3}=53mA$.
Impedance Matrices
Similar to how systems of equations from nodal analysis form admittance matrices, mesh analysis forms impedance matrices which describe the circuit being analysed. The matrix equation takes the form $Z⋅I=V$. As an example, the matrix equation for the system above is:
$ 160−20−30 −20210−10 −30−10190 I_{1}I_{2}I_{3} = 5000 $
Therefore, the impedance matrix for the system is:
$Z= 160−20−30 −20210−10 −30−10190 $
Another Example
Determine the currents in the circuit shown below:
Loop 1: $−10+10I_{1}+5(I_{1}−I_{2})=0$
Loop 2: $5(I_{2}−I_{1})+20(I_{2}−I_{3})+V+15I_{2}=0$
Where there is a current source, a voltage $V$ is assumed accross it.
Loop 3: $2I_{3}−20+20(I_{3}−I_{2})=0$
There are now 3 equations with 4 unknowns. However, it can be seen from the diagram that $I_{2}=−4A$ (the direction of the current source opposes our clockwise current), so the system can be solved as follows:
$I_{2}=−4A$ $I_{1}=1510+5I_{2} =−0.67A$ $I_{3}=2220+20I_{2} =−2.73A$
Example with dependant sources
Calculate the power dissapated in the 4 $Ω$ resistor and the power delivered/absorbed by the current dependant voltage source.
KVL round $I_{1}$:
$I_{1}+4(I_{1}−I_{3})+5(I_{1}−I_{2})=0$
KVL round $I_{2}$:
$5(I_{2}−I_{1})+20(I_{2}−I_{3})−50=0$
KVL round $I_{3}$:
$15I_{a}+20(I_{3}−I_{2})+4(I_{3}−I_{1})=0$
$I_{a}=I_{2}−I_{3}$, so this can be substituted into equation 3 to obtain a fourth equation:
$15(I_{2}−I_{3})+20(I_{3}−I_{2})+4(I_{3}−I_{1})=0$
The system of equations then solves:
$ 10−5−4 −525−5 −4−209 I_{1}I_{2}I_{3} = 0500 ⟹$