Please enable JavaScript.
Coggle requires JavaScript to display documents.
CS2515 II algorithms - Coggle Diagram
CS2515 II algorithms
Data Types
Arrays - An array is a continuous block of memory of fixed size. This is then split into cells that are the exact same size. In most languages the data type held within these cells must be of the same type
Tuples - A tuple is a sequence of references to objects the length and content of a tuple cannot be changed
The Stack : A stack is a collection of objects that uses a Last In First Out(LIFO) system the most recent object passed into the stack will be the first to exit
The Queue : A queue is a collection of objects that uses a First In First Out(FIFO) system, the first object passed in will be the first to exit
Linked List : a linked list is a set of data that holds two values the memory address of the value(pointer) and the memory address(a pointer) for the next value in sequence
Double Linked List : a double linked list is a set of data that holds three values, a "tail" that points to the address of the last value in sequence, a "head" that points to the next value in sequence and the value itself
Big O notation
In simple terms it is a algebraic expression for how complex a given algorithm is. Formally : f(x) is O(g(x)) if and only if f(x) <= C*g(x)
-
How to derive Big O
-
Add all of those together to get the notation. For example a Big O notation could be O(4 + 5n) where there is 4 O(1)s and 5 O(n)s
Log : Logᵦ x = Bˣ, so Log₂ 8 = 3, because 2³ = 8
ADT's
-
List
add(pos, item) - similar to insert in a list. add "item" at position "pos" again starts at 0
replace(pos, item) same as above it just replaces the item at position "pos" with the "item"
get(pos) - return the item at position(pos) starts at 0. Similar to searching through a list (list[i])
-
-
-
Queue
deque(), returns a data item - removes the item from the front of the queue
-
-
-
Trees
They are connected simple graphs that do not cycle. Trees are not directional but rooted trees are as they have a "start" known as a root
Directional trees
Directional trees have a root that is a "starting point" for the diagram all nodes must come directionally off of the root
defining vertices
-
-
-
all the nodes from v to the root are considered ancestors and all the nodes after v are considered descendents
Binary trees
A binary tree is a rooted tree that has every parent have at most two children they are then identified by left child and right child
depth - the depth of a tree is defined by the length of the longest path from the root to a leaf node
Binary search trees
-
it is the same as a binary tree but every node left of a parent must be less than their parent, every child node to the right must be greater than the parent
-
test details
Likely question topics
Given an practical example and two solutions to the problem then asked to choose between the two and explain why you chose the solution you did
-
-
-
-
-
-
-
Optimisation
An algorithms efficiency is based off of a count of basic steps in the algorithm - anything can be a basic step, an if statement or iterating through a list etc etc
optimisation doesn't matter at a basic level but once the data set the function is working with gets larger and larger an un-optimised function will take much longer to get through the data