4.3 Fundamentals of Algorithms

Question 1

What is a Graph Traversal?

Answer 1

A graph traversal is a process of systematically visiting each node in a graph

Question 2

What is a Breadth-first traversal?

Answer 2

1) A Breadth-first traversal is a method for traversing a graph that explores the nodes closest to the starting node
2) A queue is used to track the nodes to be visited (Contents of a queue)

Question 3

What is a Depth-first traversal?

Answer 3

1) A Depth-first traversal starts at a chosen node and explores as far as possible along each branch away from the starting node before backtracking
2) Uses current node and Visited nodes on a graph

Question 4

What are the three ways to traverse a binary tree and how do they work?

Answer 4

1) Pre-Order: Traversing by visiting the root, traversing to the left subtree and the ten traversing to the right subtree
2) Post-Order: Traversing a left subtree then a right subtree and finally visiting the root
3) In-Order: Traversing the left subtree then the root and finally the right subtree

Question 5

What is the use of a Pre-order traversal?

Answer 5

Outputting the contents of a binary search tree in

Question 6

What is the use of a Post-order traversal?

Answer 6

1) Emptying a tree

2) Producing a postfix expression from an expression tree

Question 7

What is the use of a In-order traversal?

Answer 7

Outputting the contents of a binary search tree in ascending order

Question 8

What is recursion?

Answer 8

When a function calls itself eventually unwinding when the procedure ends there must be a true condition that terminates the recursive procedure

Question 9

What is Reverse Polish Nation?

Answer 9

1) A way of writing mathematical expression in a format where the operators are written after the operands
2) E.g. 5 + 3 becomes 5 3 +

Question 10

How do you evaluate infix expressions?

Answer 10

1) 5 + 3
2) You add the 3 to the 5 to create the result
3) 3+ (18/3 squared * 3) -4
- Square 3 = 9
- 18/9 =2
- 2 * 3 = 6
- 3 + 6 = 9
- 9 - 5 = 4

Question 11

What is a Linear Search and what is its time complexity?

Answer 11

1) A search for items in a file, array or memory where the data items are searched one by one until the required one is found or the end of the list is reached

Question 12

What is a Binary Search and what is its time complexity?

Answer 12

1) A Search where the items in the list are sorted it does this by halving the search area with each execution of the loop
2) Split into the middle section and two other sections
2) Start with n items n/2 after 1 comparison n/4 2nd comparison etc…

Question 13

What is the Time Complexity of a Linear Search?

Answer 13

0(n) = Linear

Question 14

What is the Time Complexity of a Binary Search

Answer 14

0(log n) = Logarithmic

Question 15

What is a Binary Tree Search?

Answer 15

1) Same Time Complexity 0 = log(n) = Logarithmic

2) On each pass half of the tree or subtree is eliminated each time its root is examined

Question 16

What is a Bubble Sort Algorithm?

Answer 16

1) The simplest but most inefficient sorting algorithm

2) Uses two nested loops to sort n items

Question 17

What is the time complexity of a Bubble Sort?

Answer 17

0(n squared)

Question 18

What is a Merge sort Algorithm?

Answer 18

1) Uses divide and conquer approach
2) Far more efficient for a larger number of items

Steps:
1) Divides unsorted list into n sublists with each containing a single element

2) Repeatedly merges sublists to produce new sorted sublists until there is only one remaining sorted list

Question 19

What is the Time Complexity of a Merge Sort?

Answer 19

0(nlong n)

n sublists and n factors to be multiplied

Question 20

What is Dijkstra’s shortest path algorithm?

Answer 20

1) Designed to find the shortest path between one particular node and every other node in a weighted graph
2) Uses a priority queue rather than a FIFO queue
3) Uses include distance or time taken to travel between towns, or the cost of travel between airports etc