Full paper 1 flashcards

Stack uses a last in first out system

• must declare a size for it

• push - adding a value - stack can’t be full

• pop -

• push - adding a value - stack can’t be full

• pop removes item from stack make sure stack isn’t empty

allows you to look at the item at the top of the stack - stack can’t be empty

1. make sure stack isn’t empty

2. If stack is empty display an error message

3. if not empty increment stack pointer by 1 and add data item to stack

1. used in memory to store data temporarily

2. undo button

1. check is stack is empty

2. if yes display a appropriate error message

3. if not copy the data item location and decrement it by SP by 1

   Note that this doesn’t delete the item in the stack it will just overwrite it in the next stack

they use first in first out

• they have 2 pointer 1 back pointer and 1 front pointer

• you can only add/ remove items in a que

• there are linear ques: Adding item from the back removing items from the front

• if you add an item increment rear pointer

• if you remove an item increment front pointer

• Also has 2 pointers

• when item is added rear pointer is incremented, also increment number of items

• when items are removed front pointer is incremented, decrement number of item

• keeps track of number of items in que

• if que is rear front pointer will be one behind the front pointer

• if que is empty fp =rp

• it is extremely space inefficient as when you remove an item the front pointer increments and nothing can be added before it

• linear

• circular

• priority

Formats that are used to store large volumes of data

Int, string , Boolean, float, real

are base for all other data types

Theses are data structures that are allocated a fixed amount of memory which doesn’t change throughout the program e.g Array

These are data structures whose memory allocation size can change throughout the program execution eg. Linked list

Inefficient as memory might be allocated but not be used

• Fast access to each element of data as the location doesn’t change

• Fixed structure making it them easier to program

• no fixed structure therefore making it harder to program them

• slower access to each element of data as their location constantly changes

defines data types which are defined by the operations that can be performed on them

• linked list

• stack

• tree

• graphs

a pool of memory that can be allocated to variables during program execution , used in dynamic data structure

• allows more efficient use of memory

when program assigns memory to dynamic variables and never releases them causing memory from heap to run out

Checks if dynamic variable has finished using memory allocated to it and releasees it back to heap

explores the entire branch before backtracking

A node is full explored before before next node is explored

• depth first search uses stack

• breadth first search uses queue

cosθ= (a.b )/ |a||b|

α*z+β*y

• α+β=1

• α,β >=0

+good for graphs with a lot of edges and few vertices

+quicker to find an edge between to nodes

-stores information about each edge connected or not

• +good for graphs with few of edges and a lot vertices

• +less space/ storage wasted

• - need s to look through every edge to find if there is a connection j or not

arrays, dictionaries

A vector can be represented as a list of numbers, as a function and as a way of representing a geometric point in space.

dictionary

1D array

• list [42,110,-5.5, 10.75]

• dictionary { 0:42 , 1:110, 2:-5.5 , 3:10.75}

• Array[3] - myvector[0]=42 …. myvector[3]=10.75

• function

  f: S→ R

  S={0,1,2,3,}

  0→42

  1→110…

• R^{4- vector with 4 elements}

A simple Connected graph ( connected, undirected graph with no cycles)

Each node has maximum of 2 neighbours and has root

a tree which has one node designated as root

a node which has no parents

a subroutine that calls its self

Any recursive subroutine must meet have a stopping condition — base case ( if no base case present it will result in a stack overflow

This is the bit of code which calls itself

• return values

• local parameters

• return addresses

• parameter

Pre order

in order

post order

O(nlogn)

O(C)

O (logn)

O (n)

O (n^k)

O (N²)

O(K^n )

O ( n!)

A model for compuatuion for a machine that is always in one of a fixed number of states

• robotics

• video games

• used to recognise languages

A finite state machine that determines its outputs from the present state and the inputs

A finite state machine that controls 1 or more tapes where at least 1 is infinitely long

turning machine must have a set of instructions telling us which direction to move tape head in , which output is places onto tape based on current state

δ( current state, input symbol )= ( next state, output symbol, movment )

It can represent any FSM unlike turning machines are limited to 1 FSM machine so making them problem specific

• description of the FSM to be used is read from the same tape as input data, than data is processed

• U turning machine acts as interpreter as they read they instructions in sequence before executing operation on input data

• anything a turning machine can compute a real world computer can compute , this tells us which problems are computable and which aren’t