2.3 Algorithms

Question 1

A* algorithm

Answer 1

Approximately finds shortest path between two nodes

Question 2

Big O notation

Answer 2

A way or classifying algorithms based on their complexity

Question 3

Breadth first traversal

Answer 3

A method of traversing a graph by using a queue to visit all the neighbours of the current node before doing the same to each of the neighbours until the entire graph has been explored

Question 4

Depth first traversal

Answer 4

A method of traversing a graph by using a stack to travel as far along one route as possible and then backtracking and doing the same for the remaining routes until the entire graph has been explored

Question 5

What does Dijkstra’s algorithm use

Answer 5

A priority queue

Question 6

Space complexity

Answer 6

A measure of the amount of memory space needed by an algorithms to solve a particular problem of a given input size

Question 7

Time complexity

Answer 7

A measure of the amount of time needed by an algorithm to solve a particular problem of a given input size

Question 8

Constant time complexity O(1)

Answer 8

Time taken is independent from number of elements inputted

Question 9

Exponential O(2^n)

Answer 9

Double with every item added

Question 10

Polynomial time complexity O(n^n)

Answer 10

Proportional to elements inputted to the power of n

Question 11

Processing power and memory

Answer 11

More processing power means time complexity is less important whereas lots of memory means space complexity is less important

Question 12

What do you do to reduce the space complexity

Answer 12

Perform all of the changes on the original pieces of data

Question 13

What do you do to reduce time complexity

Answer 13

Reduce number of embedded loops

Question 14

Best case time complexity for linear search

Answer 14

O(1)

Question 15

Best case time complexity for BINARY search

Answer 15

O(1)

Question 16

Best case time complexity for BUBBLE sort

Answer 16

O(n)

Question 17

How many pointers do stacks use

Answer 17

1 for the top of the stack

Question 18

What is the top pointer of a stack initialised as

Answer 18

-1

Question 19

Why is the top pointer of a stack initialised as -1

Answer 19

When empty, value of 0 would suggest there is an element in the stack

Question 20

Check size of a stack

Answer 20

size()

Question 21

check if a stack is empty

Answer 21

isEmpty()

Question 22

Return top element of stack but do not remove

Answer 22

peek()

Question 23

Add to stack

Answer 23

push(element)

Question 24

Remove top element of stack and return removed element

Answer 24

pop()

Question 25

Check size of queue

Answer 25

size()

Question 26

Check if queue is empty

Answer 26

isEmpty()

Question 27

return front element of queue but do not remove

Answer 27

peek()

Question 28

remove front element from queue and return removed element

Answer 28

dequeue()

Question 29

How can next node be accessed in a linked list

Answer 29

N.next

Question 30

First item of linked list

Answer 30

Head

Question 31

Last item of linked list

Answer 31

tail

Question 32

Best case time complexity for insertion sort

Answer 32

O(n)

Question 33

Worst case for every space complexity

Answer 33

0(1)

Question 34

Average and worst time case for linear search

Answer 34

O(n)

Question 35

Average and worst time case for binary search

Answer 35

0(log(n))

Question 36

Average and worst time case for bubble sort

Answer 36

O(n^2)

Question 37

Average and worst time case for insertion sort

Answer 37

O(n^2)

Question 38

How is dijkstras algorithm implemented

Answer 38

Priority queue

Question 39

Example of when dijstras algorithm can be used

Answer 39

determine the optimal route to
use when forwarding packets through a network.