2.3 - Algorithms

Question 1

What two pieces of information allow you to analyse an algorithm?

Answer 1

● Time Complexity
● Space Complexity

Question 2

What is meant by the time complexity of an algorithm?

Answer 2

The amount of time required to solve a particular problem

Question 3

How do you measure of the time complexity?

Answer 3

Big-O notation

Question 4

What does the big-O notation show?

Answer 4

The effectiveness of an algorithm

Question 5

What is the Big-O notation good for?

Answer 5

It allows you to predict the amount of time taken to solve an algorithm given the number of items stored

Question 6

What does a linear time complexity mean?

Answer 6

O(n)

This is where the time taken for an algorithm increases proportionally or at the same rate with the size of the data set.

For example, finding the largest number in a list. If the list size doubles, the time taken doubles.

Question 7

What does a constant time complexity mean?

Answer 7

O(1)

This is where the time taken for an algorithm stays the same regardless of the size of the data set.

For example, printing the first letter of a string. No matter how big the string gets it won’t take longer to display the first letter.

Question 8

What does a polynomial time complexity mean?

Answer 8

O(n^k) (where k>=0)

This is where the time taken for an algorithm increases proportionally to n to the power of a constant.

Bubble sort is an example of such an algorithm.

Question 9

What is space complexity?

Answer 9

The space complexity is the amount of storage space an algorithm takes up

Question 10

What is an algorithm?

Answer 10

An algorithm is a series of steps that complete a task

Question 11

How do you reduce the space complexity?

Answer 11

Try to complete all of the operations on the same data set

Question 12

How do you reduce the time complexity of an algorithm?

Answer 12

You reduce the amount of embedded for loops, and then reduce the amount of items you complete the operations on i.e. divide and conquer

Question 13

What does a Logarithmic time complexity mean?

Answer 13

O(log n)
This is where the time taken for an algorithm increases logarithmically as the data set increases.

As n increases, the time taken increases at a slower rate, e.g. Binary search.

The inverse of exponential growth.

Scales up well as does not increase significantly with the number of data items.

Question 14

What is the Big-O notation of a linear search algorithm?

Answer 14

O(n)

Question 15

What is the Big-O notation of a binary search algorithm?

Answer 15

O(log(n))

Question 16

What is the Big-O notation of a bubble sort algorithm?

Answer 16

O(n^2)

Question 17

Are stacks FIFO or FILO?

Answer 17

FILO

Question 18

What is the significance of the back pointer in the array representation of a queue?

Answer 18

Holds the location of the next available space in the queue

Question 19

What is the purpose of the front pointer in the array representation of a queue?

Answer 19

Points to the space containing the first item in the queue

Question 20

What value is the top pointer initialised to in the array representation of a stack?

Answer 20

-1

Question 21

Give pseudocode for the two functions which add new elements to stacks and queues

Answer 21

STACK
push(element)
top += 1
A[top] = element

QUEUE
enqueue(element)
A[back] = element
back += 1

Question 22

Give pseudocode to push onto a stack

Answer 22

PROCEDURE AddToStack (item):

IF top == max THEN

stackFull = True

ELSE

top = top + 1

stack[top] = item

ENDIF

ENDPROCEDURE

Question 23

Give pseudocode to pop onto a stack

Answer 23

PROCEDURE DeleteFromStack (item):

IF top == min THEN

stackEmpty = True

ELSE

stack[top] = item

top = top - 1

ENDIF

ENDPROCEDURE

Question 24

Give pseudocode to enqueue onto a queue

Answer 24

PROCEDURE AddToQueue (item):

IF ((front - rear) + 1) == max THEN

queueFull = True

ELSE

rear = rear - 1

queue[rear] = item

ENDIF

ENDPROCEDURE

Question 25

Give pseudocode to dequeue onto a queue

Answer 25

PROCEDURE DeleteFromQueue (item): IF front == min THEN queueEmpty = True ELSE queue[front] = item front = front + 1 ENDIF ENDPROCEDURE

