Programming: algorithms

Question 1

describe the process of graph traversal

Answer 1

visiting each vertex in a graph

Question 2

what are the two algorithms used for graph traversal?

Answer 2

depth first and breadth first

Question 3

describe the concept of a depth first traversal

Answer 3

a branch is fully explored before back tracking

Question 4

describe the concept of a breadth first algorithm

Answer 4

each adjacent node is fully explored before moving to the next node

Question 5

describe the process of depth first traversal

Answer 5

a stack is used

Question 6

what is the root node in graph traversal

Answer 6

the node from which the traversal starts

Question 7

if the root node were F, with two child nodes being B and G, which child node would be discovered first?

Answer 7

B

Question 8

what is a breadth first algorithm used for?

Answer 8

finding the shortest path on an unweighted graph

Question 9

for depth and breadth graph traversal, which uses a stack and which uses a queue?

Answer 9

depth first traversal uses a stack and a breadth first traversal uses a queue.

Question 10

describe the use of a pre order tree traversal algorithm

Answer 10

can be used to copy a tree

Question 11

describe the use of an in order tree traversal algorithm

Answer 11

outputting the contents of a binary search tree in ascending order

Question 12

describe a purpose of a post order tree traversal algorithm

Answer 12

converting from Infix to reverse polish notation or emptying a tree

Question 13

describe a tree traversal

Answer 13

the process of visiting/updating/outputting each node in a tree.

Question 14

what is the difference between graph and tree traversals?

Answer 14

-tree traversals are unique to trees
-tree traversals must start at the root node

Question 15

where can an in order traversal be used?

Answer 15

only with binary trees

Question 16

what is a binary tree

Answer 16

a rooted, ordered tree in which each parent node has no more than 2 child nodes

Question 17

what is the purpose of reverse polish notation

Answer 17

-it removes the need for brackets
-eliminates confusion over the order of execution

Question 18

describe reverse polish notation

Answer 18

the opcode is written after the operand

Question 19

what is infix and postfix?

Answer 19

infix is a sum written as a human would write it, postfix is a sum written in reverse polish notation form

Question 20

how is a stack used to evaluate postfix equations?

Answer 20

an algorithms goes along an array (containing the postfix expression) and operands are pushed onto a stack. Once an opcode is identified, two items of the stack are popped and the operation is performed.

Question 21

describe a linear search

Answer 21

the list is iterated through and each value in the list is checked until the desired item is found

Question 22

what is the time complexity of a linear search?

Answer 22

O(N)

Question 23

when can a binary search be used?

Answer 23

when the list is sorted. If it is not, it must be sorted before a binary search can be carried out

Question 24

how does a binary search work?

Answer 24

the midpoint of the list is compared to the desired value and depending on if it is higher or lower than it, a half of the list is discounted as it will not contain the desired value. The midpoint of what’s left of the list is then found, and so on.

Question 25

define a binary tree search

Answer 25

functions the same as a binary search, only with the values in a list represented in a binary tree

Question 26

describe the purpose of a sorting algorithm

Answer 26

to put the elements of an array into a specific order

Question 27

what is the advantage of having a sorted list?

Answer 27

a binary search can be performed on a sorted list, which has a time complexity of O(logN), compared o O(N) of a linear search

Question 28

describe the process of a merge sort

Answer 28

a list of items is broken down into individual elements (individual sorted lists) and then combined into groups of two, then groups of four and ordered as they are combined

Question 29

what is an optimisation algorithm?

Answer 29

an algorithm that finds the best possible solution to a problem

Question 30

describe dijkstra’s algorithm

Answer 30

A pathfinding algorithm designed to find the shortest path between two points

Question 31

summarise the functioning of dijkstra’s algorithm

Answer 31

functions similarly to a breadth first searching algorithm, keeping track of visited nodes in a queue. The difference between the two is that a priority queue is used with dijkstra’s algorithm to give weighting to certain paths.

Question 32

where is dijkstra’s algorithm commonly used?

Answer 32

-satellite navigation systems
-routers, shortest network route during packet transmission

Question 33

describe the steps of dijkstra’s algorithm

Answer 33

1.select start and end nodes
2.determine the distance of each adjacent node to the start node
3.the start node is fully explored. Choose the node closest to A and mark it as the shortest distance
4. the shortest path from this node to one of its adjacent nodes is then recorded etc.