3 - Fundamentals of Algorithms

Question 1

What is infix notation?

What is postfix notation (also known as Reverse Polish Notation)?

Answer 1

Infix notation is where the operator is between the operands eg. 5 + 3

Postfix notation is where the operators follow the operands eg. 5 3 +

Question 2

How do you evaluate a postfix expression?

eg.4 2 3 5 1 - + * +

Answer 2

Work from left to right, applying each operator to the previous two operands.

eg.4 2 3 5 1 - + * + → 4 2 3 4 + * +
→ 4 2 7 * + → 4 14 + → 18

Question 3

How do you convert from postfix to infix?

eg.3 4 + 2 *

Answer 3

Work from left to right, moving the operator between the previous two operands and encasing the operands in brackets. Make sure the operands remain in the same order.

eg.3 4 + 2 * → ( 3 + 4 ) 2 *
→ (( 3 + 4 ) * 2 ) → ( 3 + 4 ) * 2

Question 4

How do you convert from infix to postfix?

eg.3 * ( 7 - 2 )

Answer 4

Add brackets to indicate which order to perform the operations. Move the operator to the end of each bracket, then remove the brackets. Make sure the operands are in the same order.

eg.3 * ( 7 - 2 ) → ( 3 * ( 7 2 ) - )
→ ( 3 ( 7 2 ) - ) * → 3 7 2 - *

Question 5

Why is Reverse Polish Notation used?

Answer 5

• Because the order of evaluation of an expression is unambiguous, RPN expressions don’t need brackets.
• Expressions in RPN can be evaluated easily using a stack.
• There is no need for backtracking in evaluation as the operators appear in the order required for computation and can be evaluated from left to right.

Question 6

Where is Reverse Polish Notation used?

Answer 6

RPN is used in interpreters based on a stack for example Postscript and bytecode.

Question 7

What is meant by a recursive subroutine?

Answer 7

A subroutine that calls itself.

Question 8

What are the advantages of Reverse Polish Notation over infix notation?

Answer 8

• Simpler for a computer to evaluate.
• Do not need brackets to show correct order of evaluation.
• Operators appear in the order required for computation.
• No need for order of precedence of operators.
• No need to backtrack when evaluating.

Question 9

What is the complexity of merge sort?

Answer 9

O(nlogn)

Question 10

What is the complexity of bubble sort?

Explain why this is.

Answer 10

O(n²)

In each pass through the list n items will be examine. There will be at most n passes through the list.

Question 11

What is the complexity of binary search?

Explain why this is.

Answer 11

O(logn)

Each comparison halves the size of the list that has to be searched through.

Question 12

What is the complexity of linear search?

Explain why this is.

Answer 12

O(n)

As the size of the list increases the time taken increases at the same rate.

Question 13

What are the steps for Breadth-First Search?

Answer 13

• Mark all vertices as unvisited
• Choose a starting vertex
• Visit the starting vertex and mark it as visited
• Enqueue starting vertex in the queue
• Dequeue a vertex from the queue
• For each neighbouring vertex of this vertex, if it is univisited visit it, mark it as visited and enqueue it in the queue
• Repeat the processor of dequeuing vertices and visiting its neighbours until the queue is empty

Question 14

What is a common use of Breadth-First Search?

Answer 14

To find the path containing the least number of nodes between two points in an unweighted graph.

Question 15

What are the steps for Depth-First Search using a stack?

Answer 15

• Mark the starting vertex as discovered
• Push the starting node onto the stack
• Pop the top vertex off the stack and mark and visit it
• Push each of this vertex’s neighbours to the stack and mark them as discovered
• Repeat the processes of popping vertices and pushing their neighbours to the stack until the stack is empty

Question 16

What is a common use of Depth-First Search?

Answer 16

It is commonly used to navigate a maze.

Question 17

What are the steps for linear search?

Answer 17

• Start with the beginning of the list
• Compare each item with the item you’re searching for
• Stop either when the item is found or the end of the list is reached

Question 18

What are the steps for binary search?

Answer 18

• For a sorted list
• Set the front pointer to 0 and the rear pointer to the index of the last item in the list
• Compare the item in the middle of the two pointers with the item you’re looking for
• If the items are the same, the item is in the list
• If the middle item is less than the item to search for, change the rear pointer to the middle - 1
• If the middle item is greater than the item to search for, change the front pointer to the middle + 1
• Repeat the processes of comparing the middle item until either the item is found or the front pointer is greater than the rear pointer

Question 19

What are the steps for binary tree search?

Answer 19

• Start at the root
• Compare the item at the root to the value you’re searching for
• If it is the same, the item has been found
• If the root is higher, check the left child
• If the root is lower, check the right child
• Keep comparing the value to different nodes until either the item is found or the item has been compared with a leaf node

Question 20

What are the steps for bubble sort?

Answer 20

• Compare the first item to the second item and swap them if they are in the wrong order
• Compare the second item with the third item and swap them if they are in the wrong order
• Keep comparing each pair of adjacent items and swapping them if they are in the wrong order
• After each pair of cards have been compared the first pass is complete
• For the next pass the item at the rear of the list doesn’t need to be compared with (as it is already in the correct position)
• For each pass, the number of items at the rear of the list that don’t need to be compared with increases by 1
• Stop when there is only 1 item that hasn’t been discounted from the comparisons

Question 21

What are the steps for merge sort?

Answer 21

• Repeatedly split the list in half until each sublist contains only 1 item
• Merge each sublist with the sublist that it was most recently split from so that the new list they form is ordered
• Continue merging the sublists until they form a single list

Question 22

What approach to problem solving is merge sort an example of?

Answer 22

‘Divide and conquer’

Question 23

What problem is Dijkstra’s Algorithm designed to solve?

Answer 23

Finding the shortest path between two nodes in a graph (it actually find the shortest path between one node and every other node)

Question 24

What is an application of Dijkstra’s Algorithm?

Answer 24

Routing packets on the Internet