Question 26

Perform the first pass of bubble sort on the values: 4, 2, 3, 5, 1

Answer 26

4 2 3 5 1 2 4 3 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 1 5

Question 27

Perform insertion sort on the values: 4, 2, 3, 5, 1

Answer 27

4 2 3 5 1 2 4 3 5 1 2 3 4 5 1 2 3 4 5 1 1 2 3 4 5

Question 28

Perform merge sort on the values: 4, 2, 3, 5

Answer 28

4 2 3 5 4 2 3 5 4 2 3 5 2 4 3 5 2 3 4 5

Question 29

Which of our sorting algorithms is the most efficient?

Answer 29

Merge sort

Question 30

Which sorting algorithm uses pivots?

Answer 30

Quick sort

Question 31

Perform quick sort on the values: 3 5 4 1 2

Answer 31

3 5 4 1 2 3 1 2 4 5 1 3 2 4 5 1 2 3 4 5

Question 32

Which searching algorithm requires data to be sorted before starting?

Answer 32

Binary search

Question 33

Perform a linear search for 9 on the values: 1, 3, 6, 7, 9, 12, 15

Answer 33

1 3 6 7 9 12 15 1 3 6 7 9 12 15 1 3 6 7 9 12 15 1 3 6 7 9 12 15 1 3 6 7 9 12 15 1 3 6 7 9 12 15

Question 34

What is the time complexity of binary search?

Answer 34

O(log n)

Question 35

Perform a binary search for 6 on the values: 1, 3, 6, 7, 9, 12, 15

Answer 35

1 3 6 7 9 12 15 1 3 6 7 9 12 15 1 3 6 7 9 12 15 1 3 6 7 9 12 15

Question 36

Which searching algorithm has a time complexity of O(n)?

Answer 36

Linear search

Question 37

What is Dijkstra's algorithm?

Answer 37

A shortest path algorithm used to find the shortest distance between two nodes in a network.

Question 38

How is Dijkstra's algorithm implemented?

Answer 38

You use a priority queue which has the shortest lengths at the front of the queue.

Question 39

What is the A* algorithm?

Answer 39

The A* algorithm is a general path-finding algorithm which has two cost functions: actual cost and an approximate cost.

Question 40

How does the A* algorithm differ from Dijkstra’s algorithm?

Answer 40

A* algorithm has two cost functions: the actual cost and the approximate cost

Question 41

Why are heuristics used in the A* algorithm?

Answer 41

To calculate an approximate cost from node x to the final node. This aims to make the shortest path finding process more efficient.

Question 42

What data structure can be used to implement Dijkstra’s algorithm?

Answer 42

Priority queue

Question 43

State a disadvantage of using the A* algorithm

Answer 43

The speed of the algorithm is constrained by the accuracy of the heuristic

Question 44

What is depth first traversal?

Answer 44

Visit all nodes to the left of the root node Visit right Visit root node Repeat three points for each node visited Depth first isn’t guaranteed to find the quickest solution and possibly may never find the solution if we don’t take precautions not to revisit previously visited states.

Question 45

What is breadth first traversal?

Answer 45

Visit root node Visit all direct subnodes (children) Visit all subnodes of first subnode Repeat three points for each subnode visited Breadth first requires more memory than Depth first search. It is slower if you are looking at deep parts of the tree.

Question 46

Write pseudocode for depth first traversal

Answer 46

FUNCTION dfs(graph, node, visited): markAllVertices (notVisited) createStack() start = currentNode markAsVisited(start) pushIntoStack(start) WHILE StackIsEmpty() == false popFromStack(currentNode) WHILE allNodesVisited() == false markAsVisited(currentNode) //following sub-routine pushes all nodes connected to //currentNode AND that are unvisited pushUnvisitedAdjacents() ENDWHILE ENDWHILE ENDFUNCTION

Question 47

Write pseudocode for breadth first traversal

