Unit 12 - Algorithms

Question 1

define big O notation

Answer 1

an approximation of how well an algorithm scales with an increasing data set

Question 2

two main parts of big o

Answer 2

• time complexity
• memory complexity

Question 3

description of O(1)

Answer 3

constant

Question 4

description of O(log n)

Answer 4

logarithmic

Question 5

description of O(n)

Answer 5

linear

Question 6

description of O(n log n)

Answer 6

linearithmic

Question 7

description of O(n^2)

Answer 7

polynomial

Question 8

description of O(2^n)

Answer 8

exponential

Question 9

description of O(n!)

Answer 9

factorial

Question 10

best to worst big O scenarios

Answer 10

O(1)
O(log n)
O(n)
O(n log n)
O(n^2)
O(2^n)
O(n!)

Question 11

best, average and worse case scenarios of time complexity for linear search

Answer 11

best - O(1)
average - O(n)
worst - O(n)

Question 12

best, average and worse case scenarios of time complexity for binary search array

Answer 12

best - O(1)
average - O(log n)
worst - O(log n)

Question 13

best, average and worse case scenarios of time complexity for binary search tree

Answer 13

best - O(1)
average - O(log n)
worst - O(n)

Question 14

best, average and worse case scenarios of time complexity for hashing

Answer 14

best - O(1)
average - O(1)
worst - O(n)

Question 15

best, average and worse case scenarios of time complexity for breadth/depth-first traversal of a graph

Answer 15

best - O(1)
average - O(V + E)
worst - O(v^2)

V = vertices
E = edges

Question 16

best, average and worse case scenarios of time complexity for bubble sort

Answer 16

best - O(n)
average - O(n^2)
worst - O(n^2)

Question 17

best, average and worse case scenarios of time complexity for insertion sort

Answer 17

best - O(n)
average - O(n^2)
worst - O(n^2)

Question 18

best, average and worse case scenarios of time complexity for merge sort

Answer 18

best - O(n log n)
average - O(n log n)
worst - O(n log n)

Question 19

best, average and worse case scenarios of time complexity for quick sort

Answer 19

best - O(n log n)
average - O(n log n)
worst O(n^2)

Question 20

space complexity for bubble sort

Answer 20

O(1)

Question 21

space complexity for insertion sort

Answer 21

O(1)

Question 22

space complexity for merge sort

Answer 22

O(n)

Question 23

space complexity for quick sort

Answer 23

O(log n)

Question 24

what makes a good algorithm

Answer 24

• gives the correct output for any set of valid inputs
• finite number of steps
• accomplish an identifiable task
• must always terminate
• readable code
• minimal memory overhead
• interoperability between algorithms

Question 25

pseudocode for bubble sort

Answer 25

Question 26

similarity between linear and binary search

Answer 26

1. same best case case time complexity = O(1) 2. both find the item being searched for if it is the list

Question 27

differences between binary and linear search

Answer 27

1. different average and worst case time complexities = linear: O(n), binary O(log n) 2. binary search must be performed on a sorted list

Question 28

similarities between bubble and insertion sort

Answer 28

1. both sort the list 2. same best, average and worst case time complexities - O(n) and O(n^2) 3. same space complexity = O(1)

Question 29

differences between bubble and insertion sort

Answer 29

1. in one pass, bubble sort has one item in the correct place where as insertion sort has all items in the correct order

Question 30

pseudocode for insertion sort

Answer 30

Question 31

pseudocode for merge sort

Answer 31

def mergeSort(alist): if len(alist)>1: print("Splitting ",alist) mid = len(alist)//2 # performs integer division lefthalf = alist[:mid] # left half of alist put into lefthalf print ("left half ",lefthalf) righthalf = alist[mid:] # right half of alist put into righthalf print ("right half ",righthalf) mergeSort(lefthalf) mergeSort(righthalf) i=0 j=0 k=0 while i

Question 32

how does a quick sort work

Answer 32

