1) Fundamentals of algorithms

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.

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.

O (N) This means that the runtime of the function increases directly proportional to the input size. Example; Linear search of an array

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

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

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

O (1) This is when the time taken to run an algorithm does not vary with input size. Example: Indexing an array

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).

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 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.

Different ways in which an item can be arranged.

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)

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 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)

de

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 - 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 - 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.

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)

Def calc(n): if n == 0: factorial = 1 else: factorial = n * calc (n-1) return factorial print( calc(4) )

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

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

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

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 *