2.3.1 Algorithms

Question 1

Algorithms

Answer 1

A series of instructions that are used to solve a problem

Question 2

Properties of a good algorithm

Answer 2

1. Produce the correct output for valid inputs
2. Should account for invalid inputs
3. Must always terminate at some point
4. Executes efficiently in as few steps as possible
5. Should be designed such that other people can easily understand and modify it

Question 3

Big O notation

Answer 3

The time complexity of an algorithm, how changing the size of the units affects the runtime
Remove coefficients and write the highest power of n only

Question 4

Big O process

Answer 4

1. Calculate how many times each line runs
2. Simplify
3. Remove coefficients and put O(n^highest power)

Question 5

Sequential big O

Answer 5

O(1)

Question 6

Single loop big O

Answer 6

O(n)

Question 7

Loops inside each other big O

Answer 7

O(n^2)

Question 8

Recursive functions big O

Answer 8

O(numberofrecursions^n)

Question 9

Divide and conquer big O

Answer 9

O(log n)

Question 10

Permutations

Answer 10

The permutation of n items is the number of ways n items should be arranged

Question 11

Permutation where values can be repeated big O

Answer 11

O(a^n)

Where a is the amount of possible values for each

Question 12

Permutation where values can’t be repeated big O

Answer 12

O(n!)

Question 13

Linear search

Answer 13

Iterates through each item in turn until you find the item or have checked every item

Question 14

Linear search pseudocode

Answer 14

Iterating through an array until the value is found, at which point the index is returned or if the loop is completed the value has not been found

Question 15

Linear search big O

Answer 15

O(n)

Question 16

Binary search big O

Answer 16

O(log n)

Question 17

Binary search process

Answer 17

Order the items and examine the middle item of the list. if that is the item it is found, else repeat using the items bigger or smaller than the value depending if it is bigger or smaller than the middle value

Question 18

Binary search pseudocode

Answer 18

The lowerbound starts at 0 and the upperbound 1 less than the list length
The midpoint is (LB + UB) DIV 2
If the midpoint is the value return the index
If the midpoint is less than the value LB is midpoint + 1
If the midpoint is more than the value UB is midpoint - 1
If lowerbound > upperbound it is not found

Question 19

Bubble sort big O

Answer 19

O(n^2)

Question 20

Insertion sort big O

Answer 20

O(n^2)

Question 21

Bubble sort pseudocode

Answer 21

for (i = 0 to length - 2)
for (j = 0 to length - i - 1)
if list[i] > list [i + 1]
temp = list[i]
list[i] = list[i + 1]
list [i + 1] = temp
end if
next j
next i
end procedure

Question 22

Insertion sort pseudocode

Answer 22

for (j = 1 to length - 1)
nextItem = list[j]
i = j - 1
while i>=0 and list[i] > nextItem
list [i+1] = list[i]
i--
end while
list{i+1] = nextItem
next j
end procedure

Question 23

Merge Sort Process

Answer 23

1. Divide the unsorted list into n sublists, each containing one element, halving the length each time
2. Order consecutive pairs of sublists and combine
3. Repeat to have 4 items in each ordered list
4. Repeat until there is one ordered list

Question 24

Merge Sort Big O

Answer 24

n log n

Question 25

Quick Sort Process

Answer 25

1. The first value becomes the pivot, the left pointer starts at the second-left and the right pointer the rightmost 2. Move the left pointer right until it lands on a value greater than the pivot and the right left until it lands on a value one less 3. When both are on said values, swap the values and repeat 4. When the left pointer is to the right of the right pointer, the right pointer swaps with the pivot if it is smaller and the pivot is in position 5. Repeat with each list until it is in order

Question 26

Quick Sort Big O

Answer 26

n log n | worst case: O(n^2)

Question 27

Stable

Answer 27

Keeps identical elements in the same order as in the input

Question 28

Bubble sort advantages and disadvantages

Answer 28

+ easy implementation, stable, in place | - large time complexity, outperformed by other sorting algorithms

Question 29

Insertion sort advantages and disadvantages

Answer 29

+ easy implementation, in place | - unstable, large time complexity

Question 30

Merge sort advantages and disadvantages

Answer 30

+ low time complexity, stable | - hard to implement, slower than quick

Question 31

Quick sort advantages and disadvantages

Answer 31