- The algorithm works by finding a split point, which divides the list into two sub lists, one containing items less than the value at the split point, one containing items greater than the value at the split point. - The first step is to choose a value called the pivot value, typically the first item in the list - In order to find the split point where the pivot belongs, left and right pointers are used - The left pointer moves right, until it finds an item larger than the pivot, and then it stops and hands over to the right pointer - The right pointer moves left until it finds an item smaller than the pivot, and then stops - The values in each pointer swap. - The pointers repeat this process until they cross over. - The pivot value swaps with the right pointer – this value is now in place. - Each sub list is treated the same way until it is all sorted.

Question 33

advantages of a quick sort

Answer 33

1. extremely fast time complexity O( n log n) 2. does not need additional memory like merge sort

Question 34

disadvantages of a quick sort

Answer 34

1. if the split point are not near the middle of the list the division will be uneven = O(n^2) 2. if the list is very large and recursion continues too long, it may cause stack overflow and the program will crash

Question 35

what are the two ways to traverse a graph

Answer 35

1. depth first 2. breadth first

Question 36

how does depth-first traversal work

Answer 36

you go as far as you can down a path before backtracking and going down the next path. it uses a stack to keep track of the last node visited, and a list to hold the names of nodes that have been visited – start with both empty

Question 37

pseudocode for depth-first traversal

Answer 37

Question 38

applications of depth first traversal

Answer 38

1. job-scheduling 2. finding a path between two vertices 3. solving puzzles such as navigating a maze

Question 39

how does breadth first traversal work

Answer 39

you explore all neighbours of the current vertex, then the neighbours of each of those vertices and so on. a queue is used to keep track of nodes that we still have to visit.

Question 40

applications of breadth first traversal

Answer 40

1. find the shortest path between two points 2. web crawler 3. facebook uses it to find all the friends of a given individual

Question 41

what is depth-first traversal also known as on trees

Answer 41

pre-order traversal

Question 42

time complexity of a graph with max edges

Answer 42

O(n^2)

Question 43

what is djikstra's algorithm used for

Answer 43

designed to find the shortest path between a start node and every other node in a weighted graph

Question 44

how does djikstra's algorithm work

Answer 44

- uses a priority queue as the supporting data structure to keep record of which vertex to visit next - it starts by assigning a temporary distance value to each node - the temporary distance is 0 at the start node

Question 45

what are computable problems

Answer 45

if there is an algorithm that can solve every instance of it in a finite number of steps

Question 46

what are computational problems

Answer 46

theoretically solvable by computer but if they take millions of years to solve, they are in a sense, insolvable

Question 47

2 limitations of computation

Answer 47

1. algorithmic complexity 2. hardware

Question 48

what is an intractable problem

Answer 48

a problem that does not have a polynomial time solution. although they may have a theoretical solution, it is impossible to solve it within a reasonable time for values of n greater than something very small. big O = O(n!), O(2^n)

Question 49

what is a tractable problem

Answer 49

a problem that has a polynomial time solution or better = O(n), O(nlogn), O(n^2), O(n^k)

Question 50

what are heuristic methods

Answer 50

one which tries to find a solution, which may not be perfect but which is adequate for its purpose

Question 51

how does the A* algorithm work

Answer 51

Two cost functions: - G(x) - the real cost from the source to the given node - H(x) - the approximate cost from node(x) to the goal node (heuristic function) Calculate: f(x) = g(x) + h(x), stipulates that h(x) should NEVER be greater than g(x). The algorithm focuses only on reaching the goal node, unlike Djikstra's algorithm which finds the lowest cost or shortest path to every node.

Question 52

example use for djikstra's algorithm

Answer 52

Question 53

example use of A* algorithm

Answer 53

Question 54

benefits of recursion

Answer 54

- quicker to write – less lines of code - suited to certain problems - trees - reduce the size of a problem with each call - more natural to read

Question 55

drawbacks of recursion

Answer 55

- can run out of stack space due to too many calls causing it to crash - more difficult to trace/follow as each frame on the stack has its own set of variables - requires more memory than the equivalent iterative algorithm - usually slower