What is a stack
Stack uses a last in first out system
must declare a size for it
push - adding a value - stack can’t be full
pop -
what does push do in stack
push - adding a value - stack can’t be full
what does pop do in stack
pop removes item from stack make sure stack isn’t empty
what does peek do in a stack
allows you to look at the item at the top of the stack - stack can’t be empty
What are the steps for pop
make sure stack isn’t empty
If stack is empty display an error message
if not empty increment stack pointer by 1 and add data item to stack
what is stack used for
used in memory to store data temporarily
undo button
What are the steps for push
check is stack is empty
if yes display a appropriate error message
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
What are ques
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
What is linera 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
What is circular que
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
What are the cons of Linear ques
it is extremely space inefficient as when you remove an item the front pointer increments and nothing can be added before it
What types of ques are there
linear
circular
priority
What are data structures
Formats that are used to store large volumes of data
What are strong data structures
Int, string , Boolean, float, real
are base for all other data types
What are static data structures
Theses are data structures that are allocated a fixed amount of memory which doesn’t change throughout the program e.g Array
What are dynamic data structures
These are data structures whose memory allocation size can change throughout the program execution eg. Linked list
cons of static data structure
Inefficient as memory might be allocated but not be used
pros of static data structures
Fast access to each element of data as the location doesn’t change
Fixed structure making it them easier to program
cons of dynamic data structure
no fixed structure therefore making it harder to program them
slower access to each element of data as their location constantly changes
What is abstract data structure
defines data types which are defined by the operations that can be performed on them
What are examples of stack
linked list
stack
tree
graphs
What is a memory heap
a pool of memory that can be allocated to variables during program execution , used in dynamic data structure
allows more efficient use of memory
What is memory leakage
when program assigns memory to dynamic variables and never releases them causing memory from heap to run out
What is Garbage Collector
Checks if dynamic variable has finished using memory allocated to it and releasees it back to heap
What is depth first traversal
explores the entire branch before backtracking
What is breadth first traversal
A node is full explored before before next node is explored
What is the difference between breadth first search and depth first search
depth first search uses stack
breadth first search uses queue
What is the formula to workout angle between to vectores
cosθ= (a.b )/ |a||b|
What is convex combination
α*z+β*y
α+β=1
α,β >=0
what are pros and cons about adjacency matrix
+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
what are pros and cons about adjacency list
+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
What are the ways a vector can be represented
arrays, dictionaries
What are vectors
A vector can be represented as a list of numbers, as a function and as a way of representing a geometric point in space.
what can be use to represent a vector if its viewed as a function
dictionary
what can be use to represent a vector if its viewed as a list
1D array
What are all the vector notation (42,110,-5.5, 10.75)
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…
R4- vector with 4 elements
What is a tree
A simple Connected graph ( connected, undirected graph with no cycles)
What is a binary tree
Each node has maximum of 2 neighbours and has root
What is a rooted tree
a tree which has one node designated as root
what is root node
a node which has no parents
What is recursion
a subroutine that calls its self
What is base case
Any recursive subroutine must meet have a stopping condition — base case ( if no base case present it will result in a stack overflow
What is general case
This is the bit of code which calls itself
What is added to stack frame during recursion
return values
local parameters
return addresses
parameter
Recursion stack frame
Compare recursion and iteration
Which traversal represents polish notation
Pre order
Which traversal represents infix notation
in order
Which traversal represents reverse polish notation
post order
Time complexity of merge sort
O(nlogn)
Time complexity of finding out if number is even or odd
O(C)
Time complexity of binary search
O (logn)
Time complexity of linear search
O (n)
What is time complexity for polynomial
O (n^k)
What is time complexity for bubble sort
O (N²)
what is time complexity of travelling tower of Hanoi
O(K^n )
What is the time complexity of travelling salesman problem
O ( n!)
What is finite state machine
A model for compuatuion for a machine that is always in one of a fixed number of states
What are finite state machines used for
robotics
video games
used to recognise languages
What is mealy machine
A finite state machine that determines its outputs from the present state and the inputs
What is turning machine
A finite state machine that controls 1 or more tapes where at least 1 is infinitely long
What is the transition rule of finite state machine
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
How do you represent turning machine as a transition function
δ( current state, input symbol )= ( next state, output symbol, movment )
How does a universal turning machine work
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
why are turning machines important
anything a turning machine can compute a real world computer can compute , this tells us which problems are computable and which aren’t