Fundamentals of Algorithms

Question 1

Convert X = A * (B + C) / D to Reverse Polish Notation

Answer 1

1. Use the stack/queue method (input queue, output queue and a operations stack)
   XABC+*D/=

Question 2

When using a stack to evaluate a RPN statement, what do you need to do to how many elements in the stack?

Answer 2

You need to pop the previous 2 elements and use them in the equation

Question 3

Why is RPN used? (3 key ones)

Answer 3

• eliminates need for brackets
• makes it simpler to code
• makes it simpler for the computation

Question 4

Where is RPN used?

Answer 4

Interpreters based on a stack for example Postscript and bytecode

Question 5

CHALLENGE: Convert This infix expression to RPN -
(A+(C+DF+TA)*B/C)

Practice more questions like this!

Answer 5

ACDF+TA+B*C/+

Question 6

What are the 3 common algorithms for traversing trees?

Answer 6

Pre-order, post-order, in-order

Question 7

How is a tree traversal different from a graph traversal?

Answer 7

it has no cycles/loops making it less complex

Question 8

What is the process for a pre-order tree?

Answer 8

Visit the root node and process it
Visit the node to it’s right and process it
THEN visit the node to it’s right and process it (if not then go left and process it)
Once the right side of the tree is processed, begin the same process on the left

Question 9

What is the process for a In-order tree?

Answer 9

For a binary tree, it will be processed alphabetically

Question 10

What is the process for a post-order tree?

Answer 10

Start from the bottom leftmost node on the right side of the root node and process it
Then process the bottoms of the tree and then go up
the root should come at the end of the traversal

Question 11

Write a pseudocode for a pre-order traversal?
Tip: Use a procedure and use the attributes for node as ‘node.left’, ‘node.right’ and ‘node.data’

Answer 11

PROCEDURE pre_order_traversal(node)
PRINT(node.data)
IF node.left != Null THEN
pre_order_traversal(node.left)
ENDIF

       IF node.right != Null THEN
                  pre_order_traversal(node.right)
       ENDIF  ENDPROCEDURE

Question 12

Write a pseudocode for an in-order traversal?
Tip: Use a procedure and use the attributes for node as ‘node.left’, ‘node.right’ and ‘node.data’

Answer 12

PROCEDURE in_order_traversal(node)
IF node.left != Null THEN
in_order_traversal(node.left)
ENDIF
PRINT(node.data)

       IF node.right != Null THEN
                  in_order_traversal(node.right)
       ENDIF ENDPROCEDURE

Question 12

Write a pseudocode for an in-order traversal?
Tip: Use a procedure and use the attributes for node as ‘node.left’, ‘node.right’ and ‘node.data’

Answer 12

PROCEDURE in_order_traversal(node)

Question 13

Write a pseudocode for an post-order traversal?
Tip: Use a procedure and use the attributes for node as ‘node.left’, ‘node.right’ and ‘node.data’

Answer 13

PROCEDURE post_order_traversal(node)
IF node.left != Null THEN
post_order_traversal(node.left)
ENDIF
IF node.right != Null THEN
post_order_traversal(node.right)
ENDIF
PRINT(node.data)
ENDPROCEDURE

Question 14

What can an in-order traversal of a binary tree show?

Answer 14

it can be used to access the values of a binary search tree in ascending order

Question 15

What can a reverse in-order traversal of a binary tree show?

Answer 15

to access the values of a binary search in descending order