topic 4

data type

a classification of data into groups according to the kind of data they represent

name the basic data types

integer, real, char, string, boolean

integer

used to represent whole numbers

real

used to represent numbers with fractional part / decimals

character

used to represent a single character such as a letter, digit or symbol

string

used to represent a sequence of characters

boolean

used to represent true or false values

casting

converting from one data type to another data type

binary

refers to a system of representing information using only 2 digits, 0 and 1

bit

smallest unit of digital information, either an ‘off’ (0) or an ‘on’ (1) state

byte

8 bits

character sets

a published collection of codes and corresponding characters which can be converted to unique binary numbers for computers to represent text

name the 2 most common character sets

ascii

unicode

ascii

character set that uses 7 bits to represent 128 characters - including English letters, digits, punctuations and control characters

extended ascii 

has 8 bits for 256 characters

ascii benefit and drawback

• simple and compact

• limited to English and basic symbols

unicode

32 bits - 140,000 characters. allows representation of characters from all languages and many symbols across different devices and platforms

signed binary numbers

used to represent both positive and negative binary numbers

unsigned binary numbers

used to represent positive binary numbers

how can you represent negative binary numbers

• sign and magnitude

• 2’s complement

sign and magnitude

the most significant bit is for the sign instead of 128. 0 = positive, 1 = negative

downside of sign and magnitude

• loses the maximum size of numbers that can be stored

• can have 2 values for 0

2’s complement

the most significant bit is -128

overflow errors

occurs when the sum of two binary numbers exceeds the given number of bits

what is one method of subtraction

convert the number you are subtracting into two’s complement and then add the two numbers

how do I convert a number into two’s complement

dont change the zeros until the first one which you should keep the same then flip the rest

what’s another method of subtraction 

you subtract normally

• 0-0 = 0

• 1-0 = 1

• 0-1 is when you borrow one from the next column and it is worth 2 

hexadecimal

a base-16 number system that has numbers 0-9 and letters ABCDEF

why use hexadecimal

hexadecimal values are shorter than binary as 4 bits can be represented by one Hex character

hexadecimal values are faster / more reliable to read/write as it is more human friendly

potential uses of hexadecimal

• debugging

• configuring hardware devices

• define colours

what does X subscript n mean

X in base N

mantissa

part of the number that holds the actual digits of the value , represents the precision of the number

exponent

controls how far the binary point moves, controls the scale of the number

what does positive/negative exponent do

positive exponent shifts it to the right

negative exponent shifts it to the left

normalising floating point binary

ensuring the decimal point starts with 01 or 10 to ensure a consistent format and make arithmetic and comparisons more straightforward

logical shifts

process of moving the bits in a binary number to the left or right by a specified number of places

result of left and right shift

left shift - x2

right shift - divide by 2

mask

a binary number used in bitwise operations to isolate, modify, or test specific bits in another binary value

why use a mask

• extract certain bits

• to flip bits

• to set bits to 0 or 1

array

ordered , static set of elements of one data type 

what type of array is a 1d array

linear array

what can 2d arrays be visualised as 

a table 

what can 3d arrays be visualised as

a multi-page spreadsheet

how do you select an element in a 2d and 3d array

2d array : arrayname[x][y]
3d array : arrayname[x][y][z]

record

a row in a file and is made up of fields

What is the definition of a list?

A data structure consisting of a number of items, where the items can occur more than once.

What are the main differences between arrays and lists?

• Lists can store data non-contiguously whereas arrays store data in order.

• Lists can store data of more than one data type.

what does non-contiguously mean

they do not have to be stored next to each other in memory

What is a tuple?

An immutable, ordered set of values of any type.

What is the difference between a tuple and an array?

Tuples are initialised using regular brackets instead of square brackets.

immutable

it can’t be changed , can’t be added or removed once it has been created

What is a stack?

A last in first out data structure, where items can only be removed from and added to the top of the list

Give an example of where stacks may be used.

• Back button in a web page

• Undo buttons

