MA-351 Homework 3
Due at 4:59pm in my mailbox in SAS 3151, Tuesday, November 1, 2016
All solutions must be submitted in hardcopy
either to me in class or placed in my mailbox.
Note my office hours on my schedule.
-
DMM §3.6, Problem 13, page 168.
Note that your coloring also needs to include the
country "11" surrounding countries 1-10.
-
Consider
Stirling
's formula for approximating n!:
|
|
n |
|
|
( 2*π )1/2 * ( |
|
)n * n 1/2 |
|
|
e |
|
-
Using the binary operators + (plus), - (minus),
* (times), / (divides),
and ^ (exponentiation), all of which have exactly 2 operands, draw the expression
tree corresponding to this expression. Please note that 1/2 is not a constant.
-
Convert the expression tree into a minimally parenthesized linear infix
expression string, using precedence and left-to-right rules whenever possible.
-
Write the prefix and postfix expression string equivalent to the expression tree.
-
Consider the context-free grammar whose production/rules are
<T> → λ, <T> → <T> ( <T> )
where T in the metasymbols refers to tree.
The terminals are (, ),
λ is the empty string (tree with no vertices),
and the start symbol is
<T>. Please draw the parse tree for the word
()(()())()(())
and then draw the binary tree. Note that the right subtree
is in parentheses, not the left as we did in class.
-
DMM §3.3, Problem 8, page 107. Note: in order to
have a unique DFS tree, assume that the order of
the neighboring vertices of each vertex is alphabetical
and that you start at vertex labeled a.