2.3 Flashcards
big O notation classifications
Classifications of big O notation, ranging from fast efficient algorithms that remain constant despise their input size to the bad ones to be avoided.
- Can help you select the most appropriate one to use and optimise your code.
O(1) Constant
Will always take the same amount of memory (in addition to the list itself).
O(n)Linear
Best time grows at the same rate as the number of elements
This is the case when the data is already in order
O(n2) Polynomial / Quadratic
Worst and average time is proportional to the square (polynomial) of the number of elements
Worst case is when the data is initially in the reverse order
Logarithmic complexity: impact of an algorithm directly proportional to the logarithmic result of the input size (e.g., binary search)
Exponential complexity: the time it take to execute will double with each additional item in the input.
stack
stack operations
stack words
stack push
stack pop
stack peek
stack and queue efficenies
queues
queue operations
enqueueing and dequeuing item from queue
enqueue code
function enqueue(newJob)
if queueTail == 99 then
return -1
else
queueTail = queueTail + 1
buffer[queueTail] = newJob
return 1
endif
endfunction
dequeue code
function dequeue()
if queueHead > queueTail then
return null
else
queueHead = queueHead + 1
return buffer[queueHead-1]
endif
endfunction
difference between stack and queue
how Dijkstra’s algorithm would find the shortest path
Mark A as the initial node and then visit B (5)
Node E (8) is then visited (chosen from C (13), D (14), E (8))
Node I (12) is then visited after E
Node J (14) is then visited after I
Visiting G (18) from I;
Visiting G (15) from C – overriding the previous value of 18
solution A-B-E-I-J path length 14
Compare the performance of Dijkstra’s algorithm and the A* search algorithm,
Heuristic helps produce a solution in a faster time
A* uses estimated distance from final node
Dijkstra uses a weight/distance
A* chooses which path to take next based on lowest
current distance travelled
AO2: Application
Description of how A* will differ from Dijkstra, e.g.
taking the shorter route A-B-E-I before exploring
nodes from D and E
Description of the different number of comparisons
that would be needed in this problem
A* doesn’t need to find all possible solutions (saves
time)
AO3: Evaluation
Candidates will need to evaluate the benefits and
drawbacks of each algorithm
Small-scale problem
Quick to find a solution using either method
Difference in programming complexity is minimal
Don’t know if this problem needs to scale
Most efficient route needed
array
An array is a static collection of items of the same data type called elements. An array is typically used when the required number of data items is known in advance, to store data that would otherwise be stored in multiple variables.
Limitations of using arrays:
1. All data elements in an array must be of the same data type. For example, an array of strings cannot contain an integer.
2. The size of an array is determined when it is declared – i.e., when the algorithm is written – and cannot usually be changed when the program is running.
Assigning data to array
Assigning data to the array can be carried out using syntax similar to:
name[0] = “Craig”
name[1] = “Dave”
name[2] = “Sam”
name[3] = “Carol”
Possible to use an iteration to output all the data in the array:
For index = 0 to 3
Print(name[index])
Next
operations of an array
binary tree
tree operations
multi branch tree
difference between graph, binary tree, tree
linked list
data structure that provides a foundation upon which other structures can be built, e.g. stacks, queues, graphs, trees. constricted from nodes and pointers and a start pointer identifies the first node. each node contains data and a pointer to the next node.
data in lists can be stored anywhere in memory, with pointers indicating the address of the next item.
doubly linked lists have extra pointers, where nodes can point to previous/next items.
circular linked lists can be created by making the last node point to the first.
doubly circular linked lists is when each node in a circular linked list can also have an additional pointer pointing to the previous item.
why and how trees are traversed
depth-first (post-order) traversal
depth-first (post-order) traversal code
breadth-first traversal
breadth-first traversal code
stages of binary search
works on ordered set of data
Repeat
Calculating an array midpoint…
…by adding the array lower bound to the array upper bound, dividing by 2 and rounding
Compare array midpoint with value to search for…
…if equal set found flag to true
…if array midpoint < value to search for, change lowerbound to equal midpoint + 1
…if array midpoint > value to search for, change upperbound to equal midpoint – 1
Until lowerbound is greater than or equal to upperbound
Return/output found flag
binary search code
linear search
.Start at the first item in the list.
2.If the item in the list is the one to be found, the search is complete.
3.If it is not, move to the next item.
4.Repeat from step 2 until the item is found or there are no more items in the list.
5.If the item has been found, output its data. If it has not, output “Not found”.
linear search code
bubble sort
In bubble sort all adjacent items are compared against each other.
The biggest number in the adjacent pair is swapped over with the smallest number and when a swap is made a flag is set.
A temp variable is used to hold the data while it’s being moved. This is repeated for all adjacent values, known as one pass.
At the end of one pass, the largest item should appear at the end of the list.
If at the end of the list the flag has been set the flag is unset and the algorithm starts from the beginning of the list again.
When the algorithm gets to the end of the list and the flag is unset the list is sorted the inner loop will compare l the adjacent items in a single pass the outer loop will repeat the process of checking adjacent items until all passes are completed
bubble sort code
how insertion sort works
insertion sort code
merge sort
merge sort code
quicksort
- Choose a pivot // identify start and end pointers
- Compare each element to the pivot… // compare start and end pointers
- Put items < pivot in the left sublist
- Put items > pivot in the right sublist
- Choose a pivot in each sublist
- If start pointer is larger than end pointer…
- …then swap data items around
- And repeat the process until each item becomes a pivot
decomposing data sets into smaller subsets
* and then sorting each split subset
* until each subset is sorted
* and then combining the subsets to provide a solution
quicksort code
implementations of linked list
can be implemented using a static array, being static data structures, arrays are stored contiguously in memory, requiring the use of index register to determine where a specific index is in relation to a base address. in a linked list the items would be stored alphabetically because of their pointers.
OOP- any available memory address can be used to store data, does not need to be adjacent as each node points to the next in the structure.
applications of linked list
operating systems managing a processor to store process blocks in ready state.
image viewers to switch between previous and next images.
music players to store tracks in a playlist.
web browsers to navigate forwards/backwards.
operations of a linked list
adding an item to a linked list
deleting an item from a linked list
traversing a linked list
analysing an algorithm
Goal is that algorithm should always:
- Run as quickly as possible (time complexity)
- Take up the least amount of memory possible space complexity)
When considering algorithms complexity you should think about time to execute and amount of memory it uses.
classification symbols
labelling classifications
comparison- linear search
comparison- binary search
comparison- bubble sort
comparing searching algorithms
comparing sorting algorithms
enqueue
Check if the queue is full … if the firstElement pointer (+1) = lastElement … if it is return False
* Adds element at lastElement (+1) position … increments lastElement pointer
* If lastElement is greater than last Index …reset to 0
delete node from tree
find node to delete- search the tree to find the location of Node
* Replace the content of the node with null
* Make node before point to the next node
* Add node E to the empty node list
add node to tree
check for dree memory output error if not
Search the tree to find the location of previous node
* Create a new node with value K
* Add a pointer from node before to the new node
* Make new node point to null
similarities and diff of graph and tree
Both consists of nodes
* Both are connected by edges/links
* Both are non-linear data structures
* Both are dynamic data structures
1 mark per difference to max 2
* Tree is 1-directional whereas a graph is 2-directional
* Tree has a root node whereas a graph does not have a (clear) root node
* Tree will not have cycles whereas graphs can contain cycles
* Tree will not be weighted whereas edges in a graph can be weighted
finding node in linked list
Initialise message string
* Start with the headPointer
* Check if the headPointer is null …return that the list is empty
* Check the pointer of the node at headPointer
* If it is not null
* loop through all the linkedList elements
* …concatenate the pointer to the message
* …replacing the pointer with the current node’s pointer each time
* …if the data is found concatenate the pointer and “found” to the message
and return it
* …if the loop ends and the data item is not found, concatenate “not found” to
the message and return it
linked list adv
- …items can be added at different points in the linked list depending on priority
- …by changing the pointers to items needing priority
- Have different queues for different priorities
- …add the job to the queue relevant to its priority
- …print all the jobs in the highest priority queue firs
deleting item from linked list
Traverse the list to the item immediately prior to the item to be
removed (1)
… which is DataItem 1 - Daisy
Find the value of the NextPointer of the item to be removed
… which is the NextPointer of DataItem 2 - Hosta, value 7
Set the nextPointer of the item prior to the item to be removed to
the NextPointer value of the DataItem to be removed
… update the NextPointer of DataItem 1 - Daisy from 2 to 7
(Lavender)
outputing contents of linked list
currentElement = firstElement
while(currentElement != null) print(plantList[currentElement,0])
currentElement = plantList[currentElement,1]
endwhile
difference between array, list and object