+ low time complexity, usually the fastest sort | - hard to implement, unstable

Question 32

Dijkstra's Algorithm Process

Answer 32

1. Start with the distance to the start node 0 and infinity to all the others 2. Mark the latest node with the next number in the visited column and for all adjacent nodes where the current weight + distance between is less than the weight, write the sum in the weight and the vertex in the last visited 3. Repeat until you have checked the destination node 4. Trace back through last visited for the route

Question 33

Dijkstra's Algorithm

Answer 33

Vertex | Order visited | Shortest distance | Previous vertex

Question 34

Computable problem

Answer 34

A problem for which an algorithm can solve every instance of it in a finite number of steps

Question 35

Insoluble problem

Answer 35

A problem that is theoretically solvable by a computer but takes an impractical length of time

Question 36

TSP time complexity

Answer 36

O(n!)

Question 37

Tractable problem

Answer 37

A problem with polynomial or better time complexity

Question 38

Limitations of computation

Answer 38

Algorithmic complexity and hardware

Question 39

Heuristic method

Answer 39

A method to find a reasonable solution to an intractable problem within a reasonable time frame, even if it isn't the optimal solution

Question 40

A* table

Answer 40

Vertex | Order visited | Shortest distance (g) | Heuristic (h) | f=g+h | Previous vertex

Question 41

A* method

Answer 41

Similar to Dijkstra, mark the lowest f as visited (shortest path if equal) and add the path to the distance for new paths (only add the heuristic of the destination)

Question 42

Showing how an insertion sort is used

Answer 42

Show the first list with each item in turn used as a pivot and correctly positioned in the growing second list which gains the pivot as a new item each time

Question 43

In place

Answer 43

All sorting happens in the memory space taken up by the actual data

Question 44

Depth first data structures used in algorithm

Answer 44

Uses a list to store the nodes that have been visited | Uses a stack to show the path followed, push on when you go to a child, pop off when you backtrack back to the node

Question 45

Breadth first data structures used in algorithm

Answer 45

Uses a list to store the nodes that have been visited | Uses a queue that the children of the current node are enqueued to when the node is visited, removes and visits in FIFO

Question 46

Queue isFull() pseudocode

Answer 46

``` function isFull() if size == maxSize then return True else: return False end if end function ```

Question 47

Queue isEmpty() pseudocode

Answer 47

``` function isEmpty() if size == 0 then return True: else: return False end if end function ```

Question 48

enQueue() pseudocode

Answer 48

``` procedure enQueue(item) if size < maxSize then rear = (rear + 1) MOD maxSize Q[rear] = item size ++ else: print (queue is full) end if end procedure ```

Question 49

deQueue() pseudocode

Answer 49

``` function deQueue() if size == 0 then item = null print (queue is empty) else: item = Q[front] front = (front + 1) MOD maxSize size -- end if return item end function ```

Question 50

Stack isEmpty() pseudocode

Answer 50

``` function isEmpty() if top == -1 then return True else: return False end if end function ```

Question 51

Stack isFull() pseudocode

Answer 51

``` function isFull() if (top + 1) == maxSize then return True else: return False end if end function ```

Question 52

Stack push() pseudocode

Answer 52

``` procedure push(newItem) if (top + 1) == maxSize then print (stack is full) else: top ++ stack[top] = newItem end if end procedure ```

Question 53

Stack pop() pseudocode

Answer 53

``` function pop() if top == -1 then print (stack is empty) item = null else: item = stack[top] top -- end if return item end function ```

Question 54

In order traversal

Answer 54

Follow the left subtree then visit the root then follow the right

Question 55

Pre-order traversal

Answer 55

Visit the root then follow the left subtree then the right

Question 56

Post-order traversal

Answer 56

Traverse the left subtree then the right then visit the root node

Question 57

Deleting a leaf node

Answer 57

Just remove the node

Question 58

Deleting a node with one child

Answer 58

The child replaces the deleted parent

Question 59

Deleting a node with two children

Answer 59

Repeatedly add 1 to the value of the node until you find the value of another node, which will replace the deleted node

Question 60

Breadth-first traversal

Answer 60

Traverses the root then the children of the root left to right then their children left to right

Question 61

Depth-first (post-order) traversal

Answer 61

Starts at the bottom left and at each leaf it will move up to the latest decision point and go right where it hasn’t been done before