1.4 Data types, data structures and algorithms

Sign and Magnitude

End bit represents whether it is positive or negative, 0 is positive, 1 is negative.

Twos Complement

End bit is a negative value for example 4 bit would be:
-8 4 2 1

Subtracting twos complement

num1 - num2 = num1 + -(num2)

Normalisation

1.0 if negative and 0.1 if positive change exponent so that the decimal is in the correct place.

Character sets

ASCII and Unicode

Stack

FILO - First in last out an example is a back button

Queues

FIFO - First in first out

Circular queue

Have pointers to to know where to store the next item and which item to remove first. It will loop back to the front when it reaches the end.

Linear queue

Items are added to next available space.

Priority queue

Different items within the queue will have different priority levels meaning some will be dequeued before others.

Stack methods

isEmpty() Checks if the stack is empty
push(value) Adds a new value to the top of the stack
peek() Returns the top value of the stack without removing it
pop() Returns and removes the top value of the stack
size() Returns the size of the stack
isFull() Checks if the stack if full

Queue methods

enQueue(value) Adds a new item to the end of the queue deQueue() Removes the item from the end of the queue isEmpty() Checks if the queue if empty
isFull() Checks if the queue is full

Linked lists

Dynamic data structure, each item is called a node and contains data, with a link or pointer which points to the next node.

Graphs

Set of nodes linked together through edges. Is implemented using an adjacency matrix/list.
Directed graph - Can only traverse in one direction
Undirected graph - Can traverse either directions
Weighted graph - Each traversal has a cost attached

Adjacency matrix

Adjacency list

Adjacency matrix vs Adjacency list

Adjacency matrix is convenient to work with and easy to add nodes.
Adjacency list is space efficient for large networks.

Binary search tree

Has a maximum of two children and stores information in order stores each node using a left/right pointer.

Pre-order traversal

2-1-3, middle-left-right

In-order traversal

1-2-3, left-middle-right

Post-order traversal

1-3-2, left-right-middle

Hash table

Has a hash function which takes a key to produce the unique output (the hash). Used to map the key to a unique index in a hash table. If a collision happens the item will be stored in the next available spot.

Gates

AND = ^
OR = v
NOT = ¬
XOR = ⊻

Karnaugh Map

Used to simplify boolean expressions.

De Morgans Law

¬(A ^ B) = ¬A v ¬B
¬(A v B) = ¬A ^ ¬B

Distribution

A ^ (B v C) = (A ^ B) v (A ^ C)
A v (B ^ C) = (A v B) ^ (A v C)

Association

(A ^ B) ^ C = A ^ B ^ C
(A v B) v C = A v B v C

Commutation

A v B = B v A

Double negation

¬¬A = A

D-Type Flip Flops

Full Adder

Three inputs

Half Adder

Two inputs