1) Fundamentals of algorithms Flashcards
Big-O Notation
Is a measure of the time complexity of an algorithm.
An algorithm with a function f(x) = x+2
The set values that can go into a function (x) is known as the domain.
The set of values produced from the function is known as the codomain.
How Big-O Notation calculates the order of complexity?
Big-O notation calculates the maximum amount of time it takes for an algorithm to complete.
The notation refers to the order of growth (order of complexity) which is the measure of how much more time or space it takes to execute as the input size increases.
Linear Functions
O (N)
This means that the runtime of the function increases directly proportional to the input size.
Example; Linear search of an array
Quadratic Functions
O (N^2)
This means that the runtime of the algorithm is directly proportional to the square of the input size.
Examples;
- Bubble sort
- Selection sort
- Insertion sort
Logarithmic Functions
O (log(N))
O(N) = logv2 (N)
This means that the time taken to run the algorithm increases or decreases in line with a logarithm.
Example: Binary search
Exponential Functions
O (2^N)
The runtime of the algorithm increases as an exponential function to the number of inputs.
For each additional input, the time taken might double.
Example: Intractable problems
Time Constant Functions
O (1)
This is when the time taken to run an algorithm does not vary with input size.
Example: Indexing an array
Deriving the complexity of an algorithm
An algorithm that requires no input data, loops or recursion, such as a simple statement will have a time complexity of O(1).
An algorithm that loops through an array accessing each element will have a time complexity of O (n).
An algorithm with nested loops will increase runtime with the increasing number of inner loops, O (n^2).
An algorithm that uses recursion to call itself will have a time complexity of O (2^N).
Tractable and Intractable problems
A tractable problem is a problem that is said to be solvable in polynomial time.
An intractable problem is a problem that can be solved theoretically but cannot be solved within polynomial time.
The Halting problem
The halting problem is an example of an unsolvable problem where it is impossible to write a program that can work out that whether another problem will halt given a particular input.
Theoretically can be solved but is not possible to solve within a reasonable amount of time.
Permutations
Different ways in which an item can be arranged.
Linear Search Algorithm
SUB linearSearch (namelist,nameSought)
index = -1
i = 0
found = False
WHILE i < len(namelist) AND NOT found:
IF namelist [i] = nameSought:
index = i
found = True
ENDIF
i = i + 1
ENDWHILE
RETURN index
ENDSUB
Total Number of steps:
2n + 3 (In Worst Case)
Time Complexity = O (n)
Bubble Sort Algorithm
FOR i = 1 to n
FOR j = 1 to (n - i)
IF numbers [j] > numbers [j + 1]
a = numbers [j]
numbers [j] = numbers [j + 1]
numbers [j + 1] = a
ENDIF
ENDFOR
ENDFOR
Time Complexity = O (n^2)
Binary Search Algorithm
Binary search is a very efficient way of searching a sorted algorithm.
The middle item is examined in a list, if this is the item you are searching for, return the index.
Eliminate half of the list, depending on whether the item is greater or less than the middle item.
Repeat until the item has been found or it is proved not to be in the list.
SUB binarySearch (array, element, start, end)
IF start > end:
RETURN -1
mid = (start + end) // 2
IF element == array [mid]:
RETURN mid
IF element < array [mid]:
RETURN binarySearch (array, element, start, mid -1)
ELSE:
RETURN binarySearch (array, element, mid+1, end)
Merge Sort Algorithm
de
Representing a graph
Node- an element of a graph or tree.
Edge- a connection between two nodes in a graph or tree.
Graph- a data type made up of edges and nodes.
Node Adjacent nodes A B B A, C, E C B, D D C, E E B, D A two-dimensional array is used to represent a graph.
Depth-first Traversal (Search)
Depth-first traversal - a method for traversing a graph that starts at a chosen node and explores as far as possible down each branch before backtracking.
The algorithm uses a stack to keep track of the last node visited and a list holds all of the nodes that have been visited.
Example:
Graph = {“A”: [“B”, “D”, “E”], “B”: [“A”, “D”, “C”} }
SUB dfs (graph, currentVertex, visited)
append currentVertex to visited nodes
FOR vertex in graph [currentVertex]:
IF vertex NOT in [visited]:
dtf (graph, vertex, visited)
ENDIF
ENDFOR
RETURN visited
ENDSUB
Breadth-first Traversal (Search)
Breadth-first traversal - a method for traversing a graph that explores nodes closest to the starting node first before progressing to node further way.
All nodes adjacent to the current node are visited before moving to the next node. Instead of using a stack, a queue is used to keep track of nodes that still have to be visited.
The complexity of DFS and BFS
A DFS and BFS both visit every vertex and explore every edge.
In a sparse graph, the number of operations is n + e.
O (n)
n = number of vertices
e = number of edges
In a dense graph, the adjacency matrix is full so there are n vertices and n^2 edges, giving vn^2 +n
O (n^2)
Recursive Algorithms
Def calc(n):
if n == 0:
factorial = 1
else:
factorial = n * calc (n-1)
return factorial
print( calc(4) )
Tree Traversal Algorithms
A tree is a data structure, there are 3 ways of traversing a tree; pre-order, in-order and post-order.
Pre-order, 24, 15, 9, 17, 38, 29, 58
In-order, 9, 15, 17, 24, 29, 38, 58
Post-order, 9, 17, 15, 29, 58, 38, 24
A table that represents a tree
left data right tree[0] 1 24 3 tree[1] 5 15 2 tree[2] 17 tree[3] 38 tree[4] 29 tree[5] 9 tree[6] 58
Algorithms for pre, in, post order traversal
SUB preOrderTraverse(p)
OUTPUT tree[p].data (Pre-order)
IF tree[p].left <> -1 THEN
preOrderTraverse (tree[p].left)
ENDIF
OUTPUT tree[p].data (In-Order)
IF tree[p].right <> -1 THEN
preOrderTraverse (tree[p].right)
ENDIF
OUTPUT tree[p].data (Post-order)
ENDSUB
Uses of Post-order traversal
Postfix Notation, 5 + 3 * 8
post_tree = {
0: {"lptr":1, "rptr":3, "Data": "*"},
1: {"lprt":4, "rptr":2, "Data": "+"},
2: {"lptr":-1, "rptr":-1, "Data": 5},
3: {"lptr":-1, "rptr":-1, "Data": 8},
4: {"lptr":-1, "rptr":-1, "Data": 3},
}
Post-order = 5 3 + 8 *Reverse Polish Notation Terminology
Infix- the operator comes between the operands.
a * (b + c) / d
Prefix- (Polish Notation) the operator comes before the operands.
/ * a + b c d
Postfix- (Reverse Polish Notation) the operator comes after the operand.
a b c + * d /
Why is RPN is used?
- This system was used in computer algorithms because evaluation can be done using a stack.
- Eliminates the need for brackets
- Used by interpreters based on a stack such as bytecode.
Precedence
1) -(number)
2) ^
3) * and /
4) + and -
Reverse Polish Notation by Numbering
4 / 2 + 8 * 4 - ( 5 + 2 ) 1 2 1 3 2 4 5 1 3 2 7 4 6 5 8 9 1 3 2 7 4 6 5 11 8 10 9
4 2 / 8 4 * + 5 2 + -
Reverse Polish Notation by Bracketing
a * ( b + c ) / d
( ( a * ( b + c ) ) / d )
( ( a * ( b c + ) ) / d )
( ( a ( b c + ) * ) / d )
( ( a ( b c + ) * ) d /)
a b c + * d /
Translation by a binary tree
((a * ( b + c )) / d )
/
* d
a +
b c
Evaluate RPN by using a stack
5 3 - * 4 2 / -
Stack Pop, execute, Push 3 -3 5 -3 -15 = 5 * -3 5 -15 2 2 = 4 / 2 4 -15 2 -17 = -15 - 2 -15 -17
Dijkstra’s Shortest path algorithm
The algorithm is designed to find the shortest path between a start node and every other node in a weighted graph.
Implementing Dijkstra’s algorithm
Similar to a breadth-first search it uses a priority queue to keep track of which vertex to visit next.
It starts by assigning a temporary distance value to each node, the temporary distance at the start node is 0 and infinity at every other node.
