Scribd
Upload
3 views1 page

Shunting Algorithm and Complexity Analysis

This document summarizes a CS tutorial on interpretation and shunting yard algorithms. It discusses putting complexity orders in ascending order, finding pathological cases for algorithms, the complexity of factorial and memoized factorial algorithms, drawing a parse tree for an RPN expression, evaluating expressions using order of operations, and extending the shunting yard algorithm to handle brackets.

Uploaded by

Abhishek Gambhir
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views1 page

Shunting Algorithm and Complexity Analysis

This document summarizes a CS tutorial on interpretation and shunting yard algorithms. It discusses putting complexity orders in ascending order, finding pathological cases for algorithms, the complexity of factorial and memoized factorial algorithms, drawing a parse tree for an RPN expression, evaluating expressions using order of operations, and extending the shunting yard algorithm to handle brackets.

Uploaded by

Abhishek Gambhir
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

CS2001 week 11 tutorial:

Interpretation and shunting (with some complexity)

1. Simplify the following expressions for complexity, explain how you get your answer, and
put them in ascending order or complexity:
a) O(n2)
b) O(n + 2n)
c) O(log(n2))
d) O(n2 + 2n + n log(n))

2. Some algorithms have pathological cases, where they behave significantly worse than one
might expect from their average behaviour. How would you go about finding a pathological
case for an algorithm? Outline the steps you might follow.

3. What is the average-case computational complexity of the factorial algorithm? – argue it


through by identifying the problem size, the basic operation, and the number of times it's
done. How about the memoised version of the algorithm? Does this version have different
best-case complexity? Why?

4. Draw a parse tree that would be equivalent to the following RPN expression (where
“equivalent” means “would be interpreted to the same final value if we used a sensible
interpreter”):

3 2 + 4 * 7 8 9 / + +

5. Operator precedence means we can write expressions without brackets in some cases.
Explain how each of the following expressions are evaluated using the “normal” (Java-like)
precedence rules by putting in enough brackets to make the expression completely
unambiguous regardless of precedence. Comment on any ambiguities you think might cause
problems for programmers.

a) a = 4 * 5 + 6
b) b = p / q % r
c) c = x && y == 1
d) d = p || q && r
e) e = 0 – 1 * 3

6. Show how the shunting algorithm would handle the expression 4 + 5 * 6. showing the
stacks at each step.

7. If we extend the shunting algorithm to cope with brackets, show how it handles the
expression 4 + (4 + 1) * 6.

You might also like