4.4 - Fundamentals of Algorithms

Question 1

What is a tree?

Answer 1

A tree is a connected, undirected graph with no cycles.

Question 2

What are the 3 types of tree-traversal algorithms?

Answer 2

In-order
Pre-order
Post-order

Question 3

What is a recursively-defined procedure?
What must it have to be recursive?
What can it be used for?

Answer 3

Recursion (or a recursive procedure) is one that calls itself. It is used when a problem can be broken down, and the same algorithm is repeatedly used on each sub-problem.

It MUST have an end condition, and any recursive algorithm can be written using iteration instead (and vice versa).
It can be used for:
- Sorting agorithms
- Parsing XML/HTML
- Working with files
- In directory structure

Question 4

What is pre-order tree traversal used for?

Answer 4

• Copying a tree

Question 5

What is in-order tree traversal used for?

Answer 5

• Binary earch trees
• Outputing tree nodes in order (print method)
• Polish notation

Question 6

What is post-order tree traversal used for?

Answer 6

• Reverse polish notation

Question 7

What is the issue with infix notation

Answer 7

• There can be ambiguity over the order of operations e.g.
  6 + 4 x 2
  1. (6 + 4) x 2
  OR
  2. 6 + (4 x 2)

Question 8

What is pre-fix notation?

Answer 8

Mathematical notation where the operator is at the start of the operands

Question 9

What is post-fix notation?

Answer 9

Mathematical notation where the operator is at the end of the operands

Question 10

How do we implement post-fx notation using a stack?

Answer 10

1. Read the numbers onto the stack
2. When you reach an operator, pop that last 2 numbers off, apply the operator to them
3. Push the result back onto the stack

Question 11

What is advantage of using post-fix (reverse polish) over pre-fix (polish) notation?

Answer 11

In reverse polish, the operators appear in the order required for completion, therefore are easier to implement using a stack.