Answer 47

FUNCTION bfs(graph, node): markAllVertices (notVisited) createQueue() start = currentNode markAsVisited(start) pushIntoQueue(start) WHILE QueueIsEmpty() == false popFromQueue(currentNode) WHILE allNodesVisited() == false markAsVisited(currentNode) //following sub-routine pushes all nodes connected to //currentNode AND that are unvisited pushUnvisitedAdjacents() ENDWHILE ENDWHILE ENDFUNCTION

Question 48

Write pseudocode that outputs linked list in order

Answer 48

FUNCTION OutputLinkedListInOrder (): Ptr = start value REPEAT Go to node(Ptr value) OUTPUT data at node Ptr = value of next item Ptr at node UNTIL Ptr = 0 ENDFUNCTION

Question 49

Write pseudocode that searches for an item in a linked list

Answer 49

FUNCTION SearchForItemInLinkedList (): Ptr = start value REPEAT Go to node(Ptr value) IF data at node == search item OUTPUT AND STOP ELSE Ptr = value of next item Ptr at node ENDIF UNTIL Ptr = 0 OUTPUT data item not found ENDFUNCTION

Question 50

How do you do bubble sort?

Answer 50

Is intuitive (easy to understand and program) but woefully inefficient. Uses a temp element. Moves through the data in the list repeatedly in a linear way Start at the beginning and compare the first item with the second. If they are out of order, swap them and set a variable swapMade true. Do the same with the second and third item, third and fourth, and so on until the end of the list. When, at the end of the list, if swapMade is true, change it to false and start again; otherwise, If it is false, the list is sorted and the algorithm stops.

Question 51

Write pseudocode that performs bubble sort

Answer 51

PROCEDURE (items): swapMade = True WHILE swapMade == True swapMade = False position = 0 FOR position = 0 TO length(list) - 2 IF items[position] > items[position + 1] THEN temp = items[position] items[count] = items[count + 1] items[count + 1] = temp swapMade = True ENDIF NEXT position ENDWHILE PRINT(items) ENDPROCEDURE

Question 52

Write pseudocode that performs insertion sort

Answer 52

PROCEDURE InsertionSort (list): item = length(list) FOR index = 1 TO item - 1 currentvalue = list[index] position = index WHILE position > 0 AND list[position - 1] > currentvalue list[position] = list[position - 1] position = position - 1 ENDWHILE list[position] = currentvalue NEXT index ENDPROCEDURE

Question 53

How does merge sort work?

Answer 53

Works by splitting n data items into n sub-lists one item big. These lists are then merged into sorted lists two items big, which are merged into lists four items big, and so on until there is one sorted list. Is a recursive algorithm so may require more memory space. Is fast and more efficient with larger volumes of data to sort.

Question 54

Write pseudocode that does a merge sort

Answer 54

PROCEDURE MergeSort (listA, listB): a = 0 b = 0 n = 0 WHILE length(listA) > 1 AND length(listB) > 1 IF listA(a) < listB(b) THEN newlist(n) = listA(a) a = a + 1 ELSE newlist(n) = listB(b) b = b + 1 ENDIF n = n + 1 ENDWHILE WHILE length(listA) > 1 newlist(n) = listA(a) a = a + 1 n = n + 1 ENDWHILE WHILE length(listB) > 1 newlist(n) = listB(b) b = b + 1 n = n + 1 ENDWHILE ENDPROCEDURE

Question 55

How do you do quick sort?

Answer 55

Uses divide and conquer. Picks an item as a ‘pivot’. It then creates two sub-lists: those bigger than the pivot and those smaller than it. The same process is then applied recursively to the sub-lists until all items are pivots, which will be in the correct order. (As this recursive algorithm can be memory intensive, iterative variants exist.) Alternative method uses two pointers. Compares the numbers at the pointers and swaps them if they are in the wrong order. Moves one pointer at a time. Very quick for large sets of data. Initial arrangement of data affects the time taken. Harder to code.