What is a queue?

A first in first out data structure, where items are added to the end of the queue and removed from the front of the queue.

What does the operation isEmpty() do?

Checks to see if the stack is empty

What does the operation push(value) do?

Adds a new value to the top of the stack

What does the operation peek() do?

Returns the top value of the stack without removing it

What does the operation pop() do?

Returns and removes the value at the top of the stack

What does the operation size() do?

It returns the size of the stack

What does the operation isFull() do?

Checks to see if the stack is full.

What does the operation enQueue(value) do?

Adds the value to the end of the queue

What does the operation deQueue() do?

Removes the item from the start of the queue

What does the operation isEmpty() do?

It checks to see if the queue is empty

What does the operation isFull() do?

Checks to see if the queue is full

static data structure

size of the structure cannot change at run time

dynamic data structure

size of the structure can change at run time.

pointers in stacks :

a single pointer is used to point to the top item of the stack,

when a new item is pushed onto the stack the pointer is incremented and when an item is popped off the stack the pointer decrements to point to the new top of the stack

pointers in queues:

a pair of pointers point to the front and back of the queue

if an item is popped from the queue, it points to it and then points to the next item. if an item is pushed , the tail pointer increments by one to point to the new end of queue

Algorithm for insertion into a stack:

• Check to see if the stack is full

2. If the stack is full report error and stop

3. Increment the stack pointer

4. Insert new data item into location pointed to by the stack pointer and stop

Algorithm for deletion/fetching from a stack:

1. Check to see if the stack is empty

2. If the stack is empty report an error and stop

3. Copy the data item in location pointed to by the stack pointer/ delete the data item

4. Decrement the stack pointer

Algorithm for insertion into a queue:

1. Check to see is the queue is full

2. If the queue is full report an error and stop

3. Insert new data item into location pointed to by the tail pointer

4. Increment the tail pointer and stop

Algorithm for deletion/fetching from a queue:

1. Check to see if the queue is empty

2. If the queue is empty report an error and stop

3. Copy data item in location pointed to by the front pointer/ delete the data item

4. decrement front pointer and stop

pointer

an object that stores a memory address

types of queues

linear queue, circular queue

linear queue

a queue implemented in a straight line. elements are added to the rear and removed from the front.

circular queue

static array that has a fixed capacity

difference between linear and circular queues

in a linear queue, if there is space at the front, you cannot reuse it as the tail only moves forward . you cant add new items in a fixed queue with free space unless everything shifts to the left .

In a circular queue, the tail pointer can wrap around to where there is free space so no space is wasted

linked list

a dynamic data structure that is used to hold an ordered sequence

each item is called a node and has a pointer

location of items in a linked list

in a linked list, the items which form the sequence do not have to be in contiguous data locations

how to delete from linked list

remove the pointer of the item and replace the pointer of any value that points towards it so no items point to it

graph

a set of vertices/nodes that are connected by edges/pointers.

types of graphs-

directed graph, undirected graph, weighted graph

directed graph

the edges can only be traversed in one direction

undirected graph

the edges can be traversed in both directions

weighted graph

a value is attached to each edge

how do computers process graphs

adjacent matrix, adjacency list

adjacency matrix

2d array that records relationship between each node and all the other nodes in the graph

adjacency list

a list which records the existence of an edge between each node and all of its neighbours

what are values of edges in unweighted graphs

1 for when an edge exists between 2 nodes, 0 for no edge

applications of graphs

social networks, transport networks, operating system

how to traverse a graph

breadth first search, depth first search

breadth first search

visit all the children of a vertex before moving on to its children

depth first search

visit all the children of the left most vertex and the backtrack to the next one

tree

a connected unweighted graph with no cycles

root node

the node at the very top of the structure

children

subsequent nodes below the current node

branches

the lines that join the nodes

terminal / leaf nodes

nodes without subtrees

binary trees

type of tree where each node is only allowed 2 children

what does each node contain in binary trees

left pointer, data, right pointer