Question 56

Write pseudocode for a quick sort

Answer 56

PROCEDURE QuickSort (list, leftPtr, rightPtr): leftPtr = list[start] rightPtr = list[end] WHILE leftPtr! != rightPtr WHILE list[leftPtr] < list[rightPtr] AND leftPtr! != rightPtr leftPtr = leftPtr + 1 ENDWHILE temp = list[leftPtr] list[leftPtr] = list[rightPtr] list[rightPtr] = temp WHILE list[leftPtr] < list[rightPtr] AND leftPtr! != rightPtr rightPtr = rightPtr - 1 ENDWHILE temp = list[leftPtr] list[leftPtr] = list[rightPtr] list[rightPtr] = temp ENDWHILE ENDPROCEDURE

Question 57

How does the binary search work?

Answer 57

Requires the list to be sorted in order to allow the appropriate items to be discarded. It involves checking the item in the middle of the bounds of the space being searched. It the middle item is bigger than the item we are looking for, it becomes the upper bound. If it is smaller than the item we are looking for, it becomes the lower bound. Repeatedly discards and halves the list at each step until the item is found. Is usually faster in a large set of data than linear search because fewer items are checked so is more efficient for large files. Doesn't benefit from an increase in speed with additional processors. Can perform better on large data sets with one processor than linear search with many processors.

Question 58

Write pseudocode for an iterative binary search

Answer 58

FUNCTION BinaryS (list, value, leftPtr, rightPtr): Found = False IF rightPtr < leftPtr THEN RETURN error message ENDIF WHILE Found == False mid = (leftPtr + rightPtr)/2) IF list[mid] > value THEN rightPtr = mid - 1 ELSEIF list[mid] < value THEN leftPtr = mid + 1 ELSE Found = True ENDIF ENDWHILE RETURN mid ENDFUNCTION

Question 59

Write pseudocode for an recursive binary search

Answer 59

FUNCTION BinaryS (list, value, leftPtr, rightPtr): IF rightPtr < leftPtr THEN RETURN error message ENDIF mid = (leftPtr + rightPtr)/2) IF list[mid] > value THEN RETURN BinaryS (list, value, leftPtr, mid-1) ELSEIF list[mid] < value THEN RETURN BinaryS (list, value, mid+1, rightPtr) ELSE RETURN mid ENDFUNCTION

Question 60

How does linear search work?

Answer 60

Start at the first location and check each subsequent location until the desired item is found or the end of the list is reached. Does not needed an ordered list and searches through all items from the beginning one by one. Generally performs much better than binary search if the list is small or if the item being searched for is very close the to start of the list. Can have multiple processors searching different areas at the same time. Linear search scales very with additional processors.

Question 61

Write pseudocode for a linear search

Answer 61

FUNCTION LinearS (list, value): Ptr = 0 WHILE Ptr < length(list) AND list[Ptr] != value Ptr = Ptr + 1 ENDWHILE IF Ptr >= length(list) THEN PRINT("Item is not in the list") ELSE PRINT("Item is at location "+Ptr) ENDIF ENDFUNCTION

Question 62

What is the worst, average and best case for a bubble sort?

Answer 62

Worst Case: n^2 Average Case: n^2 Best Case: n

Question 63

What is the worst, average and best case for a insertion sort?

Answer 63

Worst Case: n^2 Average Case: n^2 Best Case: n

Question 64

What is the worst, average and best case for a merge sort?

Answer 64

Worst Case: n log n Average Case: n log n Best Case: n log n

Question 65

What is the worst, average and best case for a quick sort?

Answer 65

Worst Case: n^2 Average Case: n log n Best Case: n log n

Question 66

What is the worst, average and best case for a binary search?

Answer 66

Worst Case: log2 n Average Case: log2 n-1 Best Case: 1

Question 67

What is the worst, average and best case for a linear search?

Answer 67

Worst Case: n Average Case: n/2 Best Case: 1